Quick Sort

Quick Sort is an efficient, comparison-based sorting algorithm that falls under the Divide and Conquer category. It works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. This process is repeated for each sub-array until the entire array is sorted. The pivot selection and partitioning steps make Quick Sort faster than other sorting algorithms.

Algorithm

1. Partition: Select a pivot element and partition the array into two sub-arrays, one with elements less than the pivot and the other with elements greater than the pivot.
2. Sort: Recursively apply the Quick Sort algorithm to the sub-arrays.
3. Combine: The final sorted array is obtained by combining the sorted sub-arrays.

Time Complexity

The time complexity of Quick Sort depends on the choice of pivot. In the average case, Quick Sort has a time complexity of O(n log n), where n is the number of elements to be sorted. However, in the worst case, Quick Sort has a time complexity of O(n^2). To mitigate the effect of the worst-case scenario, various techniques, such as choosing a random pivot or using the Median of Three method, can be employed.

Space Complexity

Quick Sort has a space complexity of O(log n) for the recursive call stack. However, the sorting is done in-place, so the overall space complexity is O(1).

Example

1${code}

In this example, we have an array of integers arr and we first print the original array. Then, we apply the Quick Sort algorithm to sort the array in ascending order and print the sorted array.

Output:

1Original Array:
28 4 2 7 1 5 9 
3Sorted Array:
41 2 4 5 7 8 9 

xxxxxxxxxx

}

class QuickSort {

  public static void quickSort(int[] arr, int low, int high) {

    if (low < high) {

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

      quickSort(arr, low, pivotIndex - 1);

      quickSort(arr, pivotIndex + 1, high);

    }

  }

​

  public static 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++;

        swap(arr, i, j);

      }

    }

​

    swap(arr, i + 1, high);

​

    return i + 1;

  }

​

  public static void swap(int[] arr, int i, int j) {

    int temp = arr[i];

    arr[i] = arr[j];

    arr[j] = temp;