पिरामिडल सॉर्टिंग (यह भी एक गुच्छा द्वारा सॉर्ट किया जाता है ) एक क्लासिक एल्गोरिथ्म है जो, शायद, किसी भी प्रोग्रामर को पता होना चाहिए। अच्छा पुराना "पिरामिड" इस तथ्य के लिए उल्लेखनीय है कि, डेटा सेट की परवाह किए बिना, इसमें एक ही समय जटिलता है (इसके अलावा, यह बहुत ही सभ्य है) - ओ ( एन लॉग एन )। उसके लिए कोई बेहतर और पतित मामले नहीं हैं।

विधि के आविष्कार के बाद से (और इस वर्ष एल्गोरिथ्म अपनी अर्ध-शताब्दी वर्षगांठ मना रहा है), वहाँ कई को छँटाई ढेर लगाने की प्रक्रिया को मौलिक रूप से अनुकूलित करने के लिए तैयार किया गया है। टेरानरी पिरामिडल सॉर्टिंग, स्मूथ सॉर्टिंग, कार्टेशियन ट्री सॉर्टिंग - यह नवाचारों की एक अपूर्ण सूची है। उपरोक्त एल्गोरिदम, हालांकि परीक्षण के दौरान वे मूल गति से आगे कुछ 12% और कुछ 25% से आगे हैं, समय की जटिलता के मूल्यांकन में अभी भी O ( n लॉग एन ) के चारों ओर घूमते हैं। इसके अलावा, इन विधियों को बहुत परिष्कृत रूप से लागू किया जाता है।

मैनिटोबा विश्वविद्यालय के एक मामूली कार्यकर्ता , जेसन मॉरिसन ने भी पिरामिडल छँटाई के अपने दृष्टिकोण की पेशकश की। इसके अलावा, कुछ मामलों में विधि गति में O ( n ) तक पहुंचती है।

HeapSort

उन लोगों के लिए जो विषय में नहीं हैं, मैं संक्षेप में बताऊंगा कि पिरामिड की छंटाई कैसे काम करती है।

यदि आप बाइनरी हीप या सिर्फ पिरामिड के रूप में जाना जाता है, तो इसके आधार पर एक सॉर्टिंग ट्री का निर्माण और पुनर्निर्माण करने पर एक सरणी को सॉर्ट किया जा सकता है।

छँटाई का पेड़ क्या है? यह एक ऐसा पेड़ है जिसमें कोई भी माता-पिता अपने वंशजों की तुलना में बड़ा (या छोटा होता है, जिसके आधार पर वह किस दिशा में होता है) होता है।

साधारण पेड़ से छंटाई कैसे करें? बहुत सरल है - आपको वंशज से माता-पिता तक जाने की आवश्यकता है और यदि वंश माता-पिता से बड़ा है, तो स्थानों को बदल दें। यदि ऐसा कोई विनिमय हुआ है, तो जो अभिभावक एक स्तर नीचे चला गया है, उसकी तुलना नीचे के वंशजों के साथ करने की आवश्यकता है - शायद विनिमय का एक कारण भी होगा।

सरणी के अनियोजित भाग को एक छंटाई वाले पेड़ में परिवर्तित करना, परिणामस्वरूप, सबसे बड़ा तत्व "पॉप अप" रूट में। हम अनसुचित सबर्रे की अंतिम कुंजी के साथ अधिकतम विनिमय करते हैं। संरचना एक छंटाई वाले पेड़ के रूप में बंद हो जाएगी, लेकिन एक नैतिक मुआवजे के रूप में, इसका अनसुलझा हिस्सा एक नोड कम हो जाएगा। पूरी प्रक्रिया को इस अनसोल्ड भाग पर फिर से लागू किया जाता है, अर्थात, हम इसे एक सॉर्टिंग ट्री में तब्दील कर देते हैं, जो बाद में अधिकतम पाए गए अंत के क्रमपरिवर्तन के साथ होता है। और इसलिए हम तब तक कार्य करते हैं जब तक कि एक हिस्सा किसी एक तत्व से निचोड़ा न जाए।

दृष्टिकोण, सुनिश्चित होने के लिए, मजाकिया है, लेकिन एक ही समय में, एल्गोरिदम के विशेषज्ञ ढेर के आधार पर छांटने में खामियों का एक पूरा गुच्छा नोट करते हैं, जैसे कि अस्थिरता, नमूनाकरण की यादृच्छिकता, लगभग ऑर्डर किए गए सरणियों के लिए असंवेदनशीलता, आदि। अकल्पित गति ओ ( एन लॉग एन ) भी सभी को भ्रमित करती है। , किसी भी इनपुट डेटा सेट के साथ बिल्कुल छँटाई करके प्रदर्शित किया जाता है।

उत्कृष्ट कंप्यूटर विज्ञान दिमाग विभिन्न मस्तिष्क-असर विचारों ( टर्नरी पिरामिड , लियोनार्डो संख्या , कार्तीय पेड़ ) प्रदान करता है जिसके साथ आप एल्गोरिथ्म में सुधार कर सकते हैं। जेसन मॉरिसन ( J ason Morrison, लेखक के नाम पर छँटाई) ने इसके विपरीत सुझाव दिया - अनुकूलन के लिए यह आवश्यक नहीं है कि इसे जटिल बनाया जाए, बल्कि इसे यथासंभव सरल बनाया जाए ।

