Quicksort

Python में Data Structures और Algorithms

Miriam Antona

Software engineer

Quicksort

Divide and conquer सिद्धांत का पालन करता है
कई programming languages इसे implement करती हैं
Partition तकनीक
- Pivot
- pivot से छोटे items -> left
- pivot से बड़े items -> right
Left वाले elements को recursively sort करेंगे
Right वाले elements को recursively sort करेंगे

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र.

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. पहला तत्व नीले रंग में है.

Hoare का partition

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. पहला तत्व नीले रंग में है. दो pointers हैं. बायाँ pointer दूसरे तत्व पर और दायाँ pointer आखिरी तत्व पर है.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. पहला तत्व नीले रंग में है. दो pointers हैं. बायाँ pointer तीसरे तत्व पर और दायाँ pointer आखिरी तत्व पर है.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. पहला तत्व नीले रंग में है. दो pointers हैं. बायाँ pointer तीसरे तत्व पर और दायाँ pointer पाँचवें तत्व पर है.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए
- Right pointer को तब तक घटाएँ जब तक pivot से छोटा मान न मिल जाए

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. पहला तत्व नीले रंग में है. दो pointers हैं. बायाँ pointer तीसरे तत्व पर और दायाँ pointer पाँचवें तत्व पर है. दो तीर दिखाते हैं कि तीसरा और पाँचवाँ तत्व swap होंगे.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए
- Right pointer को तब तक घटाएँ जब तक pivot से छोटा मान न मिल जाए

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. पहला तत्व नीले रंग में है. दो pointers हैं. बायाँ pointer तीसरे तत्व पर और दायाँ pointer पाँचवें तत्व पर है. तीसरा और पाँचवाँ तत्व swap हो चुके हैं.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए
- Right pointer को तब तक घटाएँ जब तक pivot से छोटा मान न मिल जाए

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. पहला तत्व नीले रंग में है. दो pointers हैं. बायाँ pointer चौथे तत्व पर और दायाँ pointer पाँचवें तत्व पर है.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए
- Right pointer को तब तक घटाएँ जब तक pivot से छोटा मान न मिल जाए

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. पहला तत्व नीले रंग में है. दो pointers हैं. बायाँ और दायाँ pointer दोनों चौथे तत्व पर हैं.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए
- Right pointer को तब तक घटाएँ जब तक pivot से छोटा मान न मिल जाए

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. पहला तत्व नीले रंग में है. दो pointers हैं. बायाँ pointer चौथे तत्व पर और दायाँ pointer तीसरे तत्व पर है.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए
- Right pointer को तब तक घटाएँ जब तक pivot से छोटा मान न मिल जाए

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. पहला तत्व नीले रंग में है. दो pointers हैं. बायाँ pointer चौथे तत्व पर और दायाँ pointer तीसरे तत्व पर है. दो तीर दिखाते हैं कि पहला और तीसरा तत्व swap होंगे.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए
- Right pointer को तब तक घटाएँ जब तक pivot से छोटा मान न मिल जाए

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. तीसरा तत्व नीले रंग में है. पहला और तीसरा तत्व swap हो चुके हैं.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए
- Right pointer को तब तक घटाएँ जब तक pivot से छोटा मान न मिल जाए

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. तीसरा तत्व हरे रंग में है.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए
- Right pointer को तब तक घटाएँ जब तक pivot से छोटा मान न मिल जाए

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. तीसरा तत्व हरे रंग में है और पहले दो तत्व नारंगी में, जो सूची के बाएँ भाग को दर्शाते हैं.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए
- Right pointer को तब तक घटाएँ जब तक pivot से छोटा मान न मिल जाए

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. पहला तत्व नीला, दूसरा नारंगी, तीसरा हरा. left और right pointers दूसरे तत्व पर हैं.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए
- Right pointer को तब तक घटाएँ जब तक pivot से छोटा मान न मिल जाए

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. पहला नीला, दूसरा नारंगी, तीसरा हरा. left और right pointers दूसरे तत्व पर हैं. दो तीर दिखाते हैं कि पहला और दूसरा तत्व swap होंगे.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए
- Right pointer को तब तक घटाएँ जब तक pivot से छोटा मान न मिल जाए

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. पहला नीला, दूसरा नारंगी, तीसरा हरा. left और right pointers दूसरे तत्व पर हैं. पहला और दूसरा तत्व swap हो चुके हैं.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए
- Right pointer को तब तक घटाएँ जब तक pivot से छोटा मान न मिल जाए

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. पहला तत्व नारंगी, दूसरा और तीसरा हरे रंग में हैं.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए
- Right pointer को तब तक घटाएँ जब तक pivot से छोटा मान न मिल जाए

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. पहला, दूसरा और तीसरा तत्व हरे रंग में हैं.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए
- Right pointer को तब तक घटाएँ जब तक pivot से छोटा मान न मिल जाए

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. पहला, दूसरा और तीसरा तत्व हरे रंग में हैं. दाईं तरफ की सूची नारंगी रंग में है.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए
- Right pointer को तब तक घटाएँ जब तक pivot से छोटा मान न मिल जाए

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. पहला, दूसरा और तीसरा तत्व हरे हैं. दाएँ भाग का पहला तत्व नीला है. बायाँ pointer दाएँ भाग के दूसरे तत्व पर और दायाँ pointer दाएँ भाग के आखिरी तत्व पर है.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए
- Right pointer को तब तक घटाएँ जब तक pivot से छोटा मान न मिल जाए

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. पहला, दूसरा और तीसरा तत्व हरे हैं. दाएँ भाग का पहला तत्व नीला है. बायाँ और दायाँ pointer दाएँ भाग के दूसरे तत्व पर हैं.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए
- Right pointer को तब तक घटाएँ जब तक pivot से छोटा मान न मिल जाए

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. पहला, दूसरा और तीसरा तत्व हरे हैं. दाएँ भाग का पहला तत्व नीला है. बायाँ pointer दाएँ भाग के पहले तत्व पर और दायाँ pointer दूसरे तत्व पर है.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए
- Right pointer को तब तक घटाएँ जब तक pivot से छोटा मान न मिल जाए

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. पहला, दूसरा, तीसरा और चौथा तत्व हरे, पाँचवाँ और छठा नारंगी हैं.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए
- Right pointer को तब तक घटाएँ जब तक pivot से छोटा मान न मिल जाए

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. पहला, दूसरा, तीसरा और चौथा तत्व हरे हैं. तत्व नीला है. बायाँ और दायाँ pointer आखिरी तत्व पर हैं.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए
- Right pointer को तब तक घटाएँ जब तक pivot से छोटा मान न मिल जाए

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. पहला, दूसरा, तीसरा और चौथा तत्व हरे हैं. तत्व नीला है. बायाँ और दायाँ pointer आखिरी तत्व पर हैं. दो तीर दिखाते हैं कि पाँचवाँ और छठा तत्व swap होंगे.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए
- Right pointer को तब तक घटाएँ जब तक pivot से छोटा मान न मिल जाए

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. पहला, दूसरा, तीसरा और चौथा तत्व हरे हैं. तत्व नीला है. बायाँ और दायाँ pointer आखिरी तत्व पर हैं. पाँचवाँ और छठा तत्व swap हो चुके हैं.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए
- Right pointer को तब तक घटाएँ जब तक pivot से छोटा मान न मिल जाए

