
Quicksort algorithm introduced - with Java and Kotlin examples
2020-10-27 12:35:48.6509461. 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.
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.
fun main() {
// Initial unsorted list
val inputList: List<Int> = listOf(1, 2, 1, 60, 4, -10, 50)
// Sort the list and print it
println(quicksort(inputList));
}
fun quicksort(items: List<Int>): List<Int> {
// Return if the input list is empty or only has 1 entry, since it's already sorted
if (items.size <= 1) {
return items
}
// Pick a pivot
val chosenItem: Int = items[items.size / 2]
// Partition items in three sets: smaller, equal and greater than chosen item
val smallerList: MutableList<Int> = mutableListOf()
val equalList: MutableList<Int> = mutableListOf()
val greaterList: MutableList<Int> = mutableListOf()
items.forEach {
when {
it < chosenItem -> smallerList.add(it)
it > chosenItem -> greaterList.add(it)
else -> equalList.add(it)
}
}
// Combine results and return
val sortedList: MutableList<Int> = mutableListOf()
sortedList.addAll(quicksort(smallerList)) // Recursive call
sortedList.addAll(equalList)
sortedList.addAll(quicksort(greaterList)) // Recursive call
return sortedList
}
5. Java implementation
In a similar way as to 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:
public class Person {
private final String name;
private final int age;
public Person(final String name, final int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
@Override
public String toString() {
return "Person{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}
Java quicksort implementation:
import java.util.ArrayList;
import java.util.List;
public class App {
public static void main(final String[] args) {
// Initial unsorted list of people
final List<Person> people = new ArrayList<>();
people.add(new Person("Addison", 1));
people.add(new Person("Joey", 2));
people.add(new Person("Rory", 1));
people.add(new Person("Ryan", 60));
people.add(new Person("Royce", 4));
people.add(new Person("Leslie", 50));
// Sort the list of people and print it
System.out.println("Sorted people: " + quicksort(people));
}
private static List<Person> quicksort(final List<Person> people) {
// Return if the input list is empty or only has 1 entry, since it's already sorted
if (people.size() <= 1) {
return people;
}
// Pick a pivot
final Person chosenItem = people.get(people.size() / 2);
// Partition items in three sets (younger, sameAge and older)
final List<Person> younger = new ArrayList<>();
final List<Person> sameAge = new ArrayList<>();
final List<Person> older = new ArrayList<>();
for (final Person i : people) {
if (i.getAge() < chosenItem.getAge()) {
younger.add(i);
} else if (i.getAge() > chosenItem.getAge()) {
older.add(i);
} else {
sameAge.add(i);
}
}
// Combine results and return
final List<Person> sortedPeople = new ArrayList<>();
sortedPeople.addAll(quicksort(younger)); // Recursive call
sortedPeople.addAll(sameAge);
sortedPeople.addAll(quicksort(older)); // Recursive call
return sortedPeople;
}
}
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(n2)
. 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.