पसंद के अनुसार छंटनी का विचार क्या है?

एक अनारक्षित उपश्रेणी में, एक स्थानीय अधिकतम (न्यूनतम) मांगा जाता है।
पाया गया अधिकतम (न्यूनतम) सबअरे में अंतिम (पहले) तत्व के साथ स्थान बदलता है।
यदि अनसुनी सबरेज़ सरणी में रहती हैं, तो बिंदु 1 देखें।

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

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

चयन प्रकार

सरल और सरल - हम अधिकतम तत्व की तलाश में सरणी के माध्यम से जाते हैं। पाया अधिकतम अंतिम तत्व के साथ जुड़ा हुआ है। ऐरे का अनसर्टेड पार्ट एक एलिमेंट से घटाया गया (इसमें अंतिम एलीमेंट को शामिल नहीं किया गया जहाँ हमने अधिकतम पाया गया)। हम इस अनसोल्ड भाग में समान क्रियाओं को लागू करते हैं - हम अधिकतम पाते हैं और इसे ऐरो के अनसोल्ड पार्ट में अंतिम स्थान पर रखते हैं। और इसलिए हम तब तक जारी रखते हैं जब तक कि सरणी का अनसुलझा हिस्सा एक तत्व तक कम नहीं हो जाता।

def selection(data): for i, e in enumerate(data): mn = min(range(i, len(data)), key=data.__getitem__) data[i], data[mn] = data[mn], e return data

एक साधारण विकल्प के साथ छंटनी एक कठिन दोहरी खोज है। क्या इसे सुधारा जा सकता है? आइए कुछ संशोधनों को देखें।

डबल चयन प्रकार :: डबल चयन प्रकार

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

पहली नज़र में, ऐसा लगता है कि यह एल्गोरिथ्म को 2 गुना बढ़ाता है - प्रत्येक पास के बाद, एक से नहीं बल्कि एक तरफ से दो के बिना, सबस्क्राइर्ड सबर्रे को कम किया जाता है। लेकिन एक ही समय में, तुलना की संख्या 2 गुना बढ़ गई, और स्वैप की संख्या अपरिवर्तित रही। डबल चयन केवल एल्गोरिथ्म की गति को थोड़ा बढ़ाता है, और कुछ भाषाओं में यह किसी कारण से धीमी गति से भी काम करता है।

प्रविष्टि छँटाई से पसंद के अनुसार छँटाई के बीच का अंतर

ऐसा प्रतीत हो सकता है कि आवेषण द्वारा चयन और छंटाई द्वारा छंटनी एक और एक ही बात है, एल्गोरिदम का एक सामान्य वर्ग। खैर, या आवेषण द्वारा छांटना एक प्रकार का छांटना है। या चुनाव द्वारा छांटना आवेषण द्वारा छँटाई का एक विशेष मामला है। और वहां और वहां, हम तत्वों को निकालने के लिए सरणी के अनसरेस्टेड हिस्से से मुड़ते हैं और उन्हें सॉर्ट किए गए क्षेत्र पर पुनर्निर्देशित करते हैं।

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

यह दोनों वर्गों के एल्गोरिदम को उनके सार और उपयोग की गई विधियों में एक दूसरे से पूरी तरह से अलग बनाता है।

बिंगो सॉर्ट :: बिंगो सॉर्ट

छँटाई विकल्पों की एक दिलचस्प विशेषता डेटा की प्रकृति की गति की स्वतंत्रता है जो छँटाई जा रही है।

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

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

लेकिन सिद्धांत रूप में, आप एल्गोरिथ्म को नियंत्रित और संशोधित कर सकते हैं ताकि यह कुछ डेटा सेटों के साथ तेजी से काम करे। उदाहरण के लिए, बिंगो सॉर्टिंग को ध्यान में रखा जाता है यदि सरणी में दोहराए जाने वाले तत्व होते हैं।

यहां चाल यह है कि अव्यवस्थित भाग में न केवल अधिकतम तत्व को याद किया जाता है, बल्कि अगले पुनरावृत्ति के लिए अधिकतम भी निर्धारित किया जाता है। यह बार-बार मैक्सिमा के लिए उन्हें हर बार फिर से नहीं खोजने की अनुमति देता है, लेकिन जैसे ही यह अधिकतम एक बार फिर से सरणी में सामने आता है, उन्हें अपने स्थान पर रखने के लिए।