Quicksort - in action

बिना क्रम वाली संख्याओं की सूची का रेखाचित्र. सभी तत्व हरे हैं क्योंकि वे sorted हैं.

Hoare का partition
- Left pointer को तब तक बढ़ाएँ जब तक pivot से बड़ा मान न मिल जाए
- Right pointer को तब तक घटाएँ जब तक pivot से छोटा मान न मिल जाए

Quicksort - implementation

def quicksort(my_list, first_index, last_index):

    if first_index < last_index:

        partition_index = partition(my_list, first_index, last_index)

        quicksort(my_list, first_index, partition_index)

        quicksort(my_list, partition_index + 1, last_index)

Quicksort - implementation

def partition(my_list, first_index, last_index):

    pivot = my_list[first_index]
    left_pointer = first_index + 1
    right_pointer = last_index

    while True: 
        while my_list[left_pointer] < pivot and left_pointer < last_index:
            left_pointer += 1

        while my_list[right_pointer] > pivot and right_pointer >= first_index:
            right_pointer -= 1

        if left_pointer >= right_pointer:
            break

        my_list[left_pointer], my_list[right_pointer] = my_list[right_pointer], my_list[left_pointer]

    my_list[first_index], my_list[right_pointer] = my_list[right_pointer], my_list[first_index]

    return right_pointer

Quicksort - implementation

my_list = [6, 2, 9, 7, 4, 8] 
quicksort(my_list, 0, len(my_list) - 1)
print(my_list)

[2, 4, 6, 7, 8, 9]

Quicksort - complexity

Worst case: $O(n^2)$
बहुत efficient!
- Average case: $\Theta(n\log{}n)$
- Best case: $\Omega(n\log{}n)$
Space complexity: $O(n\log{}n)$

अभ्यास करते हैं!

Python में Data Structures और Algorithms