- विभाजित हो रहा हिस्सा
- पिवट
- तुलना में
- बदले गए
- अपनी जगह पर
क्विकसॉर्ट
क्विकसॉर्ट एक पिवट चुनता है, उससे छोटे हर मान को उसके पहले और बाक़ी हर मान को उसके बाद रखता है, फिर दोनों तरफ़ को इसी तरह सॉर्ट करता है। हर विभाजन के बाद पिवट अपनी अंतिम जगह पर पहुँच जाता है। पिवट चुनने का तरीक़ा चुनें, सॉर्ट को किसी भी गति से चलाएँ या एक-एक तुलना करके आगे बढ़ें, और देखें कि सॉर्ट की हुई सूची पर बुरा पिवट क्विकसॉर्ट को धीमा क्यों कर देता है। सॉर्ट देखने के लिए चलाएँ दबाएँ, या एक-एक तुलना करके बढ़ने के लिए आगे और पीछे दबाएँ। कहीं भी जाने के लिए चरण स्लाइडर खींचें। टाइलें तुलनाएँ, अदला-बदली और विभाजन गिनती हैं। बार की संख्या और उनका शुरुआती क्रम चुनें, या अपनी संख्याएँ लिखें, और चुनें कि पिवट कैसे चुना जाए। बोर्ड चुना हो तो तीर कुंजियाँ एक-एक चरण चलाती हैं, स्पेस बार चलाता और रोकता है, और Home व End शुरुआत और अंत पर ले जाते हैं।
यह कैसे काम करता है
- बार की संख्या और उनका शुरुआती क्रम चुनें: रैंडम, लगभग सॉर्ट, उल्टा, या कुछ ही अलग मानों वाला। या अपनी संख्याएँ लिखें।
- चलाएँ दबाएँ, या एक-एक तुलना करके बढ़ने के लिए आगे और पीछे का इस्तेमाल करें। सॉर्ट में कहीं भी जाने के लिए चरण स्लाइडर खींचें।
- पिवट का नियम चुनें: आख़िरी मान, बीच का मान, रैंडम मान, या तीन का मीडियन। हर एक को सॉर्ट की हुई सूची पर आज़माएँ।
क्विकसॉर्ट कैसे काम करता है
सॉर्ट होने वाले हिस्से का एक मान पिवट के रूप में चुनें और उसे अंत में ले जाएँ। बाक़ी मानों को बाएँ से दाएँ देखें; पिवट से छोटा हर मान अदल-बदलकर उस बाएँ हिस्से में आता है जो शुरुआत से बढ़ता है। फिर पिवट को अदल-बदलकर बाएँ हिस्से के ठीक बाद रखें। उसके पहले के सभी मान अब छोटे हैं और उसके बाद कोई छोटा नहीं है, इसलिए पिवट अपनी अंतिम जगह पर है। उसके पहले और बाद के हिस्सों को इसी तरह सॉर्ट करें, जब तक हर हिस्से में एक ही मान न रह जाए।
पिवट क्यों मायने रखता है
जब पिवट बीच के पास आता है, तो हर विभाजन समस्या को आधा कर देता है, और तुलनाएँ n log n की तरह बढ़ती हैं: 40 रैंडम मानों के लिए लगभग 190। जब पिवट सबसे छोटा या सबसे बड़ा मान होता है, तो एक तरफ़ खाली रहती है और दूसरी तरफ़ बाक़ी सब कुछ। आख़िरी मान को पिवट बनाने पर सॉर्ट की हुई या उल्टी सूची में हर चरण पर ऐसा होता है, और सॉर्ट में n(n − 1)/2 तुलनाएँ लगती हैं, 40 मानों के लिए 780। रैंडम पिवट या पहले, बीच वाले और आख़िरी मान का मीडियन व्यवहार में इससे बचाता है।
अक्सर पूछे जाने वाले प्रश्न
क्विकसॉर्ट कैसे काम करता है?
यह एक पिवट चुनता है, सूची का विभाजन करता है ताकि छोटे मान पिवट से पहले और बाक़ी उसके बाद आएँ, और फिर दोनों तरफ़ को क्विकसॉर्ट से सॉर्ट करता है। हर विभाजन के बाद पिवट अपनी अंतिम जगह पर होता है।
सॉर्ट की हुई सूची पर क्विकसॉर्ट धीमा क्यों है?
पहले या आख़िरी मान को पिवट बनाने पर सॉर्ट की हुई सूची में पिवट हमेशा सबसे छोटा या सबसे बड़ा मान होता है। तब विभाजन की एक तरफ़ खाली रहती है, इसलिए हर विभाजन सिर्फ़ एक मान हटाता है, और सॉर्ट में n(n − 1)/2 तुलनाएँ लगती हैं। रैंडम पिवट या तीन का मीडियन व्यवहार में इसे ठीक कर देता है।
क्या क्विकसॉर्ट मर्ज सॉर्ट से तेज़ है?
व्यवहार में अक्सर हाँ: यह इन-प्लेस सॉर्ट करता है, इसे बफ़र की ज़रूरत नहीं होती, और इसका अंदरूनी लूप बहुत सरल है। औसतन यह मर्ज सॉर्ट से कुछ ज़्यादा तुलनाएँ करता है, और इसकी सबसे ख़राब स्थिति n² है, जबकि मर्ज सॉर्ट हमेशा n log n रहता है। introsort जैसे लाइब्रेरी सॉर्ट क्विकसॉर्ट से शुरू करते हैं और बँटवारा बहुत असमान होने पर हीप सॉर्ट पर चले जाते हैं।
क्या क्विकसॉर्ट स्थिर (stable) है?
नहीं। विभाजन मानों को दूर-दूर तक अदल-बदल करता है, इसलिए बराबर मानों का क्रम बदल सकता है।
क्या मेरी संख्याएँ कहीं भेजी जाती हैं?
नहीं। सॉर्ट आपके ब्राउज़र में चलता है, और आपकी पिछली सेटिंग इसी ब्राउज़र के लोकल स्टोरेज में रहती हैं।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
एडिटर पर जाएँ