Quick Sort in Java

In this tutorial we will discuss on of the most efficient and programmer's choice sorting called Quick Sort. Just like its counterpart sorting, Merge Sort, its also based on Divide and Conquer paradigm.

Just like merge() method is the key which merges the two equal halves in Merge Sort, Quick Sort has a method partition() which divides the list. This method places an element at its exact position in the list, and partition the list based on the index of the element. It continues to find the exact partition in the other two parts until all the elements are placed in its exact positions.

The algorithm can be summarized as below

quickSort(arr[], low, high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[pi] is now
           at right place */
        pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);  // Before pi
        quickSort(arr, pi + 1, high); // After pi
    }
}

See the below image for better understanding

Lets get hands on by writing a small Java code for Quick Sort.

import java.util.Arrays;

class QuickSort

{

    int partition(int arr[], int low, int high)

    {

        int pivot = arr[high];

        int i = (low-1);

        for (int j=low; j<high; j++)

        {

            if (arr[j] <= pivot)

            {

                i++;

                int temp = arr[i];

                arr[i] = arr[j];

                arr[j] = temp;

            }

        }



        int temp = arr[i+1];

        arr[i+1] = arr[high];

        arr[high] = temp;



        return i+1;

    }

    void mergeSort(int arr[], int low, int high)

    {

        if (low < high)

        {

            int pi = partition(arr, low, high);

            mergeSort(arr, low, pi-1);

            mergeSort(arr, pi+1, high);

        }

    }

    public static void main(String args[])

    {

        int arr[] = {10, 7, 8, 9, 1, 5};

        QuickSort qs = new QuickSort();

        System.out.println("Array before sort " + Arrays.toString(arr));

        qs.mergeSort(arr, 0, arr.length - 1);

        System.out.println("Array before sort " + Arrays.toString(arr));

    }
}

Analysis of Quick Sort

• Time Complexity: O(nLogn) in all 3 cases (average and best) as merge sort always divides the array in two halves and take linear time to merge two halves.
• Worst Case TC: O(n*n)
• Worst Auxiliary Space: O(n)
• Algorithmic Paradigm: Divide and Conquer
• Sorting In Place: Yes
• Stable: No

Hope you guys like it. Stay tune for more updates in sorting. Please comment for any doubts.
Happy Learning !!!

SHARE

Onlinecodegeek