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


पर्सी डियाकोनिस , जिन्होंने सॉलिटेयर सॉर्टिंग के साथ-साथ अध्ययन किया था, का मानना ​​है कि यह कार्ड के डेक को मैन्युअल रूप से व्यवस्थित करने का सबसे तेज़ तरीका है।

इसलिए, यदि एक सम्मानित गणितज्ञ (और एक अनुभवी कार्ड जादूगर) झूठ नहीं बोलता है, तो एल्गोरिथम के व्यावहारिक मूल्य के साथ, सब कुछ क्रम में है।

अब अपने हाथ देखो।

चरण 1. ढेर में बिछाना

तो, डेक से कीड़े ले लो। वे तेरह यादृच्छिक तत्वों की एक सरणी का प्रतिनिधित्व करेंगे।



हमें कई ढेरों में कार्ड को विघटित करने की आवश्यकता है, ताकि प्रत्येक ढेर में कार्ड एक क्रमबद्ध क्रम हो।

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

पहला कार्ड पहले ढेर की शुरुआत है।



हम कार्ड को बदले में इस स्टैक में स्थानांतरित करते हैं, जब तक कि अगला हस्तांतरित कार्ड ढेर में शीर्ष से छोटा न हो।

इसके अलावा, प्रत्येक स्टैक एक स्टैक है - हम पूरे स्टैक के साथ काम नहीं करते हैं, लेकिन इसमें केवल शीर्ष कार्ड के साथ, जो पिछले डाल दिया गया था।



यदि वर्तमान कार्ड स्टैक में न्यूनतम से अधिक है, तो आपको एक नया ढेर बनाना होगा, वर्तमान कार्ड एक नया स्टैक खोलता है।



ढेर का क्रम महत्वपूर्ण है! यदि उनकी संख्या पहले से ही एक से अधिक है, तो हम अगले कार्ड को अंतिम ढेर में नहीं, बल्कि बाईं ओर के ढेर में डालते हैं, जिसमें हम इसे डाल सकते हैं।

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



सात और छह को पहले ढेर में नहीं जोड़ा जा सकता (वे इसमें शीर्ष कार्ड से बड़े हैं), लेकिन उनके पास अभी भी दूसरे ढेर में जगह है।



ऐस एक नया ढेर शुरू करता है। शेष ट्रिफ़ल अलग-अलग ट्रे में गिरता है, यह इस बात पर निर्भर करता है कि बाईं ओर कितना ढेर था जहां इसे डाला जा सकता है।



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

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

चरण 2. नीचे की पंक्ति

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



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

भविष्य में, छँटाई के अंत तक, हमें उन सभी कार्डों में कोई दिलचस्पी नहीं है जो टेबल पर रखे गए हैं। केवल इन की जरूरत है:

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

नीचे की पंक्ति में, हम कार्ड को कार्ड के बाएं से दाएं क्रमबद्ध करते हैं। सबसे बाईं ओर वर्तमान न्यूनतम है, हम इसे मूल शीर्ष पंक्ति में लौटाते हैं। उसी समय, हर बार जब हम आधार को दूसरे कार्ड पर लौटाते हैं, तो इसके स्थान पर दूसरे को रखना आवश्यक है। कहां से लाएं? वर्तमान नक्शे के ऊपर और उसके बायीं ओर बवासीर में से - उपलब्ध कार्डों के बीच, एक न्यूनतम का चयन किया जाता है जो नीचे पंक्ति में वर्तमान बाएं कार्ड के रिक्त स्थान पर जाता है, और वहां से मुख्य सरणी में जाता है।

सरणी में दो तुरंत लौटते हैं। रिक्त स्थान ट्रिपल द्वारा लिया जाता है (हम इसे पहले ढेर से नीचे की पंक्ति में स्थानांतरित करते हैं), और नीचे की पंक्ति से ट्रिपल एक न्यूनतम के रूप में मुख्य सरणी में जाता है। पहले दो बवासीर में, न्यूनतम फिर से खोजा जाता है - यह चार है - जो घर भी जाता है। पांच वर्तमान न्यूनतम हो जाता है, आदि।



