Quick Sort

February 21, 2021

Overview

Quick Sort is a very popular divide and conquer algorithm used for sorting collections. It works by selecting a pivot element and partition the array such that all the elements to the left of pivot are smaller that the pivot element. Quick Sort is preferred over Merge Sort as both algorithms have same run time complexity but Quick sort uses less space

Pseudo Code

Pick a pivot (usually the last element of the array) and partition the array
- Left of the pivot should be all the elements smaller than the pivot
- Right of the pivot should be all the elements larger than the pivot
After step 1 the pivot is at the correct position in the array and will not move
Repeat step 1 with the left and right of partitioned array until the entire array is sorted

Implementation

public class QuickSortBlog {
    public static void main(String[] args) {
        int[] sampleArray = { 423, 99, 1, 5, 2, 7, 8, 9, 11, 3, 5 };

        quickSort(sampleArray, 0, sampleArray.length - 1);
        System.out.println(Arrays.toString(sampleArray));
       //output: [1, 2, 3, 5, 5, 7, 8, 9, 11, 99, 423]
    }

    //Quick Sort algorithm - recursive
    private static void quickSort(int[] array, int start, int end) {
        //base condition for recursion to end
        if(start >= end)
            return;

        //partition the array such that all the elements to the left of pivot are smaller than the pivot
        var boundary = partition(array, start, end);

        //repeat sorting for the partitioned arrays
        quickSort(array, boundary + 1, end);
        quickSort(array, start, boundary - 1);
    }

    public static int partition(int[] array, int start, int end) {
        int pivot = array[end];
        int boundary = start - 1;

        for (int i = start; i <= end; i++) {
            if (array[i] <= pivot) {
                var temp = array[i];
                array[i] = array[++boundary];
                array[boundary] = temp;
            }
        }

        return boundary;
    }
}