एल्गोरिथम जटिलता समान रही। लेकिन अगर सरणी में दोहराए जाने वाले नंबर शामिल हैं, तो बिंगो छँटाई नियमित रूप से छँटाई की तुलना में दस गुना तेजी से सामना करेगी।

 # - def bingo(data): #  . max = len(data) - 1 nextValue = data[max] for i in range(max - 1, -1, -1): if data[i] > nextValue: nextValue = data[i] while max and data[max] == nextValue: max -= 1 #  . while max: value = nextValue nextValue = data[max] for i in range(max - 1, -1, -1): if data[i] == value: data[i], data[max] = data[max], data[i] max -= 1 elif data[i] > nextValue: nextValue = data[i] while max and data[max] == nextValue: max -= 1 return data

चक्र प्रकार :: चक्र क्रमबद्ध

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

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

अन्य प्रकार में, पसंद से, हम उन्हें अंतिम / प्रथम स्थान पर रखने के लिए अधिकतम / न्यूनतम की तलाश करते हैं। चक्र क्रम में, यह पता चलता है कि कम से कम सबर्रे में पहला स्थान स्थित है, जैसा कि इस बात की प्रक्रिया में था कि सरणी के बीच में कई अन्य तत्व उनके सही स्थानों पर कैसे रखे जाते हैं।

और यहां, एल्गोरिथम जटिलता भी ओ ( एन ² ) के भीतर बनी हुई है। व्यवहार में, चक्रीय छंटाई नियमित रूप से छँटाई की तुलना में कई गुना धीमी गति से काम करती है, क्योंकि आपको सरणी के चारों ओर अधिक बार चलना होगा और अधिक बार तुलना करनी होगी। यह पुनर्लेखन की सबसे छोटी संभव संख्या के लिए मूल्य है।

 #   def cycle(data): #        for cycleStart in range(0, len(data) - 1): value = data[cycleStart] # ,    pos = cycleStart for i in range(cycleStart + 1, len(data)): if data[i] < value: pos += 1 #      ,   #      if pos == cycleStart: continue #   ,     #        while value == data[pos]: pos += 1 data[pos], value = value, data[pos] #      , #         while pos != cycleStart: # ,    pos = cycleStart for i in range(cycleStart + 1, len(data)): if data[i] < value: pos += 1 #      #      while value == data[pos]: pos += 1 data[pos], value = value, data[pos] return data

पैनकेक सॉर्ट करें

एक एल्गोरिथ्म जिसने जीवन के सभी स्तरों पर महारत हासिल की है - बैक्टीरिया से बिल गेट्स तक ।

सबसे सरल मामले में, हम सरणी के गैर-सॉर्ट किए गए भाग में अधिकतम तत्व की तलाश कर रहे हैं। जब अधिकतम पाया जाता है, तो हम दो तेज मोड़ बनाते हैं। सबसे पहले, हम तत्वों की श्रृंखला को चालू करते हैं ताकि अधिकतम विपरीत छोर पर हो। फिर हम पूरे अनारक्षित सबरे को पलट देते हैं, जिसके परिणामस्वरूप अधिकतम जगह गिर जाती है।

इस तरह के कॉर्डिलेट्स, आम तौर पर ओ ( एन ³ ) में एल्गोरिथम जटिलता का नेतृत्व करते हैं। ये प्रशिक्षित सिलिअल्स एक गिर गए झपट्टा में लड़खड़ा रहे हैं (इसलिए, उनके निष्पादन में जटिलता ओ ( एन ² ) है), और जब प्रोग्रामिंग करते हैं, तो सरणी के हिस्से का उलटा एक अतिरिक्त चक्र होता है।

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

 #   def pancake(data): if len(data) > 1: for size in range(len(data), 1, -1): #      maxindex = max(range(size), key = data.__getitem__) if maxindex + 1 != size: #    ,    if maxindex != 0: #  , #     data[:maxindex+1] = reversed(data[:maxindex+1]) #    , #      data[:size] = reversed(data[:size]) return data

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

संदर्भ

चयन / चक्र , पैनकेक / पेनकेक्स

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

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

आज के बिंगो, साइकिल और पैनकेक को एल्गोलैब ऐप में जोड़ा गया है। उत्तरार्द्ध में, पेनकेक्स के ड्राइंग के संबंध में, एक प्रतिबंध रखा गया है - सरणी में तत्वों का मान 1 से 5 तक होना चाहिए। आप निश्चित रूप से, अधिक डाल सकते हैं, लेकिन मैक्रोज़ यादृच्छिक रूप से इस सीमा से संख्या लेंगे।

चयन के आधार पर छाँटें