#algorithm #sort

idea

Not stable. Can be more performant than merge sort.

Between $O(n^2)$ and $O(n \times log(n))$

links

Merge sort

references

https://en.wikipedia.org/wiki/Quicksort

https://www.geeksforgeeks.org/quick-sort/?ref=lbp

Reference implementation

function quickSortRec(array, low, high) {
  if (high <= low) {
    return
  }
  const pivot = partition(array, low, high)
  quickSortRec(array, low, pivot - 1)
  quickSortRec(array, pivot + 1, high)
}

function partition(array, low, high) {
  const pivot = array[high]
  let i = low - 1
  for (let j = low; j < high; j++) {
    if (array[j] < pivot) {
      i++
      swap(array, i, j)
    }
  }
  swap(array, i + 1, high)
  return i + 1
}

function swap(array, i, j) {
  const tmp = array[i]
  array[i] = array[j]
  array[j] = tmp
}

function quickSort(array) {
  quickSortRec(array, 0, array.length - 1)
}

const array = [3, 4, 1, 9, 0, 2, 7, 33, 11]
quickSort(array)
console.log(array)