कतार के आरोही क्रम और ढेर के अवरोही क्रम के साथ काम का संयोजन बहुत जल्दी हमें सभी तत्वों को न्यूनतम से अधिकतम तक पहुंच जाता है। सामान्य तौर पर ऐसा कुछ।

इस प्रक्रिया का एनीमेशन।



यदि आप उपरोक्त सभी का अजगर में अनुवाद करते हैं, तो आपको यह मिलता है:

from functools import total_ordering from bisect import bisect_left from heapq import merge @total_ordering class Pile(list): def __lt__(self, other): return self[-1] < other[-1] def __eq__(self, other): return self[-1] == other[-1] def patience_sort(n): piles = [] # sort into piles for x in n: new_pile = Pile([x]) i = bisect_left(piles, new_pile) if i != len(piles): piles[i].append(x) else: piles.append(new_pile) # use a heap-based merge to merge piles efficiently n[:] = merge(*[reversed(pile) for pile in piles]) 

संदर्भ

धैर्य छँटाई ( Google- अनुवाद )

धैर्य सॉर्टिंग स्रोत

प्रिंसटन सीएस: सबसे लंबे समय तक बढ़ने वाली परवर्ती

बवासीर छांटने वाले धैर्य का संयोजन ( Google-Translate )

विकी एब्सट्रैक्ट: रोगी छँटाई

शब्द संरेखित ( Google- अनुवाद )

श्रृंखला लेख:

• एक्सेल आवेदन AlgoLab.xlsm
• एक्सचेंज सॉर्ट
• निवेशन शॉर्ट्स
  • लाइब्रेरियन क्रमबद्ध
  • सॉलिटेयर सॉर्ट
  • सॉर्ट "हनोई का टॉवर"
  • युवा टेबल छँटाई
  • इनवर्ट सॉर्ट करें
  • क्रमबद्ध तुलना डालें
• चयन के आधार पर छाँटें
• मर्ज करना
• वितरण के आधार पर छाँटें
• हाइब्रिड सॉर्टिंग

AlgoLab एप्लिकेशन में, यह सॉर्टिंग अब सक्रिय है। उसी समय, विज़ुअलाइज़ेशन दो मोड में संभव है: नक्शे के रूप में (डिफ़ॉल्ट मोड) और बस संख्याओं के रूप में। हालांकि, कार्ड शैली के लिए, यह आवश्यक है कि सरणी में अधिकतम और न्यूनतम तत्वों के बीच का अंतर 54 से कम हो (डेक में कार्ड की संख्या, जिसमें दो जोकर भी शामिल हैं)। यदि यह स्थिति पूरी नहीं होती है या कार्ड मोड पूरी तरह से बंद हो जाता है (इसके लिए, आपको सेल के लिए 0 को सॉर्ट नाम के साथ टिप्पणी में लिखना होगा), तो दृश्य सुस्त अंकों के रूप में होगा।

सूट वरीयता वरिष्ठता के क्रम में माना जाता है: चोटियों <क्लब <tambourines <दिल।


अर्थात्, टैमबोराइन के टैम्बोरिन सूट का कोई भी कार्ड क्लब सूट के किसी भी कार्ड से बड़ा होता है, हार्ट सूट का कोई भी कार्ड किसी भी चोटी के सूट के कार्ड से बड़ा होता है, आदि। यदि हम संख्याओं के साथ एक सादृश्य आकर्षित करते हैं, तो चोटियां 0 से 9 तक हैं, क्लब 10 से 19 तक हैं, हीरे 20 से 29 तक हैं, दिल 30 से 39 तक हैं (हां, ज़ाहिर है, सूट के अंदर कार्ड की संख्या दस नहीं है, लेकिन आप समझते हैं कि इसका क्या मतलब है)। सूट के भीतर वरिष्ठता के लिए , यह साधारण होगा: ड्यूस से ऐस तक। आप उन जोकरों को भी ले सकते हैं जो अन्य सभी कार्डों से पुराने हैं। इस मामले में, लाल जोकर काले रंग की तुलना में अधिक वजनदार है।

यह लेख एक पेशेवर वेब विकास कंपनी EDISON सॉफ्टवेयर के समर्थन से लिखा गया था जिसने हाल ही में अपनी वेबसाइट को फिर से डिज़ाइन किया।