JSort

एक कनाडाई वैज्ञानिक इस निष्कर्ष पर पहुंचे हैं कि प्रत्येक तत्व के लिए एक गुच्छा का पुनर्निर्माण करना महंगा है। क्या वास्तव में एन तत्वों की एक सरणी को मौलिक रूप से फावड़ा करना आवश्यक है?

यदि सरणी केवल ढेर (अवरोही और आरोही) के एक जोड़े का निर्माण करने के लिए है, तो यह इसे दोनों दिशाओं में महत्वपूर्ण रूप से आदेश देगा।

पहले आपको एक गैर-बढ़ते ढेर का निर्माण करने की आवश्यकता है। नतीजतन, छोटे तत्व पिरामिड के शीर्ष नोड्स पर तैरते हैं (जो सरणी के बाईं ओर आधे के अनुरूप होंगे), सबसे छोटा तत्व आम तौर पर जड़ में होगा। उच्चतर तत्व छंटाई वाले पेड़ में होते हैं, और अधिक क्रमबद्ध रूप से सरणी का संबंधित भाग होगा। पेड़ की पत्तियों के करीब स्थित तत्व (सरणी का दूसरा भाग उनके अनुरूप होगा) में कम क्रम दिखाई देगा, क्योंकि उनकी एक-दूसरे के साथ तुलना नहीं की गई थी, लेकिन बस अपने माता-पिता के आंदोलन के परिणामस्वरूप पिछवाड़े में धकेल दिया गया था।

सरणी के दाईं ओर सापेक्ष क्रम को पुनर्स्थापित करने के लिए, आपको पहले के सभी विपरीत में फिर से एक गुच्छा बनाना चाहिए। सबसे पहले, यह ढेर गैर-घटाना चाहिए (हम अब मूल्य से बड़ी कुंजी से निपटना चाहते हैं)। दूसरे, यह सरणी के लिए "दर्पण" होना चाहिए, अर्थात, इसकी जड़ पहले या अंतिम तत्व के अनुरूप नहीं होनी चाहिए, और पेड़ को अंत से शुरुआत तक सरणी को छाँटकर बनाया जाना चाहिए।

इस तरह के ट्विन पिरामिड बनाने के बाद, हमें मोटे तौर पर ऑर्डर किए गए एरे मिलते हैं। आवेषण द्वारा छंटनी मामले को पूरा करती है। इस एल्गोरिथ्म में O ( n ² ) की बहुत मामूली औसत जटिलता है, लेकिन यह उन सरणियों पर अद्भुत काम करता है जो लगभग पहले से ही हल हैं। उन्हें आवेषण के साथ छंटनी पागल की तरह क्लिक करता है।

समय की जटिलता

आइए सबसे अनुकूल परिदृश्य में मूल्यांकन करने का प्रयास करें। एक बार का पिरामिड निर्माण O ( n ) है। हम ढेर पर दो डालते हैं, इसलिए हमें ओ ( 2 एन ) मिलता है। आवेषण द्वारा लगभग एक क्रमबद्ध सरणी छँटाई एक रिकॉर्ड O ( n ) के लिए हो सकती है। समग्र जटिलता O ( 3n ) है, जो O ( n ) के समान है।

हालांकि, व्यवहार में, सब कुछ अधिक विनम्र दिखता है। उदाहरण के लिए, 1 से 30 तक की संख्या वाले ऐसे अनसोल्ड सरणी को लें:

आइए एक नियमित गैर-बढ़ते ढेर का निर्माण करें:

मासिफ के पहले तीसरे ने काफी महान रूप ले लिया है, बीच में - जो जंगल में जला हुआ लकड़ी है, मासिफ का अंत भी अभी तक प्रभावशाली नहीं है।

अब हम एक "दर्पण" गैर-घटते हुए ढेर का निर्माण करते हैं:

सरणी का अंत विशेष रूप से पूर्व-निर्धारित है। बीच में आदेशों की कुछ अशिष्टताएं हैं, लेकिन यह बाएं और दाएं क्षेत्रों के रूप में ग्लैमरस नहीं दिखता है। सिद्धांत रूप में, आवेषण द्वारा छांटे गए इसे खिलाने के लिए सरणी पर्याप्त परिपक्व होती है।

20 के मान के साथ कुंजी को नोट करें । यह तत्व सरणी के पहले तीसरे भाग में क्यों अटक गया है? यह कोई सौभाग्य नहीं था - "मिरर" को गैर-घटते हुए ढेर बनाने से पहले, शाखा के सभी माता-पिता अधिक महत्वपूर्ण हो गए (अब जड़ में यह 17 है, लेकिन यह कुंजी पेड़ के बाएं आधे हिस्से में डूब जाएगी और 30 को रास्ता देगी)। इसलिए, पिरामिड में वह कम से कम एक पायदान ऊपर उठने के लिए किस्मत में नहीं है।

