सामग्री

• तुलना चार्ट
• द्रुत क्रमवारीची व्याख्या
• मर्ज सॉर्ट ची व्याख्या
• निष्कर्ष

द्रुत क्रमवारी आणि विलीन सॉर्ट अल्गोरिदम विभाजन आणि विजय अल्गोरिदम वर आधारित आहेत जे अगदी समान प्रकारे कार्य करतात. द्रुत आणि विलीनीकरण क्रमवारी दरम्यान पूर्वीचा फरक हा आहे की द्रुत क्रमवारीमध्ये मुख्य घटक क्रमवारीसाठी वापरला जातो. दुसरीकडे, मर्ज सॉर्ट क्रमवारी लावण्यासाठी मुख्य घटक वापरत नाही.

क्रमवारी लावण्याची दोन्ही तंत्रे, द्रुत क्रमवारी आणि विलीनीकरण क्रमवारी विभाजन आणि विजय यावर आधारित आहेत ज्यामध्ये घटकांचा संच विभागला जातो आणि नंतर पुनर्रचना नंतर एकत्र केला जातो. द्रुत क्रमवारीत घटकांच्या मोठ्या संचाची क्रमवारी लावण्यासाठी विलीन क्रमवारीपेक्षा अधिक तुलना आवश्यक असते.

1. 1. तुलना चार्ट
   2. व्याख्या
   3. मुख्य फरक
   4. निष्कर्ष

तुलना चार्ट

तुलना करण्यासाठी आधार	द्रुत क्रमवारी	क्रमवारी विलीन करा
अ‍ॅरे मधील घटकांचे विभाजन	घटकांच्या यादीचे विभाजन अर्ध्या भागामध्ये करणे आवश्यक नाही.	अ‍ॅरे नेहमी अर्ध्या (एन / 2) मध्ये विभागली जाते.
सर्वात वाईट प्रकरणांची जटिलता	ओ (एन2)	ओ (एन लॉग एन)
चांगले कार्य करते	लहान अ‍ॅरे	कोणत्याही प्रकारच्या अ‍ॅरेमध्ये दंड चालवते.
वेग	लहान डेटा सेटसाठी सॉर्टिंग अल्गोरिदमपेक्षा वेगवान.	सर्व प्रकारच्या डेटा सेटमध्ये सुसंगत वेग.
अतिरिक्त संचयन जागेची आवश्यकता	कमी	अधिक
कार्यक्षमता	मोठ्या अ‍ॅरेसाठी अपात्र.	अधिक कार्यक्षम
क्रमवारी लावण्याची पद्धत	अंतर्गत	बाह्य

द्रुत क्रमवारीची व्याख्या

द्रुत क्रमवारी अल्गोरिथ्म छोट्या अ‍ॅरेसाठी जलद असल्याने सर्वत्र वापर केला जातो. घटकांचा संच वारंवार विभाजित केला जातो जोपर्यंत त्याचे विभाजन करणे शक्य होत नाही तोपर्यंत. द्रुत क्रमवारी देखील म्हणून ओळखले जाते विभाजन विनिमय क्रमवारी. हे घटक विभाजित करण्यासाठी की घटक (पिव्होट म्हणून ओळखले जाते) वापरते. एका विभाजनात ते घटक असतात जे की घटकांपेक्षा लहान असतात. दुसर्‍या विभाजनात ते घटक असतात जे की घटकांपेक्षा मोठे असतात. घटक वारंवार पुनरावृत्ती होते.

समजा ए हा एक अ‍ॅरे, ए, ए, …… .., ए क्रमांकाच्या क्रमांकावर आहे. द्रुत क्रमवारी अल्गोरिदम मध्ये खालील चरणांचा समावेश आहे.

1. की म्हणून निवडलेला पहिला घटक किंवा कोणताही यादृच्छिक घटक, की = अ (1) समजू.
2. “लो” पॉईंटर दुस at्या बाजूला ठेवला आहे आणि “अप” पॉईंटर अ‍ॅरेच्या शेवटच्या घटकावर स्थित आहे, म्हणजे, लो = 2 आणि अप = एन;
3. सातत्याने, (ए> की) पर्यंत एका स्थानाद्वारे “कमी” पॉईंटर वाढवा.
4. सतत, (अप <= की) पर्यंत एका स्थानाद्वारे “अप” पॉईंटर कमी करा.
5. अप ए सह कमी अदलाबदल ए पेक्षा जास्त असल्यास.
6. चरण 5 मधील स्थिती अपयशी होईपर्यंत चरण 3,4, आणि 5 ची पुनरावृत्ती करा (उदा. <= कमी) नंतर की बरोबर अ बदला.
7. की च्या डावीकडे असलेले घटक किल्लीपेक्षा लहान असल्यास आणि की च्या उजव्या घटकांपेक्षा की जास्त असल्यास अ‍ॅरे दोन उप-अ‍ॅरेमध्ये विभाजित केल्या जातात.
8. संपूर्ण अ‍ॅरेची क्रमवारी लावल्याशिवाय वरील प्रक्रिया वारंवार उपनगरीत लागू केली जाते.

   

   
   

फायदे आणि तोटे

त्यात एक चांगली सरासरी केस वर्तन आहे. द्रुत क्रमवारीची चालू वेळची गुंतागुंत चांगली आहे ती म्हणजे बबल सॉर्ट, समाविष्ट क्रमवारी आणि निवड क्रमवारी यासारख्या अल्गोरिदमपेक्षा वेगवान आहे. तथापि, हे गुंतागुंतीचे आणि खूप रिकर्सिव आहे, म्हणूनच ते मोठ्या अ‍ॅरेसाठी योग्य नाही.

