बबल सॉर्ट
लिस्ट पर बार-बार चलता है और गलत क्रम वाले पड़ोसियों की अदला-बदली करता है। हर चक्कर के बाद बची हुई सबसे बड़ी वैल्यू अंत में पहुंच जाती है।
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- हाँ
- हाँ
सर्वश्रेष्ठ: जब इनपुट इस एल्गोरिदम के लिए सबसे आसान हो, तब लिस्ट के आकार n के साथ समय कैसे बढ़ता है।
औसत: n के साथ समय की आम बढ़त। n² में वैल्यू की संख्या दोगुनी होने पर लगभग चार गुना समय लगता है; n log n बहुत धीरे बढ़ता है।
सबसे खराब: सबसे कठिन इनपुट पर बढ़त। तब काम का, जब रफ़्तार कभी नहीं गिरनी चाहिए।
मेमोरी: लिस्ट के अलावा कितनी अतिरिक्त मेमोरी चाहिए। 1 यानी कुछ वेरिएबल, n यानी लिस्ट की एक कॉपी।
स्टेबल: दो बराबर वैल्यू अपना मूल क्रम बनाए रखती हैं। रिकॉर्ड के किसी एक फ़ील्ड से सॉर्ट करते समय यह ज़रूरी है।
अतिरिक्त मेमोरी नहीं चाहिए: लिस्ट के अंदर ही सॉर्ट करता है, दूसरी लिस्ट के बिना।
- तुलना हो रही है
- खिसक रहा है
- अंतिम जगह पर
इसे आज़माएं: लगभग सॉर्टेड लिस्ट चुनें। बिना अदला-बदली वाले एक चक्कर के बाद एल्गोरिदम जल्दी रुक जाता है।
यह कैसे काम करता है
यह एक बार में दो पड़ोसियों की तुलना करता है और बायां बड़ा हो तो दोनों की अदला-बदली करता है। इसलिए हर चक्कर में सबसे बड़ी वैल्यू बुलबुले की तरह उठकर सबसे दाईं ओर पहुंच जाती है। किसी चक्कर में एक भी अदला-बदली न हो, तो लिस्ट सॉर्ट हो चुकी है।
यह कब सही विकल्प है
असली प्रोग्रामों में लगभग कभी नहीं, क्योंकि लंबी लिस्ट पर यह धीमा है। सीखने के लिए यह बढ़िया है: इससे तुलना और अदला-बदली से सॉर्ट करने का मूल विचार समझ आता है। यह तभी तेज़ है जब लिस्ट पहले से सॉर्टेड हो।