यदि आप कुछ वाक्यों में वर्णन करते हैं कि किस सिद्धांत पर आदान-प्रदान कार्य छँटाई करते हैं, तो:

जोड़े में ऐरे तत्वों की तुलना की जाती है
यदि बाईं ओर तत्व ^* दाईं ओर के तत्व से बड़ा है, तो तत्वों की अदला-बदली की जाती है
सरणी को हल करने तक 1-2 चरण दोहराएं

^{* - बाईं ओर के तत्व का मतलब है कि तुलना की गई जोड़ी से तत्व, जो कि सरणी के बाएं किनारे के करीब है।} ^{तदनुसार, दाईं ओर का तत्व दाहिने किनारे के करीब है।}

मैं प्रसिद्ध सामग्री को दोहराने के लिए तुरंत माफी मांगता हूं, यह संभावना नहीं है कि लेख में कम से कम एक एल्गोरिदम आपके लिए एक रहस्योद्घाटन होगा। हैबे पर इन छंटनी के बारे में यह पहले से ही कई बार लिखा गया था (मेरे - 1 , 2 , 3 सहित ) और पूछता है कि फिर से इस विषय पर क्यों लौटना है? लेकिन जब से मैंने दुनिया में सभी छंटनी के बारे में लेखों की एक सुसंगत श्रृंखला लिखने का फैसला किया, मुझे एक्सप्रेस संस्करण में भी विनिमय विधियों से गुजरना होगा। निम्नलिखित कक्षाओं पर विचार करते समय, पहले से ही कई नए (और कुछ लोग जानते हैं) एल्गोरिदम होंगे जो अलग-अलग दिलचस्प लेखों के लायक हैं।

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

सिली सॉर्ट :: स्टोगे सॉर्ट

(और यदि आवश्यक हो तो परिवर्तन) तत्वों की तुलना करें।
हम शुरुआत से ही दो-तिहाई सबर्रे लेते हैं और सामान्य एल्गोरिदम को इन 2/3 पर पुनरावर्ती रूप से लागू करते हैं।
हम इसके अंत से दो-तिहाई का हिस्सा लेते हैं और इन 2/3 के लिए सामान्य एल्गोरिदम को पुनरावर्ती रूप से लागू करते हैं।
और फिर से, हम शुरुआत से ही दो-तिहाई सबड्रे लेते हैं और इन 2/3 के लिए सामान्य एल्गोरिदम को पुन: लागू करते हैं।

प्रारंभ में, एक सबरे एक संपूर्ण सरणी है। और फिर पुनरावृत्ति मूल अंश को 2/3 में विभाजित करता है, खंडित खंडों के सिरों पर तुलना / आदान-प्रदान करता है, और अंततः सब कुछ व्यवस्थित करता है।

def stooge_rec(data, i = 0, j = None): if j is None: j = len(data) - 1 if data[j] < data[i]: data[i], data[j] = data[j], data[i] if j - i > 1: t = (j - i + 1) // 3 stooge_rec(data, i, j - t) stooge_rec(data, i + t, j) stooge_rec(data, i, j - t) return data def stooge(data): return stooge_rec(data, 0, len(data) - 1)

यह स्किज़ोफ्रेनिक दिखता है, लेकिन फिर भी यह 100% सही है।

सुस्त क्रमबद्ध :: धीरे क्रमबद्ध

और यहाँ हम पुनरावर्ती रहस्यवाद का निरीक्षण करते हैं:

यदि सबर्रे में एक तत्व होता है, तो हम पुनरावृत्ति को पूरा करते हैं।
यदि एक सबर्रे में दो या अधिक तत्व होते हैं, तो इसे आधा में विभाजित करें।
हम एल्गोरिथ्म को पुन: बाएं आधे हिस्से पर लागू करते हैं।
हम एल्गोरिदम को दाहिने आधे पर पुनरावर्ती रूप से लागू करते हैं।
सबर्रे के सिरों पर तत्वों की तुलना की जाती है (और यदि आवश्यक हो तो बदल दिया जाता है)।
हम अंतिम तत्व के बिना एल्गोरिथ्म को पुन: लागू करते हैं।

प्रारंभ में, एक सबरे पूरे सरणी है। और पुनरावृत्ति को तब तक रोकना, तुलना करना और बदलना जारी रहेगा जब तक कि यह सब कुछ हल न कर दे।

 def slow_rec(data, i, j): if i >= j: return data m = (i + j) // 2 slow_rec(data, i, m) slow_rec(data, m + 1, j) if data[m] > data[j]: data[m], data[j] = data[j], data[m] slow_rec(data, i, j - 1) def slow(data): return slow_rec(data, 0, len(data) - 1)

