संगणक विज्ञान हे अल्गोरिदम आणि डेटा स्ट्रक्चर्सच्या गुंतागुंत समजून घेणे आहे.
तुमच्याकडे क्रमवारी लावण्याची आवश्यकता असलेल्या आयटमची सूची आहे, परंतु तुमच्याकडे अधिक क्लिष्ट क्रमवारी अल्गोरिदम वापरण्यासाठी वेळ किंवा संसाधने नाहीत.
इन्सर्शन सॉर्टिंग हे सर्वात सोप्या सॉर्टिंग अल्गोरिदमपैकी एक आहे, परंतु मोठ्या सूचीसाठी ते हळू असू शकते.
सुलभ अंमलबजावणी आणि समजून घेतल्याने ही पद्धत प्रोग्रामरमध्ये आवडते बनली आहे. हे लहान सूचीसाठी किंवा जेव्हा आपल्याला द्रुत समाधानाची आवश्यकता असेल तेव्हा योग्य आहे.
या ब्लॉग पोस्टमध्ये, आम्ही इन्सर्शन सॉर्टिंगच्या वेळेची जटिलता पाहू. हा अल्गोरिदम अॅरे क्रमवारी लावण्यासाठी वापरला जातो आणि त्याचा रनटाइम O(n2). याचा अर्थ अॅरेच्या आकारानुसार वेळेची जटिलता वाढते.
तथापि, हा अल्गोरिदम इतर वर्गीकरण अल्गोरिदमपेक्षा जलद असू शकतो, जसे की क्विकसॉर्ट.
इन्सर्शन सॉर्टिंग कसे कार्य करते ते जवळून पाहूया!
इन्सर्शन सॉर्ट अल्गोरिदम म्हणजे काय?
एका वेळी एक घटक, इन्सर्टेशन सॉर्ट एक सॉर्टेबल अॅरे तयार करते, ज्याला वारंवार सूची म्हणून संबोधले जाते.
उदाहरणार्थ, क्लिष्ट कॉम्प्युटर प्रोग्राम्समध्ये क्रमवारी लावली जाते जसे की कंपाइलर, जिथे टोकन्सचा क्रम प्रोग्रामच्या स्पष्टीकरणासाठी महत्त्वाचा असतो.
इन्सर्शन सॉर्ट कसे कार्य करते?
जेव्हा आपण अॅरेची क्रमवारी लावण्यासाठी इन्सर्टेशन सॉर्ट वापरतो, तेव्हा अल्गोरिदम सूचीमधील सर्वात लहान आयटम शोधून ती योग्य स्थितीत समाविष्ट करून सुरू होते.
ते नंतर पुढील सर्वात लहान आयटम शोधते आणि योग्य स्थितीत समाविष्ट करते, आणि असेच.
अल्गोरिदम सूचीमधून लूप करून, प्रत्येक आयटमची त्याच्या आधी आलेल्या आयटमशी तुलना करून कार्य करते.
आयटम चुकीच्या क्रमाने असल्यास, अल्गोरिदम त्यांना बदलतो. त्यानंतर सूची क्रमवारी लावली आहे की नाही हे तपासते आणि ती असल्यास, अल्गोरिदम संपतो.
प्रॅक्टिसमध्ये, इन्सर्शन सॉर्ट अनेकदा कोडच्या काही ओळी वापरून अंमलात आणले जाते, ज्यामुळे लहान अॅरे क्रमवारी लावण्यासाठी ही एक लोकप्रिय निवड बनते. तथापि, हा अल्गोरिदम वापरताना वेळेची जटिलता विचारात घेतली पाहिजे.
उदाहरण:
इन्सर्शन सॉर्टिंग कसे कार्य करते याचे येथे एक उदाहरण आहे. आम्ही खालील अॅरे वापरू:
1, 2, 3, 4, 5, 6
अल्गोरिदम सूचीतील सर्वात लहान आयटम शोधून सुरू होते, जी 1 आहे. नंतर ती योग्य स्थितीत, पहिल्या स्थानावर समाविष्ट करते. ते नंतर पुढील सर्वात लहान आयटम शोधते, जी 2 आहे. ती योग्य स्थितीत समाविष्ट करते, जी दुसरी स्थिती आहे.
ते नंतर पुढील सर्वात लहान आयटम शोधते, जी 3 आहे. ती ती योग्य स्थितीत समाविष्ट करते, जे तिसरे स्थान आहे.
ते नंतर पुढील सर्वात लहान आयटम शोधते, जी 4 आहे. ती योग्य स्थितीत समाविष्ट करते, जे चौथे स्थान आहे आणि असेच. यादी आता क्रमवारी लावली आहे!
आपण उदाहरणावरून पाहू शकतो की अल्गोरिदम यादी क्रमवारी लावण्यासाठी सहा तुलना आणि स्वॅप घेते. हे n घेते कारण आहे2 n आयटमची सूची क्रमवारी लावण्यासाठी तुलना आणि स्वॅप. या प्रकरणात, n=6.
इन्सर्शन सॉर्ट टाइम क्लिष्टता कशी सुधारायची?
इन्सर्टेशन सॉर्टमध्ये O(n) चा रनटाइम असतो2), क्विकसॉर्ट सारख्या चांगल्या क्रमवारी अल्गोरिदमचा वापर करून ते सुधारले जाऊ शकते.
Quicksort मध्ये O(n log n) रनटाइम आहे, जो O(n) पेक्षा खूप वेगवान आहे2).
तथापि, काही प्रकरणांमध्ये, समाविष्ट करणे क्रमवारी क्विकसॉर्टपेक्षा जलद असू शकते.
उदाहरणार्थ, जर सूची आधीच क्रमाने असेल, तर इन्सर्शन सॉर्टिंग क्विकसोर्टपेक्षा कमी वेळ घेईल.
प्रॅक्टिसमध्ये, इन्सर्शन सॉर्ट अनेकदा कोडच्या काही ओळी वापरून अंमलात आणले जाते, ज्यामुळे लहान अॅरे क्रमवारी लावण्यासाठी ही एक लोकप्रिय निवड बनते.
तथापि, हा अल्गोरिदम वापरताना वेळेची जटिलता विचारात घेतली पाहिजे.
वेळेची गुंतागुंत
सर्वात वाईट केस कॉम्प्लेक्सिटी O(n2):
वेळेची जटिलता अॅरेच्या आकारासह वाढते. एन लागतो2 n आयटमची सूची क्रमवारी लावण्यासाठी तुलना आणि स्वॅप.
उदाहरणार्थ, जर आमच्याकडे 1000 आकाराचा अॅरे असेल, तर अॅरे क्रमवारी लावण्यासाठी अल्गोरिदम 1,000,000 तुलना आणि स्वॅप घेईल.
सर्वोत्तम केस कॉम्प्लेक्सिटी O(n):
वेळ जटिलता इनपुट अॅरेच्या आकाराप्रमाणेच आहे. आय
n आयटमची सूची क्रमवारी लावण्यासाठी t तुलना आणि स्वॅप घेते. उदाहरणार्थ, 5 आकाराच्या अॅरेचा विचार करा. अॅरे क्रमवारी लावण्यासाठी अल्गोरिदम पाच तुलना आणि स्वॅप घेईल.
सरासरी केस जटिलता O(n2):
वेळेची जटिलता या प्रकरणात सर्वात वाईट आणि सर्वोत्तम केस जटिलता दरम्यान आहे.
एन लागतो2 n आयटमची सूची क्रमवारी लावण्यासाठी तुलना आणि स्वॅप.
अशा प्रकारे, इन्सर्टेशन सॉर्टिंग हे एक स्थिर सॉर्टिंग अल्गोरिदम आहे.
अंतर्भूत क्रमवारी स्थिर का आहे?
इन्सर्शन सॉर्ट स्थिर आहे कारण ते इनपुट अॅरेमधील समान घटकांचा क्रम राखून ठेवते.
डेटा पुनर्प्राप्ती किंवा आर्थिक विश्लेषण यासारख्या अनेक अनुप्रयोगांसाठी हे महत्त्वाचे आहे. उदाहरणार्थ, जर आमच्याकडे संख्यांच्या दोन याद्या असतील आणि त्यांची तुलना करायची असेल, तर घटकांचा क्रम जतन केला आहे याची आम्हाला खात्री करावी लागेल.
याद्या क्रमवारी लावल्या नसल्यास, आम्ही त्यांची अचूक तुलना करणार नाही.
प्रत्युत्तर द्या