Posted by Marta on January 10, 2021 Viewed 7875 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!

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

The below video explains how quicksort works step by step:

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**

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; }

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; } }

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; }

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

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! ðŸ™‚

Steady pace book with lots of worked examples. Starting with the basics, and moving to projects, data visualisation, and web applications

Unique lay-out and teaching programming style helping new concepts stick in your memory

Great guide for those who want to improve their skills when writing python code. Easy to understand. Many practical examples

Perfect Boook for anyone who has an alright knowledge of Java and wants to take it to the next level.

Excellent read for anyone who already know how to program and want to learn Best Practices

Perfect book for anyone transitioning into the mid/mid-senior developer level

Great book and probably the best way to practice for interview. Some really good information on how to perform an interview. Code Example in Java