सॉर्टिंग एल्गोरिदम की तुलना
कोई एक सबसे तेज़ सॉर्टिंग एल्गोरिदम नहीं है। कुछ सरल हैं पर धीमे, कुछ रैंडम डेटा पर तेज़ हैं पर सॉर्ट डेटा पर लड़खड़ाते हैं, और कुछ तुलना पर आधारित सॉर्ट हैं ही नहीं। आठों को एक ही सूची पर रेस कराने से अंतर एक नज़र में दिख जाता है।
तीन परिवार
बबल, सिलेक्शन और इंसर्शन सॉर्ट सरल सॉर्ट हैं। ये पास-पास के मानों की तुलना और अदला-बदली करते हैं और रैंडम सूची पर n² के अनुपात में समय लेते हैं। मर्ज, क्विक और हीप सॉर्ट काम को चतुराई से बाँटते हैं और n log n के अनुपात में समय लेते हैं, जो किसी भी सॉर्ट के लिए सबसे अच्छा है जब वह बस यही पूछ सकता हो कि दो मानों में कौन बड़ा है। रेडिक्स और काउंटिंग सॉर्ट यह सवाल पूरी तरह छोड़ देते हैं: वे सीधे अंकों या मानों का इस्तेमाल करते हैं, जो सिर्फ़ छोटी पूर्ण संख्याओं जैसी कुंजियों के लिए काम करता है।
काम को मापना
सॉर्ट मुकाबला हर तुलना, हर अंक या मान के रीड, और हर अदला-बदली या मूव के लिए एक ऑपरेशन गिनता है। 40 रैंडम मानों पर यह काउंटिंग सॉर्ट के लिए लगभग 120, रेडिक्स सॉर्ट के लिए 240, क्विकसॉर्ट के लिए 260, मर्ज सॉर्ट के लिए 380, हीप सॉर्ट के लिए 490, सिलेक्शन और इंसर्शन सॉर्ट में से हर एक के लिए लगभग 820, और बबल सॉर्ट के लिए 1,100 से ज़्यादा आता है। असली कंप्यूटर मेमोरी का भी ध्यान रखते हैं: सूची में चलने के तरीके की वजह से क्विकसॉर्ट व्यवहार में अक्सर अपनी गिनती से ज़्यादा तेज़ होता है, और हीप सॉर्ट धीमा।
इनपुट मायने रखता है
लगभग सॉर्ट सूची पर 40 मानों के लिए इंसर्शन सॉर्ट को सिर्फ़ लगभग 50 ऑपरेशन चाहिए और बबल सॉर्ट को लगभग 90, क्योंकि हर मान अपनी जगह के पास होता है। उल्टी सूची पर इन्हीं दोनों को 1,560 चाहिए, जो इनकी सबसे ख़राब स्थिति है। सिलेक्शन, हीप, मर्ज, रेडिक्स और काउंटिंग सॉर्ट पर क्रम का लगभग कोई असर नहीं पड़ता। तीन के मीडियन वाला क्विकसॉर्ट सॉर्ट और उल्टी सूचियों को अच्छी तरह संभालता है, लेकिन साधारण पिवट के साथ सॉर्ट सूची ही उसकी सबसे ख़राब स्थिति होती है। कुछ ही अलग मान होने पर क्विकसॉर्ट धीमा हो जाता है, क्योंकि बराबर मान सब एक ही तरफ़ चले जाते हैं।
मेमोरी और स्थिरता
बबल, सिलेक्शन, इंसर्शन, क्विक और हीप सॉर्ट इन-प्लेस काम करते हैं, यानी बहुत कम या बिना अतिरिक्त मेमोरी के। मर्ज, रेडिक्स और काउंटिंग सॉर्ट को सूची जितना लंबा बफ़र चाहिए। स्टेबल सॉर्ट बराबर मानों को उनके मूल क्रम में रखता है: बबल, इंसर्शन, मर्ज, रेडिक्स और काउंटिंग सॉर्ट स्टेबल हैं, जबकि सिलेक्शन, क्विक और हीप सॉर्ट नहीं। जब आप रिकॉर्ड को एक के बाद एक फ़ील्ड से सॉर्ट करते हैं, तब स्थिरता मायने रखती है।
कौन-सा इस्तेमाल करें
व्यवहार में आप अपनी प्रोग्रामिंग भाषा में बना सॉर्ट इस्तेमाल करते हैं: आमतौर पर Timsort, एक मर्ज सॉर्ट जो छोटे टुकड़ों के लिए इंसर्शन सॉर्ट इस्तेमाल करता है और आंशिक रूप से सॉर्ट डेटा पर तेज़ है, या introsort, एक क्विकसॉर्ट जो ज़रूरत पड़ने पर हीप सॉर्ट पर चला जाता है और छोटे हिस्सों के लिए इंसर्शन सॉर्ट इस्तेमाल करता है। बहुत सारी छोटी पूर्णांक कुंजियों के लिए काउंटिंग या रेडिक्स सॉर्ट दोनों को पीछे छोड़ सकते हैं। बबल और सिलेक्शन सॉर्ट ज़्यादातर पढ़ाने के काम आते हैं।
ख़ुद आज़माएँ
सॉर्ट मुकाबला खोलें और चलाएँ दबाएँ। हर लेन एक ही सूची पर एक सॉर्ट है; दाईं ओर की संख्या उसके ऑपरेशन गिनती है, और काम पूरा होने पर लेन हरी हो जाती है। लगभग सॉर्ट सूची, उल्टी सूची और कुछ ही अलग मानों वाली सूची आज़माएँ, और देखें कि पूरा होने का क्रम कैसे बदलता है। हर सॉर्ट का अपना ऐप भी है, जहाँ आप उसे चरण-दर-चरण विस्तार से देख सकते हैं।
अक्सर पूछे जाने वाले प्रश्न
सबसे तेज़ सॉर्टिंग एल्गोरिदम कौन-सा है?
सामान्य डेटा के लिए क्विकसॉर्ट और मर्ज सॉर्ट (और उन पर बने हाइब्रिड, जैसे introsort और Timsort) औसतन सबसे तेज़ हैं, n log n पर। छोटी पूर्णांक कुंजियों के लिए काउंटिंग और रेडिक्स सॉर्ट और भी तेज़ हैं। छोटी या लगभग सॉर्ट सूचियों के लिए इंसर्शन सॉर्ट जीतता है।
कोई तुलना सॉर्ट n log n से बेहतर क्यों नहीं कर सकता?
n मानों की सूची n! क्रमों में हो सकती है, और हर तुलना के दो नतीजे होते हैं, इसलिए सबसे ख़राब स्थिति में सबको अलग पहचानने के लिए कम से कम log₂(n!) तुलनाएँ चाहिए। यह लगभग n log₂ n है। रेडिक्स और काउंटिंग सॉर्ट इस सीमा से बच जाते हैं क्योंकि वे तुलना नहीं करते।
कौन-से सॉर्टिंग एल्गोरिदम स्टेबल हैं?
बबल, इंसर्शन, मर्ज, रेडिक्स और काउंटिंग सॉर्ट अपने सामान्य रूप में स्टेबल हैं। सिलेक्शन सॉर्ट, क्विकसॉर्ट और हीप सॉर्ट नहीं हैं, क्योंकि वे मानों को लंबी दूरी तक खिसकाते हैं।
किन सॉर्ट को अतिरिक्त मेमोरी चाहिए?
मर्ज, रेडिक्स और काउंटिंग सॉर्ट को लगभग सूची जितना लंबा बफ़र चाहिए। बबल, सिलेक्शन, इंसर्शन और हीप सॉर्ट को लगभग कुछ नहीं चाहिए, और क्विकसॉर्ट को अपने रिकर्शन के लिए बस थोड़ी-सी।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
सॉर्ट मुकाबला शुरू करें