Python एल्गोरिदम

Python में Quick Sort

Pivot के आसपास values partition करें।

  • मध्यम
  • 2 मिनट में पढ़ें
  • 1 चलाने योग्य उदाहरण

में Quick Sort क्या है?

समस्या क्या है

Quicksort सबसे ज़्यादा इस्तेमाल होने वाले सॉर्टिंग विचारों में से एक है, क्योंकि यह औसतन तेज़ है और लिखने में आसान। यह समस्या को बाँटने का एक और तरीका दिखाता है: बीच से बाँटने की जगह, एक चुनी हुई वैल्यू के आसपास बाँटिए।

ऐसे समझें

Quicksort ऐसा है जैसे एक किताब चुनकर बाकी किताबों को उसकी ऊँचाई से तुलना करके लगाना। हर छोटी किताब बाएँ ढेर पर, हर ऊँची किताब दाएँ ढेर पर, और बराबर ऊँचाई वाली बीच में रखिए। फिर हर तरफ़ के ढेर को इसी तरह सॉर्ट कीजिए, और ढेरों को वापस जोड़ दीजिए।

किताबों के ढेर से code तक
pivot = values[len(values) // 2]📕 तुलना के लिए एक किताब चुनिए
lower = [... if value < pivot]⬅️ छोटी किताबें बाईं तरफ़
higher = [... if value > pivot]➡️ ऊँची किताबें दाईं तरफ़
quick_sort(lower) + equal + quick_sort(higher)📚 हर तरफ़ सॉर्ट कीजिए, फिर ढेर जोड़िए
Pivot से छोटे और बड़े में बाँटिए, फिर हर तरफ़ को इसी तरह सॉर्ट कीजिए।
एक वाक्य में

Quicksort एक pivot (तुलना के लिए चुनी गई वैल्यू) चुनता है, बाकी आइटम को उससे छोटे और बड़े में बाँटता है, हर हिस्से को recursion से सॉर्ट करता है और उन्हें जोड़ देता है। औसतन इसमें O(n log n) समय लगता है।

मुख्य बातें

  1. if len(values) <= 1: base case है: ऐसी list पहले से सॉर्ट की हुई है।
  2. pivot = values[len(values) // 2] बीच वाली वैल्यू को pivot बनाता है।
  3. lower, equal और higher वैल्यू को pivot के हिसाब से बाँटते हैं। equal में duplicates (दोहराई गई वैल्यू) साथ रहते हैं।
  4. 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 देखने के लिए चलाएँ या अगला चरण दबाएँ।

उदाहरण कोड

कोड चलाएँ →
main.py
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]))
इस उदाहरण के लिए Run बटन बनाएँ

अपेक्षित आउटपुट

[1, 5, 7, 8, 9, 10]

यह कैसे काम करता है

औसत समय O(n log n) है, लेकिन खराब pivot selection पर O(n²) हो सकता है।

मान बदलें और Python इंस्टॉल किए बिना CodeUtility ऑनलाइन Python कंपाइलर में प्रोग्राम चलाएँ।

अभ्यास के कार्य

बड़े dataset पर जाने से पहले input बदलें और edge cases की जाँच करें।

  1. खाली input, एक element और duplicate values जाँचें।
  2. हर चरण के बाद state दिखाएँ।
  3. Performance को दूसरे solution से तुलना करें।
Python IDE में चलाएँ →

आम गलतियाँ

Pivot के बराबर वैल्यू गिरा देना

सिर्फ़ < और > रखने पर pivot के duplicates गायब हो जाते हैं।

समस्या
return quick_sort(lower) + [pivot] + quick_sort(higher)
सुधार
return quick_sort(lower) + equal + quick_sort(higher)

यह पाठ पूरा कर लिया?

अपनी प्रगति ट्रैक करने के लिए इसे सीखा हुआ मार्क करें।

चैलेंज से अभ्यास करें

इस पाठ में सीखी बात से एक असली समस्या हल करें। हर चैलेंज ब्राउज़र में चलता है, तुरंत टेस्ट और AI रिव्यू के साथ।

सभी चैलेंज