QuickSort Algorithm

In this post, we will look in to the Quicksort in Java and its different implementations. Like Mergesort, Quicksort is a Divide and Conquer algorithm.

 

1.  Quicksort Algorithm

Quicksort algorithm is one of the most used sorting algorithm based on the Divide-and-Conquer algorithm. It work by dividing the input in the 2 sub problems and sorting the both side recursively. This algorithm picks one of the element as Pivot and partition the input around the Pivot. There are different variations of choosing the Pivot element:

  1. Choose the first element as Pivot.
  2. Last element as Pivot.
  3. Random element as Pivot.

The core concept of Quicksort algorithm is the partition logic. Once we pick the Pivot element, we group the input into 2 parts and place the Pivot on the correct position so that

  • All elements less than pivot are on the left-hand side of the pivot.
  • All element greater than pivot will be on the right-hand side.

We sort the both side recursively by repeating the above step (Choose Pivot and put Pivot in the correct position). Before we get in to the Quicksort implementation, let’s see how this work using one example. Let’s take this array as an input:

Quicksort algorithm

Let’s choose the Pivot element, in this example, we will choose last element as a pivot. Once we choose the pivot, we will position the pivot element to its correct position so as all element less than pivot are on the left-hand side while element greater than the pivot element are on the right-hand side. On the first iteration, this is how our array look like:

Quicksort partition

We know this process as Partitioning and it’s the core concept of the Quicksort algorithm. There are multiple ways to partition the input. In our example, we will start with the following steps

  1. Take position index which keep trek of the last item swapped.
  2. We start from the left side and will push the element to the left if less than pivot else to the right side.
  3. Process will go till the end of the input.
  4. As the last step, we will swap the pivot with the last swap item index. (This step moves the pivot to its sorted position)

Let’s see this in action:

quicksort_partition

[pullquote align=”normal”]Pay close attention to the pIndex position. Once we swapped the elements, we incremented the pIndex so trek the next element which should be moved to the right of pivot. [/pullquote]

We repeat this process we reach at the end. Once we reach at the end, we swap the pivot element with the pIndex to move the pivot to its sorted position (Pivot is at the sorted element and we left with sorting the right and left side of the pivot)

QuickSort_2

1.1  Recursive Sorting

With Quicksort, we recursively sort the left and right side of the input by selecting the new pivot element and sorting this pivot to its correct position. At the end of each iteration, we recursively sorting the left and right side of the input.

QuickSort in Java

 

2. Pseudo Code

Let’s look in to the pseudo-code if you want to implement the Quicksort in Java:

quickSort(array[] input, start, end){
    if(start < end){  // we only want to run it till we are not at the end of the input
        position = partition(input, start, end); // position show the correct place for the pivot element 
        quickSort(input, start, position-1); // we will recursively sort the left side of the pivot
        quickSort(input, position+1, end)  // sort the right side of pivot
    }
}
/**
 * partition is the core of the quick sort algorithm
 */
partition(array[] a, start, end){
    pivot = a[end]; // we picked the last element as pivot
    pIndex = low;
    for(i = start; i<=end-1; i++){
        if(a[i] <pivot){
            swap(a[pIndex], a[i]);
            pIndex++; // we moved the position to next element
        }
    }
    // when reached at the end, let's swap the pivot and pInex
    swap(pivot,pindex);
    return pIndex;
}

 

3. Quicksort in Java

Let’s see Quicksort in Java by choosing the last element as the pivot element.

public class QucikSortAlgo {

    public static void main(String[] args) {

      int[] array = {17,41,5,22,54,6,29,3,13}; // initial input
      array = quickSort(0, array.length-1,array);

     for (int i =0; i< array.length; i++){
        System.out.println(array[i]); // print the response
    }
    
  }

    /** 
     * The main quickSort method
     * */  
    public static int[] quickSort(int start, int end, int[] array){

        if(start < end){
            // keep in mind that once we have the partition, pivot is already in the correct sorted position
            int partition = partitionPoint(start,end,array); // find the correct position for the pivot

            quickSort(start, partition-1, array); // recursively call the quick sort for the left had side of the pivot
            quickSort(partition+1, end,array);  // sort right hand side of the pivot
        }
        return array;
    }

    public static int partitionPoint(int start, int end, int[] array){

        int pivot = array[end]; // choose the last element as pivot
        int swapPosition = start;
        for(int i=start; i<= end - 1; i++){
            /**
             * if value at i is less than pivot, 
             * swap the ith position with the swapPosition and incriment the swapPosition to next element.
             */
            if(array[i] <= pivot){
                swapElements(swapPosition, i, array);
                swapPosition ++;
            }
        }
        /* At the end swap the pivot with the swapposition.
        This will move the pivot element to sorted position */
        swapElements(swapPosition,end,array); 
        return swapPosition;
    }

