एक प्रोग्रामिंग पद्धति के रूप में quicksort

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

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

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

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

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

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

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