Quicksort
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 follow4. 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 the6. 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 pointer7. 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 pointer8. Quicksort - in action
and swap these items.9. Quicksort - in action
We start again10. Quicksort - in action
moving the left pointer and stopping when we find a greater element.11. Quicksort - in action
We move12. 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 is15. 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 swap19. 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 pointer25. Quicksort - in action
to find a lower value. Since there isn't any, we finish pointing to the pivot, so we stop the right pointer26. 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 it29. 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!Create Your Free Account
or
By continuing, you accept our Terms of Use, our Privacy Policy and that your data is stored in the USA.