क्विक सॉर्ट क्या है?
क्विक सॉर्ट एक क्रमबद्ध करने की विधि है। यह एक पिवट चुनती है, उसके आसपास मानों को बाँटती है और फिर बने हुए हिस्सों को इसी तरह क्रम में लगाती है।
पिवट के आसपास बाँटना क्यों ज़रूरी है?
मान लें सूची [6, 2, 8, 3, 1] है और पिवट 6 है। तीन मान उससे छोटे हैं, इसलिए शून्य से गिनने पर 6 का स्थान इंडेक्स 3 है। पर केवल 6 को वहाँ रख देने से [3, 2, 8, 6, 1] मिल सकता है। इसमें 8 बाईं ओर और 1 दाईं ओर रह गया है।
[2, 3, 1, 6, 8] एक सही विभाजन है: 6 से छोटे मान बाईं ओर हैं और बड़ा मान दाईं ओर है। दोनों हिस्सों को अभी अलग से क्रम में लगाना होगा।
लोमुटो विभाजन कैसे काम करता है?
इस विधि में वर्तमान हिस्से का अंतिम मान पिवट है। इंडेक्स i उस स्थान को दिखाता है जहाँ अगला छोटा मान रखा जाएगा। हर मान को पिवट से तुलना करके, छोटा होने पर i वाले मान से बदलें और i आगे बढ़ाएँ। अंत में पिवट को i वाले मान से बदलें।
उदाहरण के लिए [5, 3, 1, 8, 7] में पिवट 7 है। 5, 3 और 1 छोटे हैं, इसलिए i उनके बाद पहुँचता है। 8 छोटा नहीं है। अंत में 7 और 8 बदलते हैं और [5, 3, 1, 7, 8] मिलता है। बराबर मान इस संस्करण में पिवट के दाईं ओर रहते हैं।
चरणों के साथ अभ्यास करें
उदाहरण बदलने के लिए उसके नाम के पास वाले तीर दबाएँ। चरण वाले बटन आपको एक उदाहरण में आगे या पीछे ले जाते हैं। देखें कि j मानों को एक-एक करके जाँचता है, जबकि i पिवट से छोटे अगले मान की जगह दिखाता है।
अभ्यास में वर्तमान मान की तुलना पिवट से करें, तय करें कि अदला-बदली करनी है या नहीं, और इंडेक्स खुद आगे बढ़ाएँ। हर क्रिया तालिका में जुड़ती है। अपना काम देखने के बाद सही चरणों से उसकी तुलना करें। तुलना लोड हो रही है…
पूरी सूची कैसे क्रम में आती है?
- वर्तमान हिस्से में पिवट चुनें।
- मानों को पिवट के आसपास बाँटें।
- दोनों हिस्सों पर यही प्रक्रिया दोहराएँ।
खाली या एक मान वाला हिस्सा पहले से क्रम में है। लोमुटो में पिवट अपने अंतिम स्थान पर पहुँचता है; होआर जैसी अन्य विभाजन विधियाँ अलग सीमा लौटाती हैं।
लोमुटो में पिवट लौटाए गए इंडेक्स पर सही जगह बैठ चुका है। इसलिए उस इंडेक्स को छोड़कर दोनों हिस्सों को क्रम में लगाएँ।
quick_sort(values, low, high)
if low >= high
return
pivot_index = lomuto_partition(values, low, high)
quick_sort(values, low, pivot_index - 1)
quick_sort(values, pivot_index + 1, high)कितना समय लगता है?
लगभग संतुलित विभाजनों में हर स्तर पर कुल काम O(n) होता है और लगभग log n स्तर होते हैं। इसलिए कुल समय O(n log n) होता है। बार-बार असंतुलित विभाजन हों तो समय O(n²) तक जा सकता है।
लोमुटो उसी सूची में अदला-बदली करता है। रिकर्सिव कॉल का स्टैक संतुलित विभाजनों में लगभग O(log n) जगह और बहुत असंतुलित विभाजनों में O(n) तक जगह ले सकता है।
मुख्य बात
पिवट से छोटे मानों की संख्या उसका स्थान बताती है। विभाजन दूसरे मानों को सही तरफ भी ले जाता है। फिर दोनों छोटे हिस्सों को स्वतंत्र रूप से क्रम में लगाया जा सकता है।
संदर्भ
एआई प्रकटीकरण: यह लेख एआई (ChatGPT) की सहायता से लिखा गया है। आपसे त्रुटियों और छूटी हुई बातों की ओर ध्यान दिलाने का अनुरोध है।





