प्रोग्रामिंग विधि के रूप में त्वरित सॉर्टिंग

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

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

त्वरित सॉर्टिंग बहुत आम है, आप कर सकते हैंहर जगह मिलें। यह TList.Sort विधि पर आधारित है, जो डेल्फी के सभी संस्करणों (1 को छोड़कर) में मौजूद है, निष्पादित समय के लाइब्रेरी फ़ंक्शन, सी ++ में qsort।

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

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

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

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