जितनी अधिक बार सरणी होगी, उतनी बार पतित नोड्स उत्पन्न होंगे। तो, लंबी सरणियों के मध्य पट्टी में, आवेषण द्वारा छंटाई के लिए कड़ी मेहनत करनी होगी। इसे खिलाया जाने वाला सरणी लगभग हल नहीं किया जाएगा, बल्कि लगभग छांटा जाएगा। बहुत लंबी सूचियों पर, प्रविष्टि सॉर्ट की समय जटिलता, निश्चित रूप से, इसकी औसत / सबसे खराब O ( n ² ) नहीं होगी, लेकिन यह O ( n ) से भी दूर होगी।

वैसे

एक अन्य समान नाम के साथ एक छँटाई एल्गोरिथ्म है - जे सॉर्ट , जो जॉन कोहेन द्वारा विकसित किया गया था। यह एक हाइब्रिड एल्गोरिथ्म भी है जिसका उपयोग दोगुनी लिंक्ड सूचियों को संसाधित करने के लिए किया जाता है। स्ट्रैंड सॉर्ट और शफल प्रकार को जोड़ती है। लेकिन वह एक और कहानी है।

एल्गोरिदम के लक्षण

नाम	Jsort (J- सॉर्ट)
लेखक	जेसन मॉरिसन
वर्ग	संकर छँटाई (ढेर + आवेषण)
स्थिरता	अस्थिर
तुलना	वहाँ है
समय की जटिलता	सबसे अच्छा	ओ (एन)
	मध्यम	?
	सबसे खराब	ओ (एन ² )
स्मृति कठिनाई	केवल	ओ (एन)
स्मृति कठिनाई	अतिरिक्त डेटा	ओ (1)

इसके साथ ही

जावा में ढेर छाँट

/** *      *   - JWJ Williams  RW Floyd * * SortAlgorithm.java, Thu Oct 27 10:32:35 1994 * * @author Jason Harrison@cs.ubc.ca * @version 1.0, 23 Jun 1995 */ class HeapSortAlgorithm extends SortAlgorithm { //  void sort(int a[]) throws Exception { int N = a.length; //     //    . for (int k = N / 2; k > 0; k--) downheap(a, k, N); //   //    do { //    ... int T = a[0]; a[0] = a[N - 1]; a[N - 1] = T; //...     //    N = N - 1; downheap(a, 1, N); } while (N > 1); //   } //         void downheap(int a[], int k, int N) throws Exception { //   //  int T = a[k - 1]; //     while (k <= N / 2) { int j = k + k;//  //   , //     //     if ((j < N) && (a[j - 1] < a[j])) j++; //   ( )  ... if (T >= a[j - 1]) { //...         break; } else { //    ... //...       a[k - 1] = a[j - 1]; k = j; } } //         //(    ,     ) a[k - 1] = T; } }

हीप सॉर्ट एनीमेशन का YouTube संस्करण

जावा में Jort

 /** *    J- (JSort). *   -   (Jason Morrison) * <http://www.scs.carleton.ca/~morrison> * * JSortAlgorithm.java * *   -   * @author Patrick Morin */ class JSortAlgorithm extends SortAlgorithm { //     //       void reheap (int a[], int length, int i) throws Exception { //      boolean done = false; //   //      int T = a[i]; int parent = i; int child = 2 * (i + 1) - 1; // ,     //     (  -   ) //        //    -   . while ((child < length) && (!done)) { //      if (child < length - 1) { //        if (a[child] >= a[child + 1]) { child += 1; } } //  ? if (T < a[child]) { //        done = true; //       . //     //          } else { a[parent] = a[child]; parent = child; child = 2 * (parent + 1) - 1; } } //,     //     //(      ) a[parent] = T; } //     //       void invreheap (int a[], int length, int i) throws Exception { //      boolean done = false; //   //      int T = a[length - 1 - i]; int parent = i; int child = 2 * (i + 1) - 1; // ,     //     (  -  ) //        //    -   . while ((child < length) && (!done)) { //      if (child < length - 1) { //        if (a[length - 1 - child] <= a[length - 1 - (child + 1)]) { child += 1; } } //  ? if (T > a[length - 1 - child]) { //        done = true; } else { //       . //     //          a[length - 1 - parent] = a[length - 1 - child]; parent = child; child = 2 * (parent + 1) - 1; } } //,     //     //(      ) a[length - 1 - parent] = T; } //   void sort(int a[]) throws Exception { //   //     //    for (int i = a.length-1; i >= 0; i--) reheap (a, a.length, i); //   //     //    for (int i = a.length - 1; i >= 0; i--) invreheap (a, a.length, i); //   //  for (int j = 1; j < a.length; j++) { int T = a[j]; int i = j - 1; while (i >= 0 && a[i] > T) { a[i + 1] = a[i]; i -= 1; } a[i + 1] = T; } } }

Jsort एनीमेशन का YouTube संस्करण

संदर्भ

विकिपीडिया पर Jsort

यूनिवर्सिटी ऑफ मैनिटोबा वेबसाइट पर जेसन मॉरिसन का पेज

जेसन मॉरिसन लिंक्डइन पेज

जे छँटनी