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);
  }
}  

Recommended Posts

Algorithm gymnastics 12
Algorithm gymnastics 10
Algorithm gymnastics 3
Algorithm gymnastics 9
Algorithm gymnastics 14
Algorithm gymnastics 2
Algorithm gymnastics 7
Algorithm Gymnastics 15
Algorithm Gymnastics 16
Algorithm gymnastics 8
Algorithm Gymnastics 17
Algorithm Gymnastics 18
Algorithm gymnastics 11
Algorithm gymnastics 5
Algorithm gymnastics 4
Algorithm Gymnastics 24 Subsets
Algorithm Gymnastics 20 Remove Duplicates
Algorithm Gymnastics 21 LinkedList Cycle
Algorithm Gymnastics 24 Cyclic Sort
Algorithm Gymnastics 19 No-repeat Substring
Algorithm Gymnastics 24 Reverse a Linked List
Python algorithm
Algorithm exercises 13
Algorithm Gymnastics 20 Pair with Target Sum
Algorithm Gymnastics 22 Squaring a Sorted Array
Algorithm Gymnastics 24 Middle of the Linked List
Python memorandum (algorithm)
Dictionary learning algorithm
String search algorithm