क्विकसॉर्ट
क्विकसॉर्ट सबसे ज़्यादा इस्तेमाल होने वाले सॉर्टिंग एल्गोरिदम में से एक है। यह एक पिवट चुनता है, सूची को पिवट से छोटे मानों और बाक़ी मानों में बाँटता है, और दोनों तरफ़ को इसी तरह सॉर्ट करता है। यह व्यवहार में तेज़ है और इसे अतिरिक्त सूची की ज़रूरत नहीं होती, लेकिन यह कितना तेज़ है, यह पिवट पर निर्भर करता है।
मूल विचार
एक मान को पिवट चुनें। सूची को इस तरह फिर से जमाएँ कि पिवट से छोटा हर मान उसके पहले और बाक़ी हर मान उसके बाद आए। इस तरह फिर से जमाने को विभाजन कहते हैं, और इससे पिवट ठीक उसी जगह पहुँच जाता है जहाँ उसे सॉर्ट की हुई सूची में होना चाहिए। अब दोनों तरफ़ अलग-अलग समस्याएँ हैं: हर एक को क्विकसॉर्ट से सॉर्ट करें। जिस तरफ़ एक ही मान हो या कोई मान न हो, वह पहले से सॉर्ट है।
विभाजन, चरण-दर-चरण
ऐप Lomuto विभाजन का इस्तेमाल करता है। पिवट को हिस्से के अंत में ले जाया जाता है। एक निशान शुरुआत से चलता है: उसके पहले का हर मान पिवट से छोटा होता है। बाक़ी हर मान की तुलना पिवट से होती है; अगर वह छोटा है, तो वह अदल-बदलकर निशान पर आता है और निशान एक जगह आगे बढ़ता है। अंत में पिवट अदल-बदलकर निशान पर आता है। 5, 1, 4, 2, 8 लें और आख़िरी मान को पिवट बनाएँ: चारों मान 8 से छोटे हैं, इसलिए 8 अंत में ही रहता है। हिस्सा 5, 1, 4, 2 का विभाजन 2 के चारों ओर होता है, जिससे 1, 2, 4, 5 बनता है, और 4, 5 का 5 के चारों ओर। कुल 8 तुलनाएँ, 2 अदला-बदली और 3 विभाजन।
अच्छे और बुरे पिवट
अगर हर पिवट बीच में आता, तो हर विभाजन समस्या को आधा कर देता, और सॉर्ट में लगभग n log₂ n तुलनाएँ लगतीं। रैंडम सूची पर पिवट शायद ही कभी एकदम सही होते हैं, पर आमतौर पर काफ़ी अच्छे होते हैं: 40 रैंडम मानों के लिए ऐप लगभग 190 तुलनाएँ गिनता है। सबसे ख़राब स्थिति तब आती है जब पिवट हमेशा सबसे छोटा या सबसे बड़ा मान हो। आख़िरी मान को पिवट बनाने पर पहले से सॉर्ट की हुई या उल्टी सूची में ठीक यही होता है: हर विभाजन सिर्फ़ पिवट को हटाता है, और सॉर्ट में n(n − 1)/2 तुलनाएँ लगती हैं, 40 मानों के लिए 780।
पिवट चुनना
रैंडम पिवट किसी भी इनपुट के लिए सबसे ख़राब स्थिति को बेहद असंभावित बना देता है, क्योंकि कोई ख़ास क्रम उसे धोखा नहीं दे सकता। तीन का मीडियन, यानी पहले, बीच वाले और आख़िरी एलिमेंट में से बीच का मान, सस्ता है और सॉर्ट की हुई व उल्टी सूचियों को अच्छी तरह संभालता है। ऐप में सॉर्ट की हुई सूची पर दोनों आज़माएँ, तुलनाएँ 780 से घटकर लगभग 150 रह जाती हैं। बहुत सारे बराबर मान एक अलग समस्या हैं: वे सब पिवट की एक ही तरफ़ जाते हैं। तीन-तरफ़ा विभाजन, जो पिवट के बराबर मानों को बीच के हिस्से में रखता है, इसे ठीक करता है।
इतिहास और उपयोग
Tony Hoare ने 1959 में क्विकसॉर्ट का आविष्कार किया और 1961 में इसे प्रकाशित किया। उनका अपना विभाजन दोनों सिरों से स्कैन करता है और कम अदला-बदली करता है; यहाँ दिखाया गया सरल Lomuto संस्करण पाठ्यपुस्तकों के ज़रिए लोकप्रिय हुआ। क्विकसॉर्ट इन-प्लेस सॉर्ट करता है और इसका अंदरूनी लूप बहुत छोटा है, इसलिए व्यवहार में यह आमतौर पर मर्ज सॉर्ट से तेज़ होता है, हालाँकि यह स्थिर नहीं है। C++ की स्टैंडर्ड लाइब्रेरी के पीछे का सॉर्ट, introsort, क्विकसॉर्ट चलाता है और विभाजन बहुत असमान होने पर हीप सॉर्ट पर चला जाता है, ताकि उसकी सबसे ख़राब स्थिति भी n log n रहे।
ख़ुद आज़माएँ
ऐप खोलें और आगे दबाएँ। विभाजित हो रहा हिस्सा छायांकित होता है, पिवट का अपना रंग होता है, और डैश वाली रेखा बाएँ हिस्से, यानी पिवट से छोटे मानों, का अंत दिखाती है। हर पिवट अपनी अंतिम जगह पर पहुँचते ही हरा हो जाता है। सॉर्ट की हुई सूची और आख़िरी मान को पिवट चुनें, फिर तीन के मीडियन पर जाएँ, और काउंटरों की तुलना करें।
अक्सर पूछे जाने वाले प्रश्न
क्विकसॉर्ट की टाइम कॉम्प्लेक्सिटी क्या है?
औसतन और अच्छे पिवट के साथ O(n log n), सबसे ख़राब स्थिति में O(n²)। यह इन-प्लेस सॉर्ट करता है; छोटी तरफ़ को पहले सॉर्ट करने पर रिकर्शन को O(log n) अतिरिक्त मेमोरी चाहिए।
Lomuto और Hoare विभाजन में क्या अंतर है?
Lomuto एक निशान रखता है और बाएँ से दाएँ स्कैन करता है, जिसे समझना आसान है और यही यह ऐप दिखाता है। Hoare दोनों सिरों से एक-दूसरे की ओर स्कैन करता है और ग़लत तरफ़ वाले जोड़ों की अदला-बदली करता है, जिससे औसतन लगभग तीन गुना कम अदला-बदली होती है।
बहुत सारे मान बराबर हों तो क्विकसॉर्ट धीमा क्यों होता है?
पिवट के बराबर सभी मान एक ही तरफ़ जाते हैं, इसलिए कम अलग मानों वाली सूची असमान रूप से बँटती है, और सभी बराबर मानों वाली सूची सबसे ख़राब स्थिति जितनी बुरी होती है। तीन-तरफ़ा विभाजन, जो पिवट के बराबर मानों को बीच में इकट्ठा करता है, इससे बचाता है।
क्या क्विकसॉर्ट स्थिर (stable) है?
नहीं। विभाजन के दौरान अदला-बदली मानों को दूर तक ले जाती है, इसलिए बराबर मानों का क्रम बदल सकता है।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
क्विकसॉर्ट आज़माएँ