बबल सॉर्ट

लिस्ट पर बार-बार चलता है और गलत क्रम वाले पड़ोसियों की अदला-बदली करता है। हर चक्कर के बाद बची हुई सबसे बड़ी वैल्यू अंत में पहुंच जाती है।

• सर्वश्रेष्ठ Ω(n)
• औसत Θ(n²)
• सबसे खराब O(n²)
• मेमोरी O(1)
• स्टेबल
• अतिरिक्त मेमोरी नहीं चाहिए

इनका मतलब क्या है?

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