Get startedGet started for free

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 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!