मर्ज सॉर्ट ची व्याख्या

क्रमवारी विलीन करा बाह्य अल्गोरिदम आहे जो विभाजन आणि विजय रणनीतीवर देखील आधारित आहे. केवळ एक घटक शिल्लक होईपर्यंत घटक पुन्हा-पुन्हा उप-अ‍ॅरे (एन / 2) मध्ये विभागले जातात, जे सॉर्टिंगची वेळ लक्षणीय घटवते. हे सहाय्यक अ‍ॅरे संचयित करण्यासाठी अतिरिक्त संचयन वापरते. विलीनीकरण क्रमवारीत तीन अ‍ॅरे वापरतात जिथे दोन अर्ध्या अर्ध्या संग्रहासाठी वापरले जातात आणि तिसरा शेवटचा क्रमवारी लावलेली यादी संग्रहित करण्यासाठी वापरला जातो. नंतर प्रत्येक अ‍ॅरे पुनरावृत्ती क्रमवारीत लावली जाते. सरतेशेवटी, अ‍ॅरेचा घटक घटक बनवण्यासाठी सबरॅरीज विलीन केल्या गेल्या. यादी नेहमी अर्ध्या (एन / 2) मध्ये विभागली जाते द्रुत क्रमवारीपेक्षा भिन्न असते.

A, A, ………, A. क्रमवारी लावल्या जाणा n्या घटकांच्या संख्येचा अ‍ॅरे असू द्या विलीन क्रमवारी दिलेल्या चरणांचे अनुसरण करते.

1. अ‍ॅरे एला अंदाजे n / 2 च्या क्रमवारी लावलेल्या उप-अरेमध्ये 2 ने विभाजित करा, ज्याचा अर्थ असा आहे की (ए, ए), (ए, ए), (ए, ए), (ए, ए) उप-अ‍ॅरे आवश्यक आहेत क्रमवारी लावा.
2. आकार 4 च्या क्रमवारी लावलेल्या सबर्रेची यादी मिळविण्यासाठी प्रत्येक जोड्या एकत्र करा; सबरी मधील घटक देखील क्रमवारीत आहेत (ए, ए, ए, ए), ……, (ए, ए, ए, ए), ……., (ए, ए, ए, ए).
3. आकार n ची केवळ एक क्रमवारी केलेली अ‍रेपर्यंत चरण 2 वारंवार केला जातो.

   

फायदे आणि तोटे

मर्ज सॉर्ट अल्गोरिदम वर्गीकरणात समाविष्ट असलेल्या घटकांची संख्या विचारात न घेता अगदी तंतोतंत आणि तंतोतंत कार्य करते. मोठ्या डेटा सेटसह देखील हे ठीक कार्य करते. तथापि, तो मेमरीचा मोठा भाग वापरतो.

1. विलीनीकरण क्रमवारीत अ‍ॅरे फक्त दोन भागांमध्ये विभागली जाणे आवश्यक आहे (उदा. एन / 2) याउलट, द्रुत क्रमवारीत, यादी समान घटकांमध्ये विभाजित करण्याची सक्ती नाही.
2. द्रुत क्रमवारीची सर्वात वाईट बाब म्हणजे ओ (एन) आहे²) सर्वात वाईट परिस्थितीत बरीच तुलना घेण्यामुळे. याउलट, विलीनीकरण क्रमवारीत समान सर्वात वाईट केस आणि सरासरी केस गुंतागुंत आहेत ती ओ (एन लॉग एन) आहे.
3. विलीनीकरण क्रमवारी कोणत्याही प्रकारच्या डेटा सेटवर चांगले किंवा ऑपरेट करू शकते की ती मोठी किंवा लहान आहे. उलटपक्षी, द्रुत क्रमवारी मोठ्या डेटासेटसह चांगले कार्य करू शकत नाही.
4. लहान डेटा सेट्ससारख्या प्रकरणांमध्ये द्रुत क्रमवारी विलीन करण्यापेक्षा वेगवान आहे.
5. विलीन क्रमवारीस सहाय्यक अ‍ॅरे संचयित करण्यासाठी अतिरिक्त मेमरी स्पेसची आवश्यकता आहे. दुसरीकडे, द्रुत क्रमवारीत अतिरिक्त संचयनासाठी जास्त जागा आवश्यक नसते.
6. विलीन सॉर्ट द्रुत क्रमवारीपेक्षा अधिक कार्यक्षम आहे.
7. द्रुत क्रमवारी ही अंतर्गत क्रमवारी लावण्याची पद्धत आहे जिथे क्रमवारी लावायचा डेटा मुख्य मेमरीच्या वेळी समायोजित केला जातो. उलट, मर्ज सॉर्ट ही बाह्य क्रमवारी लावण्याची पद्धत आहे ज्यात क्रमवारी लावायचा डेटा त्याच वेळी मेमरीमध्ये सामावून घेता येणार नाही आणि काही सहाय्यक मेमरीमध्ये ठेवावा लागतो.

निष्कर्ष

द्रुत क्रमवारी ही वेगवान प्रकरणे असतात परंतु काही परिस्थितींमध्ये ती अकार्यक्षम असतात आणि विलीनीकरण क्रमवारीच्या तुलनेत बर्‍याच तुलना देखील करतात. विलीनीकरण क्रमवारीत कमी तुलना आवश्यक असला तरी अतिरिक्त अ‍ॅरे संचयित करण्यासाठी 0 (एन) ची अतिरिक्त मेमरी स्पेस आवश्यक आहे तर द्रुत क्रमवारीत ओ (लॉग एन) ची जागा आवश्यक आहे.