Quicksort algorithm introduced - with Java and Kotlin examples

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:

1. If S is empty or only has one entry: return.
2. Pick an element v in S, the pivot.
3. Partition S in two disjoint sets L and R, such that L only contains elements that are lesser than the pivot v, and R contains only contains elements that are greater than the pivot v.
4. Repeat this algorithm for L and R. 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.

Insertion sort introduced - With Java and Kotlin examples

Dijkstra's algorithm introduced - With Java and Kotlin examples

Singleton design pattern in Java and Kotlin

Full guide to deploy your Play Framework app on Ubuntu 20.04