में Quick Sort क्या है?
समस्या क्या है
Quicksort सबसे ज़्यादा इस्तेमाल होने वाले सॉर्टिंग विचारों में से एक है, क्योंकि यह औसतन तेज़ है और लिखने में आसान। यह समस्या को बाँटने का एक और तरीका दिखाता है: बीच से बाँटने की जगह, एक चुनी हुई वैल्यू के आसपास बाँटिए।
ऐसे समझें
Quicksort ऐसा है जैसे एक किताब चुनकर बाकी किताबों को उसकी ऊँचाई से तुलना करके लगाना। हर छोटी किताब बाएँ ढेर पर, हर ऊँची किताब दाएँ ढेर पर, और बराबर ऊँचाई वाली बीच में रखिए। फिर हर तरफ़ के ढेर को इसी तरह सॉर्ट कीजिए, और ढेरों को वापस जोड़ दीजिए।
pivot = values[len(values) // 2]📕 तुलना के लिए एक किताब चुनिएlower = [... if value < pivot]⬅️ छोटी किताबें बाईं तरफ़higher = [... if value > pivot]➡️ ऊँची किताबें दाईं तरफ़quick_sort(lower) + equal + quick_sort(higher)📚 हर तरफ़ सॉर्ट कीजिए, फिर ढेर जोड़िएQuicksort एक pivot (तुलना के लिए चुनी गई वैल्यू) चुनता है, बाकी आइटम को उससे छोटे और बड़े में बाँटता है, हर हिस्से को recursion से सॉर्ट करता है और उन्हें जोड़ देता है। औसतन इसमें O(n log n) समय लगता है।
मुख्य बातें
if len(values) <= 1:base case है: ऐसी list पहले से सॉर्ट की हुई है।pivot = values[len(values) // 2]बीच वाली वैल्यू को pivot बनाता है।lower,equalऔरhigherवैल्यू को pivot के हिसाब से बाँटते हैं।equalमें duplicates (दोहराई गई वैल्यू) साथ रहते हैं।quick_sort(lower) + equal + quick_sort(higher)दोनों तरफ़ सॉर्ट करता है और तीनों list जोड़ता है।
इसका उपयोग कब करें?
- Partitioning और recursion सीखना।
- कई भाषाओं और लाइब्रेरी की in-place sorting, जहाँ pivot सावधानी से चुना जाता है।
- Median ढूँढने जैसी selection समस्याएँ (quickselect वही partition इस्तेमाल करता है)।
कब ज़रूरत नहीं
- सामान्य Python code:
sorted()ज़्यादा तेज़ और stable है। - जब worst case की गारंटी चाहिए: ख़राब pivot से quicksort
O(n²)हो जाता है। Merge sort के साथ ऐसा कभी नहीं होता।
Python में Quick Sort Visualizer
O(n log n)हर comparison और data movement देखने के लिए चलाएँ या अगला चरण दबाएँ।
उदाहरण कोड
def quick_sort(values):
if len(values) <= 1:
return values
pivot = values[len(values) // 2]
lower = [value for value in values if value < pivot]
equal = [value for value in values if value == pivot]
higher = [value for value in values if value > pivot]
return quick_sort(lower) + equal + quick_sort(higher)
print(quick_sort([10, 7, 8, 9, 1, 5]))
अपेक्षित आउटपुट
[1, 5, 7, 8, 9, 10]
यह कैसे काम करता है
औसत समय O(n log n) है, लेकिन खराब pivot selection पर O(n²) हो सकता है।
मान बदलें और Python इंस्टॉल किए बिना CodeUtility ऑनलाइन Python कंपाइलर में प्रोग्राम चलाएँ।
अभ्यास के कार्य
बड़े dataset पर जाने से पहले input बदलें और edge cases की जाँच करें।
- खाली input, एक element और duplicate values जाँचें।
- हर चरण के बाद state दिखाएँ।
- Performance को दूसरे solution से तुलना करें।
आम गलतियाँ
Pivot के बराबर वैल्यू गिरा देना
सिर्फ़ < और > रखने पर pivot के duplicates गायब हो जाते हैं।
return quick_sort(lower) + [pivot] + quick_sort(higher)
return quick_sort(lower) + equal + quick_sort(higher)
यह पाठ पूरा कर लिया?
अपनी प्रगति ट्रैक करने के लिए इसे सीखा हुआ मार्क करें।
चैलेंज से अभ्यास करें
इस पाठ में सीखी बात से एक असली समस्या हल करें। हर चैलेंज ब्राउज़र में चलता है, तुरंत टेस्ट और AI रिव्यू के साथ।
सभी चैलेंज