सिलेक्शन सॉर्ट

बची हुई सबसे छोटी वैल्यू ढूंढकर अदला-बदली से उसे अगली जगह पर रखता है। अदला-बदली बहुत कम होती है, पर तुलनाएं हमेशा उतनी ही होती हैं।

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

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

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