Algorithm gymnastics 9

Quick Sort

Description

Quick sort is an algorithm that uses the famous "Divide and Conquer" sort algorithm. It's so famous that if you haven't heard of what Quick Sort is, here for reference.

Solution

Runtime Complexity O（nlogn) If you choose pivot as the leftmost of the array

1. The array is already sorted in the same order
2. The array is already sorted in reverse order
3. All elements are the same Except for these three conditions, it is O (nlogn), but if you happen to encounter this condition, it will be O (n ^ 2).

Memory Complexity O(logn) Sort the right side and the left side separately from the pivot. At this time, since a recursive function is used It is O (logn) because it consumes memory on the stack.

Rough algorithm flow

1. Select a pivot element from the array. Select the first element of the array as Pivot.
2. Swap so that values smaller than Pivot are on the left side of Pivot and values larger than Pivot are on the right side of Pivot.
3. You can recursively sort the right and left subarrays of Pivot.

Implementation

quickSort.java

class quickSort{

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

    int pivot_value = arr[low];
    int i = low;
    int j = high;

    while (i < j) {
      while( i <= high && arr[i] <= pivot_value) i++;
      while(arr[j] > pivot_value) j--;

      if (i < j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
    
    arr[low] = arr[j];
    arr[j] = pivot_value;

    return j;
  }
  
  public void quick_sort_recursive(int[] arr, int low, int high) {
    if (low < high) {
      int pivot = partition(arr, low, high);
      quick_sort_recursive(arr, low, pivot - 1);
      quick_sort_recursive(arr, pivot + 1, high);
    }
  }

  public void quick_sort(int[] arr) {
    quick_sort_recursive(arr, 0, arr.length - 1);
  }
}