1. Quicksort
We will now study quicksort.
2. Quicksort
Quicksort
follows the divide and conquer principle. It is
implemented by many programming languages. It
uses a partition technique by choosing a value from the list called the
pivot. All
items smaller than the pivot will end at the left of the pivot,
and greater elements at the right. Quicksort will be called recursively
on the elements to the left
and right of the pivot.
3. Quicksort - in action
We follow
4. Quicksort - in action
Hoare's partition approach, which sets the pivot as the first element.
5. Quicksort - in action
We use two pointers. The left pointer points to the first value from the pivot and the right pointer to the last value. We
move the
6. Quicksort - in action
left pointer until we find a greater value than the pivot. Nine is greater than six, so we stop the left pointer. We continue with the right pointer
7. Quicksort - in action
and move it until we find a value lower than the pivot. Since four is lower than six, we stop the right pointer
8. Quicksort - in action
and swap these items.
9. Quicksort - in action
We start again
10. Quicksort - in action
moving the left pointer and stopping when we find a greater element.
11. Quicksort - in action
We move
12. Quicksort - in action
the right pointer until we find a smaller value. When the pointers cross,
13. Quicksort - in action
we swap the item of the right pointer with the pivot.
14. Quicksort - in action
Now, the pivot is
15. Quicksort - in action
in its correct position. Elements to the left of the pivot are smaller than the pivot, and elements to the right are greater. We then apply quicksort to the left and right parts of the pivot.
16. Quicksort - in action
Starting with the left part,
17. Quicksort - in action
we select a new pivot and set the pointers. In this case, both pointers point to the same number. Since there aren't more numbers,
18. Quicksort - in action
we swap
19. Quicksort - in action
these items.
20. Quicksort - in action
Now, four is in its correct position. There is only one number left, so we leave it as is.
21. Quicksort - in action
Once the left part is sorted,
22. Quicksort - in action
we continue with the right.
23. Quicksort - in action
We select a new pivot and set the pointers. The left pointer points to a value that is greater than the pivot, so we stop.
24. Quicksort - in action
We move the right pointer
25. Quicksort - in action
to find a lower value. Since there isn't any, we finish pointing to the pivot, so we stop the right pointer
26. Quicksort - in action
and leave the pivot where it is.
27. Quicksort - in action
We continue with the last element. Since it is lower than the pivot,
28. Quicksort - in action
we swap it
29. Quicksort - in action
with the pivot.
30. Quicksort - in action
The numbers are sorted.
31. Quicksort - implementation
Let's implement quicksort in Python.
This function receives a list, along with first_index and last_index.
If first_index is smaller than last_index,
we call the partition function which returns an index for the partition. Then,
we call quicksort on the elements to the left of the partition,
followed by elements to the right.
32. Quicksort - implementation
The partition function shown on the previous slide involves
setting values for the pivot, left_pointer, and right_pointer.
We start a loop and move the left_pointer until we find a value greater than the pivot or the left_pointer increases the value of last_index,
and then move the right_pointer until we find a value lower than the pivot or the right_pointer is less than the first_index.
If the left_pointer is greater than the right_pointer, we break. If it isn't,
we swap the values for the elements located at the left_pointer and right_pointer. If we break the loop,
we will have to swap the pivot with the value pointed by the right_pointer. Finally,
we return right_pointer.
33. Quicksort - implementation
We can execute quicksort as shown.
34. Quicksort - complexity
Although quicksort has a complexity of
O of n-squared,
it is very efficient, taking
n log n in the average and best cases, and a space complexity of
n log n.
35. Let's practice!
Let's practice!