Quick Sort in Java

May 4, 2023

Quick Sort in Java

Quick sort is a sorting algorithm, used in data structures for sorting arrays, queues, linked lists and other linear data structures. Quick sort works on the principle of Divide and Conquer. Quick sort is also known as partition-exchange sort.

Quick
Time Complexity O(n log n)
Best Case O(n log n)
Worst Case O(n2)
Space Complexity O(1)
Auxiliary Space Complexity O(log n)
In Place Yes
Stable No

Quick Sort in Java

  • Choose the pivot element.
  • Move the elements smaller to pivot in the left partition
  • Move the elements greater than pivot to the right partition
  • The partition index is discovered at the end

New pivot is then chosen in each of the partition and the above steps are repeated until partitions of one item each is reached.

Generally, pivot can be chosen as any of the following –

  • Last element
  • First element
  • Random element
  • Median element

We will choose the last element as a pivot.

Quick Sort in JAVA

Steps to implement Quick sort:

1) Choose an element, called pivot, from the list. Generally pivot can be the last index element.

2) Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it . After this partitioning, the pivot is in its final position. This is called the partition operation.

3) Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values.

Implementation of Quick Sort in JAVA

Quick Sort in Java
Quick Sort in Java continue

Program for Quick Sort in Java

Let us have a look on the program below –

Run 
//Java Program for Merge Sort
class Main {
    // this function display the array
    public static void display(int[] arr, int size)
    {
        for(int i = 0; i < size; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    // main function of the program
    public static void main(String[] args)
    {
        int[] a = {12, 11, 13, 5, 6, 7 };

        int size = a.length;
        display(a, size);

        quickSort(a, 0, size - 1);
        display(a, size);
    }
    // A utility function to swap two elements
    static void swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    //Recursive function to apply quickSort
    static void quickSort(int[] arr, int low, int high)
    {
        if (low < high)
        {
       /* indexPI is partitioning index, partition() function will
        return index of partition */
            int indexPI  = partition(arr, low, high);

            quickSort(arr, low, indexPI  - 1);  //left partition
            quickSort(arr, indexPI  + 1, high); //right partition
        }
    }
    /* Partition function to do Partition
    elements on the left side of pivot elements would be smaller than pivot
    elements on the right side of pivot would be greater than the pivot
    */
    static int partition(int[] arr, int low, int high)
    {
        // Pivot element selected as right most element in array each time.
        int pivot = arr[high];
        int swapIndex  = (low - 1);   //swapping index.

        for (int j = low; j <= high- 1; j++)
        {
            //Check if current element is smaller than pivot element.
            if (arr[j] < pivot)
            {
                swapIndex++;    //increment swapping index.
                swap(arr, swapIndex, j);
            }
        }
        // swap swapindex+ 1 and pivot index
        // we assigned pivot = arr[high] is pivot index is high
        swap(arr, swapIndex + 1, high);

        return (swapIndex + 1);
    }
}

Output

12 11 13 5 6 7 
5 6 7 11 12 13
  • This algorithm is quite efficient for large-sized data sets as its average and worst-case complexity are of Ο(n2), where n is the number of items.
  • Quick sort is more advantageous than merge sort, as in merge sort we need a temporary array to merge the sorted arrays, and hence it is not fruitful than quick sort.

Quick Sort Performance Analysis

Advantages

  • As the name suggests !!! Is quick as a horse !!
  • Reliable algorithm and used a lot in the industry

Disadvantages

  • Needs additional spaces for temporary arrays, thus space complexity is O(log n)
  • Very difficult to understand
  • If the first element is chosen as a pivot by some idiot then it causes worst-case complexity of O(n2)
Quick sort in Java

Sorting

Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.

Data Structures and Algorithm Learn Sorting