यह बकवास जैसा दिखता है, लेकिन सरणी का आदेश दिया गया है।

क्यों StoogeSort और SlowSort सही तरीके से काम कर रहे हैं?

एक जिज्ञासु पाठक एक उचित प्रश्न पूछेगा: ये दो एल्गोरिदम काम भी क्यों करते हैं? वे सरल प्रतीत होते हैं, लेकिन यह बहुत स्पष्ट नहीं है कि आप ऐसा कुछ कर सकते हैं।

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

यह स्पष्ट रूप से देखा गया है कि पुनरावृत्ति के सभी स्तरों पर, मैक्सिमा जल्दी से दाईं ओर पलायन करती है। फिर ये मैक्सिमा, जहां उन्हें आवश्यकता होती है, खेल से दूर कर दिया जाता है: एल्गोरिथ्म खुद को कॉल करता है - लेकिन अंतिम तत्व के बिना।

Stooge सॉर्ट में, एक समान जादू होता है:

वास्तव में, जोर भी अधिकतम तत्वों पर रखा गया है। केवल स्लो सॉर्ट उन्हें एक समय में अंत तक ले जाता है, और स्टोगे सॉर्ट सबर्रे के तत्वों के एक तिहाई को धक्का देता है (उनमें से सबसे बड़ा) सेल स्पेस के सबसे सही तीसरे में धकेलता है।

हम एल्गोरिदम की ओर मुड़ते हैं, जहां सब कुछ पहले से ही काफी स्पष्ट है।

गूंगा प्रकार :: मूर्ख प्रकार

बहुत सावधान छँटाई। यह सरणी की शुरुआत से अंत तक जाता है और पड़ोसी तत्वों की तुलना करता है। यदि दो पड़ोसी तत्वों को आपस में बदलना होता है, तो, बस मामले में, सरणी के बहुत शुरुआत में रिटर्न को छांटना और फिर से सभी शुरू होता है।

 def stupid(data): i, size = 1, len(data) while i < size: if data[i - 1] > data[i]: data[i - 1], data[i] = data[i], data[i - 1] i = 1 else: i += 1 return data

सूक्ति प्रकार :: सूक्ति प्रकार

लगभग एक ही बात है, लेकिन एक्सचेंज के दौरान छंटनी सरणी के बहुत शुरुआत में वापस नहीं आती है, लेकिन केवल एक कदम पीछे ले जाती है। यह, यह पता चला है, सब कुछ बाहर करने के लिए पर्याप्त है।

 def gnome(data): i, size = 1, len(data) while i < size: if data[i - 1] <= data[i]: i += 1 else: data[i - 1], data[i] = data[i], data[i - 1] if i > 1: i -= 1 return data

अनुकूलित बौना क्रमबद्ध

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

 def gnome(data): i, j, size = 1, 2, len(data) while i < size: if data[i - 1] <= data[i]: i, j = j, j + 1 else: data[i - 1], data[i] = data[i], data[i - 1] i -= 1 if i == 0: i, j = j, j + 1 return data

बबल सॉर्ट :: बबल सॉर्ट

बेवकूफ और सूक्ति छांटने के विपरीत, जब बुलबुले में तत्वों का आदान-प्रदान होता है, तो कोई रिटर्न नहीं होता है - यह आगे बढ़ना जारी रखता है। अंत तक पहुंचते हुए, सरणी का सबसे बड़ा तत्व बहुत अंत तक चला जाता है।

फिर सॉर्टिंग प्रक्रिया पूरी प्रक्रिया को फिर से दोहराती है, जिसके परिणामस्वरूप वरिष्ठता में दूसरा तत्व अंतिम लेकिन एक स्थान पर है। अगले पुनरावृत्ति पर, तीसरा सबसे बड़ा तत्व अंत से तीसरा है, आदि।

 def bubble(data): changed = True while changed: changed = False for i in range(len(data) - 1): if data[i] > data[i+1]: data[i], data[i+1] = data[i+1], data[i] changed = True return data

अनुकूलित बबल सॉर्ट

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

शेकर सॉर्ट :: शेकर सॉर्ट
(कॉकटेल सॉर्ट :: कॉकटेल सॉर्ट)

