1. Introduction
Quicksort is a sorting algorithm that uses the divide-and-conquer paradigm. Depending on its implementation, it is a quite efficient algorithm. This blog post provides a short introduction to this algorithm. All code examples are available on GitHub.
2. Background
Quicksort was developed in 1959 by the British computer scientist Sir Charles Antony Richard Hoare, better known as Tony Hoare. He came up with the algorithm because he needed to sort words in Russian sentences at the time. Nowadays, there are countless systems that use quicksort. Developers like to use quicksort because it is usually fast and efficient.
3. How it works
Given a set of numbers S
, we have four steps that we have to take in this algorithm:
- If
S
is empty or only has one entry: return. - Pick an element
v
inS
, the pivot. - Partition
S
in two disjoint setsL
andR
, such thatL
only contains elements that are lesser than the pivotv
, andR
contains only contains elements that are greater than the pivotv
. - Repeat this algorithm for
L
andR
. Now, if you combine all sorted subsets, you'll get the entire sorted set.
Example
We have the following set of integers:
We now have to pick some pivot, in this case its 43
:
Now we partition S
without our pivot in two disjoint subsets: L
and R
. Note that all elements in the left subset
are smaller than the pivot, and all elements in the right subset are greater than the pivot:
For each of the partitions, you now recursively apply quicksort. After doing so, you'll end up with separate sorted lists, that you then combine into one:
4. Kotlin implementation
In the following Kotlin example (also available on GitHub), we made an implementation that sorts integer lists using quicksort. Here you can see how each of the four steps are implemented.
1fun main() { 2 // Initial unsorted list 3 val inputList: List<Int> = listOf(1, 2, 1, 60, 4, -10, 50) 4 5 // Sort the list and print it 6 println(quicksort(inputList)); 7} 8 9fun quicksort(items: List<Int>): List<Int> { 10 // Return if the input list is empty or only has 1 entry, since it's already sorted 11 if (items.size <= 1) { 12 return items 13 } 14 15 // Pick a pivot 16 val chosenItem: Int = items[items.size / 2] 17 18 // Partition items in three sets: smaller, equal and greater than chosen item 19 val smallerList: MutableList<Int> = mutableListOf() 20 val equalList: MutableList<Int> = mutableListOf() 21 val greaterList: MutableList<Int> = mutableListOf() 22 items.forEach { 23 when { 24 it < chosenItem -> smallerList.add(it) 25 it > chosenItem -> greaterList.add(it) 26 else -> equalList.add(it) 27 } 28 } 29 30 // Combine results and return 31 val sortedList: MutableList<Int> = mutableListOf() 32 sortedList.addAll(quicksort(smallerList)) // Recursive call 33 sortedList.addAll(equalList) 34 sortedList.addAll(quicksort(greaterList)) // Recursive call 35 return sortedList 36}
5. Java implementation
In a similar way as the Kotlin implementation, we also made a more object-oriented implementation. Instead of sorting a
list of numbers, we now sort a list of Person
based on their age. In the following code you'll see that there is only
a slight difference between the implementations.
Person
class:
1public class Person { 2 3 private final String name; 4 private final int age; 5 6 public Person(final String name, final int age) { 7 this.name = name; 8 this.age = age; 9 } 10 11 public String getName() { 12 return name; 13 } 14 15 public int getAge() { 16 return age; 17 } 18 19 @Override 20 public String toString() { 21 return "Person{" + 22 "name='" + name + '\'' + 23 ", age=" + age + 24 '}'; 25 } 26}
Java quicksort implementation:
1import java.util.ArrayList; 2import java.util.List; 3 4public class App { 5 6 public static void main(final String[] args) { 7 // Initial unsorted list of people 8 final List<Person> people = new ArrayList<>(); 9 people.add(new Person("Addison", 1)); 10 people.add(new Person("Joey", 2)); 11 people.add(new Person("Rory", 1)); 12 people.add(new Person("Ryan", 60)); 13 people.add(new Person("Royce", 4)); 14 people.add(new Person("Leslie", 50)); 15 16 // Sort the list of people and print it 17 System.out.println("Sorted people: " + quicksort(people)); 18 } 19 20 private static List<Person> quicksort(final List<Person> people) { 21 // Return if the input list is empty or only has 1 entry, since it's already sorted 22 if (people.size() <= 1) { 23 return people; 24 } 25 26 // Pick a pivot 27 final Person chosenItem = people.get(people.size() / 2); 28 29 // Partition items in three sets (younger, sameAge and older) 30 final List<Person> younger = new ArrayList<>(); 31 final List<Person> sameAge = new ArrayList<>(); 32 final List<Person> older = new ArrayList<>(); 33 for (final Person i : people) { 34 if (i.getAge() < chosenItem.getAge()) { 35 younger.add(i); 36 } else if (i.getAge() > chosenItem.getAge()) { 37 older.add(i); 38 } else { 39 sameAge.add(i); 40 } 41 } 42 43 // Combine results and return 44 final List<Person> sortedPeople = new ArrayList<>(); 45 sortedPeople.addAll(quicksort(younger)); // Recursive call 46 sortedPeople.addAll(sameAge); 47 sortedPeople.addAll(quicksort(older)); // Recursive call 48 return sortedPeople; 49 } 50}
6. Efficiency
Please do note that these implementations are not the most efficient ones. For example, instead of using List
, you can
use arrays of primitive int
type. And instead of using multiple lists, you can swap entries within the same array.
Complexity wise, in the worst-case scenario, quicksort runs in O(n^2)
. On average, the algorithm runs in O(n log n)
.
In the best case, the pivot divides the set in two equally sized subsets. That's why it's quite important what element
you pick as pivot. There are multiple ways in which you can pick a pivot:
- First element: Always pick the first element in the set as the pivot. This method makes sense if your input set is random. However, this method is not recommended.
- Middle element: Always pick the middle element in the set as the pivot. If your input set already is sorted, this might be the best method. Why? Because the pivot will always be the middle element and causes the two partitions to be equally sized.
- Median of three: Always pick the median of tree, meaning that you take the first, middle and last element, and then pick the median between those.
So, when choosing a pivot picking strategy, keep your input sets in mind. Are they sorted or not, are they large or small? That way you can optimize your quicksort algorithm.
This was a short introduction to the quicksort algorithm. If you want to learn more about this algorithm, we recommend you to dive deeper into the proof and correctness of the algorithm. That way you'll understand the algorithm even more.