QuickSort Visualization – Simply Explained

Posted by Marta on January 10, 2021 Viewed 10177 times

In this article, you will learn how the quicksort sorting algorithm works. I will show you step by step how this algorithm sort an array. Also, the article includes quicksort visualization and the implementation written in Java.

QuickSort is a popular algorithm often used in real-life. Its runtime on average is O(n log n). Additionally, its main advantage in comparison with mergesort is that it operates in place, meaning quicksort uses very little additional memory beyond the input array.

Let’s dive in and see how quicksort works!

Table of Contents

QuickSort Visualization

This quicksort visualization will help you get a deeper understading of the algorithm:

The below video explains how quicksort works step by step:

Algorithm Steps

Quicksort will sort an array or collection based on the idea of partition around a pivot element. The algorithm will pick a pivot element. Then it will rearrange the elements placing all items that are less than the pivot on the left of the pivot element and all elements that are greater on the right of the pivot element.

Once the partition is completed, the algorithm will split the array by the pivot element and call itself. See below the steps:

Select a pivot element
Partition the array around the pivot
Quicksort for the first part of the partition
QuickSort for the second part of the partition

Choose Pivot

The pivot is essential, and it will determine the running time of this algorithm. We could pick the first element of the array as the pivot or the last one. Both options will lead to a running time of O(n^2).

Another option is choosing a random element as the pivot every time. Although the implementation is slightly more complicated, you will achieve a better running time, therefore, a much quicker algorithm. The running time using a random pivot is O(n*log(n)).

The code snippet below illustrates how to choose a random pivot in Java:

public static int choosePivot(int begin, int end){
	return new Random().nextInt(end-begin)+begin;
}

Partitioning

Once we choose a pivot element, we have to make a partition around this element. In other words, rearranging the items in a way that:

Items less than the pivot go on the left of the pivot.
Items greater than the pivot go on the right of the pivot

We will scan the array and moving items that are less than the pivot to the left. To achieve this, we can use two indexes. One index keeps track of the elements already visited, called j. And the other index, called i, keeps track of the less than the pivot items. Watch the quicksort visualization video above to get a detailed explanation of how this code works:

See below how to make the partition in Java:

    public static PartitionResult partition(int[] array, int begin, int end){
        int pivotIndex = choosePivot(begin, end);
        int pivotValue = array[pivotIndex];
        int i = begin;// keep track items that are less then pivot
        
        for( int j= begin;j<end;j++){
            if(array[j]<pivotValue){
                // in case the pivot need to move
                if(array[i]==pivotValue){
                    pivotIndex=j;
                }
                int aux = array[j];
                array[j]=array[i];
                array[i]=aux;
                i++;
            }
        }
        int aux = array[i];
        array[i]=pivotValue;
        array[pivotIndex]=aux;

        return new PartitionResult(array,i);
    }
	static class PartitionResult{
        public int[] array;
        public int pivotIndex;

        PartitionResult(int[] array, int pivotIndex){
            this.array = array;
            this.pivotIndex = pivotIndex;
        }
    }

QuickSort in Java

And finally, once you choose the pivot and make the partition, the final step is calling the quicksort method recursively on the two resulting parts. See this in action below in Java:

public static int[] quicksort(int[] array,int begin,int end){
        PartitionResult partitionResult = null;
        if(end-begin>1) { // if the array is bigger than 1

            partitionResult = partition(array, begin, end);
            array = quicksort(partitionResult.array, begin , partitionResult.pivotIndex);
            array = quicksort(array, partitionResult.pivotIndex+1 , end);

        }
        return array;

}

Full Java Implementation

package quicksort;

import java.util.Random;

public class QuickSortAlg {

    public static void main(String[] args){
        int[] array = {3,2,4,6,5,1};
        printArray(array);
        array = quicksort(array,0,array.length);
        printArray(array);
    }

    public static int[] quicksort(int[] array,int begin,int end){
        PartitionResult partitionResult = null;
        if(end-begin>1) { // if the array is bigger than 1

            partitionResult = partition(array, begin, end);
            array = quicksort(partitionResult.array, begin , partitionResult.pivotIndex);
            array = quicksort(array, partitionResult.pivotIndex+1 , end);

        }
        return array;

    }


    public static PartitionResult partition(int[] array, int begin, int end){
        int pivotIndex = choosePivot(begin, end);
        int pivotValue = array[pivotIndex];
        // keep track of up to where is ordered
        int i = begin;
        for( int j= begin;j<end;j++){
            if(array[j]<pivotValue){
                // in case the pivot need to move
                if(array[i]==pivotValue){
                    pivotIndex=j;
                }
                int aux = array[j];
                array[j]=array[i];
                array[i]=aux;
                i++;
            }
        }
        int aux = array[i];
        array[i]=pivotValue;
        array[pivotIndex]=aux;

        return new PartitionResult(array,i);
    }

    public static int choosePivot(int begin, int end){
        return new Random().nextInt(end-begin)+begin;
    }

    public static void printArray(int[] array){
        StringBuilder builder = new StringBuilder("{");
        for(int val: array){
            builder.append(val).append(",");
        }
        builder.append("}");
        System.out.println(builder.toString());
    }

    static class PartitionResult{
        public int[] array;
        public int pivotIndex;

        PartitionResult(int[] array, int pivotIndex){
            this.array = array;
            this.pivotIndex = pivotIndex;
        }
    }
}

Source Code available in Github

Conclusion

In conclusion, the quicksort algorithm that will sort an array using pivot and partition key idea. We have seen step by step how quicksort sorts the array. First, select a pivot, make a partition around the pivot, and then calling the algorithm recursively on the resulting parts. Plus, using a random pivot enable the algorithm to achieve running time O(n*log(n)).

I hope this article was useful, and thanks for reading and supporting this blog. happy coding! 🙂

QuickSort Visualization – Simply Explained

QuickSort Visualization

Algorithm Steps

Choose Pivot

Partitioning

QuickSort in Java

Full Java Implementation

Conclusion

More Interesting Articles

Project-Based Programming Introduction

100% Recommended book for Java Beginners

90 Specific Ways to Write Better Python

Grow Your Java skills as a developer

Write Code as a Professional Developer

Every Developer should read this

Great preparation for interviews