एक प्रकार का बुलबुला। पहले पास पर, हमेशा की तरह - अधिकतम से अंत तक धक्का दें। फिर हम तेजी से चारों ओर मोड़ते हैं और न्यूनतम को शुरुआत में धक्का देते हैं। सरणी के क्रमबद्ध सीमांत क्षेत्र प्रत्येक पुनरावृत्ति के बाद आकार में बढ़ जाते हैं।

 def shaker(data): up = range(len(data) - 1) while True: for indices in (up, reversed(up)): swapped = False for i in indices: if data[i] > data[i+1]: data[i], data[i+1] = data[i+1], data[i] swapped = True if not swapped: return data

विषम-समान छँटाई :: विषम-क्रमबद्ध

बाएं से दाएं घूमते समय पड़ोसी तत्वों की जोड़ी की तुलना में पुन: पुनरावृत्तियों। केवल पहले, हम उन जोड़ों की तुलना करते हैं जिनमें पहला तत्व गिनती में विषम है, और दूसरा भी (यानी, पहला और दूसरा, तीसरा और चौथा, पांचवां और छठा, आदि)। और फिर इसके विपरीत - सम + विषम (दूसरे और तीसरे, चौथे और पांचवें, छठे और सातवें, आदि)। इस मामले में, एक समय में एक पुनरावृत्ति पर सरणी के कई बड़े तत्व एक कदम आगे ले जाते हैं (बुलबुले में, पुनरावृत्ति के लिए सबसे बड़ा अंत तक पहुंचता है, लेकिन बाकी बड़े लोग लगभग जगह पर रहते हैं)।

वैसे, यह मूल रूप से ओ (एन) जटिलता के साथ एक समानांतर प्रकार था। "समानांतर सॉर्टिंग" अनुभाग में एल्गोलाब को लागू करना आवश्यक होगा।

 def odd_even(data): n = len(data) isSorted = 0 while isSorted == 0: isSorted = 1 temp = 0 for i in range(1, n - 1, 2): if data[i] > data[i + 1]: data[i], data[i + 1] = data[i + 1], data[i] isSorted = 0 for i in range(0, n - 1, 2): if data[i] > data[i + 1]: data[i], data[i + 1] = data[i + 1], data[i] isSorted = 0 return data

कंघी क्रमबद्ध करें :: संयुक्त प्रकार

बुलबुले का सबसे सफल संशोधन। गति एल्गोरिथ्म तेजी से छँटाई के साथ प्रतिस्पर्धा करता है।

पिछली सभी विविधताओं में, हमने पड़ोसियों की तुलना की। और यहां, पहले, तत्वों के जोड़े पर विचार किया जाता है जो एक दूसरे से अधिकतम दूरी पर होते हैं। प्रत्येक नए पुनरावृत्ति पर, यह दूरी समान रूप से बताती है।

 def comb(data): gap = len(data) swaps = True while gap > 1 or swaps: gap = max(1, int(gap / 1.25)) # minimum gap is 1 swaps = False for i in range(len(data) - gap): j = i + gap if data[i] > data[j]: data[i], data[j] = data[j], data[i] swaps = True return data

त्वरित प्रकार :: त्वरित प्रकार

खैर, सबसे उन्नत एक्सचेंज एल्गोरिदम।

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

यह काम क्यों करता है? बैठक बिंदु के बाईं ओर संदर्भ एक से छोटे या बराबर तत्व हैं। बैठक बिंदु के दाईं ओर संदर्भ से अधिक या बराबर तत्व हैं। अर्थात्, बाईं ओर से कोई भी तत्व दाईं ओर से किसी भी तत्व से कम या बराबर है। इसलिए, बैठक बिंदु पर, सरणी को सुरक्षित रूप से दो उप-वर्गों में विभाजित किया जा सकता है और प्रत्येक उपप्रकार को एक समान तरीके से पुन: व्यवस्थित किया जा सकता है।

 def quick(data): less = [] pivotList = [] more = [] if len(data) <= 1: return data else: pivot = data[0] for i in data: if i < pivot: less.append(i) elif i > pivot: more.append(i) else: pivotList.append(i) less = quick(less) more = quick(more) return less + pivotList + more

के-सॉर्ट :: के-सॉर्ट

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

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

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

