Sorting is the task of arranging, in either increasing or decreasing order, a given set of numbers (or other orderable quantities) in an array. Sorting is an important task in computer science and considered to be among the most basic skills necessary for a programmer.
How does quicksort work?
Quicksort has some similar characteristics to merge sort. Like merge sort, it partitions the array into two parts, sorts each part and then combines the results. But the similarities stop there. Quicksort does more work before the partitioning so that the merging becomes easier, almost trivial.
We illustrate how quicksort works using a running example. We are given the array [35, 67, 12, 95, 21] and desire to sort it in increasing order, so that 12 becomes the first element and 95 becomes the last element. In other words, the array should become [12, 21, 35, 67, 95].
Quicksort begins by identifying a “pivot” which is one of the elements in the given array. There are many pivot selection strategies but for simplicity we will assume that the first element is the pivot. Then quicksort does a series of swaps so that the pivot is moved to a position in the array so that everything left of the pivot is less than (or equal to) the pivot and everything right of the pivot is greater than the pivot.
For instance, given the array [35, 67, 12, 95, 21] assuming we choose 35 as the pivot, quicksort will do moves so that the array becomes [12, 21, 35, 95, 67]. At this point, now that 35 is in its correct position, quicksort can be called recursively on each sub-array, namely [12, 21] and [95, 67]. Each of these smaller arrays can be sorted in place and 35 will not need to move.
So how exactly do the swaps work? The following diagram illustrates how this works.
Quicksort maintains, in addition to the pivot, two sets of pointers, symbolized as left (l) and right (r) initialized to the leftmost and rightmost locations of the array. The left pointer is moved (right) till it reaches an element higher than the pivot. Similarly, the right pointer is moved (left) till it reaches an element less than the pivot. Note that for the above example, the left pointer is moved to point to 67 and the right pointer stays at 21. At this point a swap happens and the array becomes [35, 21, 12, 95, 67].
The pointers continue to move until the same condition is met. This time, the right pointer points to 12 and the left pointer points to 95. Note that the pointers have crossed each other. When this happens the pivot is exchanged with the right pointer, yielding the array [12, 21, 35, 95, 67].
35 reaches its intended destination. Quicksort is now recursively called with [12, 21] and with [95, 67] and the results of these sorts and returned to yield the final sorted array, namely [12, 21, 35, 67, 95].
How efficient is quicksort?
Note that quicksort sorts elements in place - like bubble sort, it just swaps elements but unlike bubble sort it is more efficient. Its average-case performance is O(n*log(n)) where n is the size of the array.
What are the advantages of quicksort?
Quicksort is a divide-and-conquer algorithm like mergesort and thus can be defined recursively. Because it sorts in-place, its memory requirements are not as high as that of mergesort. Also, compared to insertion sort and bubble sort, its time complexity is very competitive. Finally, even though the time complexity of O(n*log(n)) is comparable to that of merge sort, the constant factor hiding in the big O() notation is smaller in the case of quicksort.
What are the disadvantages of quicksort?
Quicksort’s worst-case complexity can be O(n^2). It is not a stable sorting algorithm meaning it does not retain the relative order of elements that are equal.
How can we code quicksort in Python?
We follow the worked out example shown above.
First, we write a routine that sets up the left and right pointers and moves them. The code below with comments should be self-explanatory.
Next, we setup a function to find the partition point and recursively call quicksort on both sides of the partition. Note that we need to pass the left and right pointer locations explicitly.
Finally, we have the driver function that calls quicksort automatically by setting the initial values of the left and right pointer locations.
Kodeclik is an online coding academy for kids and teens to learn real world programming. Kids are introduced to coding in a fun and exciting way and are challeged to higher levels with engaging, high quality content.