क्विकसॉर्ट

एक वैल्यू चुनता है, जिसे पिवट कहते हैं, और छोटी वैल्यू उसके बाईं ओर व बड़ी दाईं ओर ले जाता है। फिर हर तरफ यही दोहराता है।

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

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

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