Quicksort in Python
Introduction
Quicksort is a popular sorting algorithm and is often used, right alongside Merge Sort. It’s a good example of an efficient sorting algorithm, with an average complexity of O(nlogn). Part of its popularity also derives from the ease of implementation.
We will use simple integers in the first part of this article, but we’ll give an example of how to change this algorithm to sort objects of a custom class.
Quicksort is a representative of three types of sorting algorithms: divide and conquer, in-place, and unstable.
- Divide and conquer: Quicksort splits the array into smaller arrays until it ends up with an empty array, or one that has only one element, before recursively sorting the larger arrays.
- In place: Quicksort doesn’t create any copies of the array or any of its subarrays. It does however require stack memory for all the recursive calls it makes.
- Unstable: A stable sorting algorithm is one in which elements with the same value appear in the same relative order in the sorted array as they do before the array is sorted. An unstable sorting algorithm doesn’t guarantee this, it can of course happen, but it isn’t guaranteed.
This is something