शायद मैं लोगों से व्यर्थ बात कर रहा हूं और वास्तव में एल्गोरिथ्म काम कर रहा है? क्या कोई समझा सकता है कि के-सॉर्ट कैसे काम करता है?

युपीडी। धोखाधड़ी के लेखकों को छाँटने के मेरे व्यापक आरोप अप्राप्य हो गए :) उपयोगकर्ता जेट्स ने एल्गोरिथम के छद्म कोड का पता लगा लिया, PHP में एक कार्यशील संस्करण लिखा और मुझे निजी संदेशों में भेजा:

K- तरह PHP में

 function _ksort(&$a,$left,$right){ $ke=$a[$left]; $i=$left; $j=$right+1; $k=$p=$left+1; $temp=false; while($j-$i>=2){ if($ke<=$a[$p]){ if(($p!=$j) && ($j!=($right+1))){ $a[$j]=$a[$p]; } else if($j==($right+1)){ $temp=$a[$p]; } $j--; $p=$j; } else { $a[$i]=$a[$p]; $i++; $k++; $p=$k; } } $a[$i]=$ke; if($temp) $a[$i+1]=$temp; if($left<($i-1)) _ksort($a,$left,$i-1); if($right>($i+1)) _ksort($a,$i+1,$right); }

घोषणा

यह सब एक सिद्धांत था, यह अभ्यास करने के लिए आगे बढ़ने का समय है। अगला लेख विभिन्न डेटा सेटों पर छंटनी एक्सचेंजों का परीक्षण कर रहा है। हम पता लगाएंगे:

क्या छँटाई सबसे खराब है - मूर्खतापूर्ण, नीरस या नीरस?
क्या बबल सॉर्टिंग के लिए अनुकूलन और संशोधन वास्तव में मदद करते हैं?
QuickSort की गति में धीमी एल्गोरिदम आसानी से किस स्थिति में हैं?

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

संदर्भ

एक्सेल-एप्लिकेशन AlgoLab , जिसके साथ आप चरणबद्ध तरीके से इनका विज़ुअलाइज़ेशन देख सकते हैं (और केवल ये नहीं)।

विकी - सिली / स्टोएग , स्लो , ड्वार्फ / गनोम , बबल / बबल , शेकर / शेकर , ऑड / इवन , कॉम्ब / कॉम्ब , फास्ट / क्विक

एक्सचेंज सॉर्ट

सिली सॉर्ट :: स्टोगे सॉर्ट

सुस्त क्रमबद्ध :: धीरे क्रमबद्ध

क्यों StoogeSort और SlowSort सही तरीके से काम कर रहे हैं?

गूंगा प्रकार :: मूर्ख प्रकार

सूक्ति प्रकार :: सूक्ति प्रकार

अनुकूलित बौना क्रमबद्ध

बबल सॉर्ट :: बबल सॉर्ट

अनुकूलित बबल सॉर्ट

शेकर सॉर्ट :: शेकर सॉर्ट
(कॉकटेल सॉर्ट :: कॉकटेल सॉर्ट)

विषम-समान छँटाई :: विषम-क्रमबद्ध

कंघी क्रमबद्ध करें :: संयुक्त प्रकार

त्वरित प्रकार :: त्वरित प्रकार

के-सॉर्ट :: के-सॉर्ट

घोषणा

संदर्भ

श्रृंखला लेख

More articles:

एक्सचेंज सॉर्ट

सिली सॉर्ट :: स्टोगे सॉर्ट

सुस्त क्रमबद्ध :: धीरे क्रमबद्ध

क्यों StoogeSort और SlowSort सही तरीके से काम कर रहे हैं?

गूंगा प्रकार :: मूर्ख प्रकार

सूक्ति प्रकार :: सूक्ति प्रकार

अनुकूलित बौना क्रमबद्ध

बबल सॉर्ट :: बबल सॉर्ट

अनुकूलित बबल सॉर्ट

शेकर सॉर्ट :: शेकर सॉर्ट(कॉकटेल सॉर्ट :: कॉकटेल सॉर्ट)

विषम-समान छँटाई :: विषम-क्रमबद्ध

कंघी क्रमबद्ध करें :: संयुक्त प्रकार

त्वरित प्रकार :: त्वरित प्रकार

के-सॉर्ट :: के-सॉर्ट

घोषणा

संदर्भ

श्रृंखला लेख

More articles:

शेकर सॉर्ट :: शेकर सॉर्ट
(कॉकटेल सॉर्ट :: कॉकटेल सॉर्ट)