    /**
     * Swap the element in the position
     */
    public static void swapElements(int position1, int position2, int[] array){
        int temp = array[position1];
        array[position1] = array[position2];
        array[position2] = temp;
    }
}

 

4. Algorithm Analysis

Let’s take a quick look at the time and space complexity of the Quicksort algorithm:

 

4.1 Time Complexity

Quicksort works similar to the merge sort algorithm and recursively breaking the input in small sub problems. In the best case, it will split the input in two 2 equal half. Let’s see the time complexity for worst and best case.

Worst Case: In the worst case, partition might always pick the largest or smallest element from the input. In our example last element always picked as pivot element. This can happen if we sort the input array in increasing or decreasing order. In the worst case it’s possible for the complexity to get as high as O<(n2.

TC(n) = TC(0) + TC(n-1) +(n)

Best Case: In the best case, the partition process always pick the middle element as Pivot. The best-case time and average case complexity of Quicksort is O(nLogn).

 

4.2 Space Complexity

Quicksort is an in-place algorithm. This means, it does not need any extra array or data structure to store the intermediate results. This algorithm has a space complexity of O(n) where there are O(n) recursive calls (Worst case).

 

4.3 QuickSort vs MergeSort

Both Quicksort and Mergesort algorithm have an average time complexity of O(n log n). but Quicksort is a preferred sorting algorithm for sorting Arrays. Here are some points which makes Quicksort a preferred sorting algorithm for Arrays.

    1. It is an in place sorting algorithm (Don’t need any extra storage).
    2. Allocating or reallocating the Array is expensive (especially with big input) and add extra running time. Time take to copy the array to the new Array, etc.
    3. Quick Sort is a cache friendly sorting algorithm.
    4. Mergesort is a preferred sorting algorithm for the Linked-list. 

 

5. Sorting With First Element as Pivot

Let’s see another variation of the Quicksort algorithm by selecting the first element as Pivot

public class QuckSortFirstElement{

    public static void main(String[] args){
        int[] input = {3,1,9,8,2,7,1,21,5,101,1};
        quickSort(0, input.length-1, input);
        for(int i=0; i< input.length; i++){
            System.out.println(input[i]);
        }
    }

    protected static void quickSort(int start, int end, int[] a){
        if(start<end){
            int index=partition(start,end,a);
            quickSort(start,index-1,a);
            quickSort(index+1,end,a);
        }
        return;
    }

    protected static int partition(int start, int end, int[] a){
        int p = start;
        int i = start;
        int j= end;

        while (i< j){
            while(a[i]<= a[p] && i< end){
                i++;
            }
            while(a[j]> a[p] && j > start){
                j--;
            }
            if(i< j){
                swap(i,j,a);
            }
        }
        swap(j,p,a);
        return j;
    }

    private static void swap(int p1, int p2, int[] a){
        int temp = a[p1];
        a[p1] = a[p2];
        a[p2] = temp;
    }

}

 

6. Quicksort – Randomization

The worst case time complexity for the Quicksort is O(n2). We can work on the randomization version of Quicksort algorithm where the expected time complexity is O(nLogn). Here is one of the variation of the randomized Quicksort algorithm.

  • Swap the random pivot with the last item and start the sorting as explained in the first section.
  • After every iteration, swap the last item (Pivot element) with the swap index to move the pivot to the correct position.

Let’s see the code in action:

public class QuickSortRandom{

    public static void main(String[] args){
        int[] input = {3,1,11,8,21,2,6,12,103,3};
        quickSort(0, input.length-1, input);
        for(int i =0 ; i< input.length; i++){
            System.out.println(input[i]);
        }
    }

    public static void quickSort(int start, int end, int[] a){
        if(start<end) {
            int index = partition(start, end, a);
            quickSort(start, index - 1, a);
            quickSort(index + 1, end, a);
        }
        return;
    }

    protected static int partition(int start, int end, int[] a){
        Random rand = new Random();
        int median = rand.nextInt(end-start)+start;
        int pIndex=start;
        swap(median,end,a);
        int pivot = end;
        for(int i=start; i<= end-1; i++){
            if(a[i] <= a[pivot]){
                swap(i, pIndex, a);
                pIndex++;
            }
        }

        swap(pivot, pIndex,a);
        return pIndex;
    }

    protected static void swap(int s1, int s2, int[] a){
        int temp =a[s1];
        a[s1] = a[s2];
        a[s2] = temp;
    }
}

 

Summary

In this article, we saw the Quicksort in Java. We discussed the different variations of the Quicksort algorithms. This is a very efficient algorithm and used in multiple places. At the end of our article, we learned the randomized version of Quicksort where the expected time complexity is O(nLogn) and not O(n2) for most cases.