Quick Sort : -

1. Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays.

2. A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value.

3. Quicksort partitions an array and then calls itself recursively twice to sort the two resulting subarrays.

4. This algorithm is quite efficient for large-sized data sets as its average and worst-case complexity are $O(n^2)$, respectively.

Algorithm for Quick Sort : -

Step 1 − Choose the highest index value has pivot.

Step 2 − Take two variables to point left and right of the list excluding pivot.

Step 3 − left points to the low index.

Step 4 − right points to the high.

Step 5 − while value at left is less than pivot move right.

Step 6 − while value at right is greater than pivot move left.

Step 7 − if both step 5 and step 6 does not match swap left and right.

Step 8 − if left ≥ right, the point where they met is new pivot.

Complexity Analysis of Quick Sort : -

Best case Time Complexity :-

The best case scenario occurs when the partitions are as evenly balanced as possible, i.e their sizes on either side of the pivot element are either are equal or are have size difference of 1 of each other.

1. Case 1: The case when sizes of sublist on either side of pivot becomes equal occurs when the subarray has an odd number of elements and the pivot is right in the middle after partitioning. Each partition will have (n-1)/2 elements.

2. Case 2: The size difference of 1 between the two sublists on either side of pivot happens if the subarray has an even number, n, of elements. One partition will have n/2 elements with the other having (n/2)-1.

The best-case complexity of the quick sort algorithm is O(n logn).

Worst case Time Complexity :-

This happens when we encounter the most unbalanced partitions possible, then the original call takes n time, the recursive call on n-1 elements will take (n-1) time, the recursive call on (n-2) elements will take (n-2) time, and so on. The worst case time complexity of Quick Sort would be $O(n^2)$.

Space complexity of Quick Sort :-

The space complexity is calculated based on the space used in the recursion stack. The worst case space used will be O(n) . The average case space used will be of the order O(log n). The worst case space complexity becomes O(n), when the algorithm encounters its worst case where for getting a sorted list, we need to make n recursive calls.

Program Implementation of Quick Sort :-

import java.util.Arrays;

class Quicksort {

  // method to find the partition position
  static int partition(int array[], int low, int high) {

    // choose the rightmost element as pivot
    int pivot = array[high];

    // pointer for greater element
    int i = (low - 1);

    // traverse through all elements
    // compare each element with pivot
    for (int j = low; j < high; j++) {
      if (array[j] <= pivot) {

        // if element smaller than pivot is found
        // swap it with the greatr element pointed by i
        i++;

        // swapping element at i with element at j
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
      }

    }

    // swapt the pivot element with the greater element specified by i
    int temp = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp;

    // return the position from where partition is done
    return (i + 1);
  }

  static void quickSort(int array[], int low, int high) {
    if (low < high) {

      // find pivot element such that
      // elements smaller than pivot are on the left
      // elements greater than pivot are on the right
      int pi = partition(array, low, high);

      // recursive call on the left of pivot
      quickSort(array, low, pi - 1);

      // recursive call on the right of pivot
      quickSort(array, pi + 1, high);
    }
  }
}

// Main class
class Main {
  public static void main(String args[]) {

    int[] data = { 8, 7, 2, 1, 0, 9, 6 };
    System.out.println("Unsorted Array");
    System.out.println(Arrays.toString(data));

    int size = data.length;

    // call quicksort() on array data
    Quicksort.quickSort(data, 0, size - 1);

    System.out.println("Sorted Array in Ascending Order: ");
    System.out.println(Arrays.toString(data));
  }
}