'use strict'

const nums = [3, 0, 2, 5, 1, 3, 0]
quicksort(nums, 0, nums.length - 1)
console.log(nums)

const chars = ['z', 'a', 'u', 'f', 'f', 'A']
quicksort(chars, 0, chars.length - 1)
console.log(chars)

// quicksort is at worst O(n^2), on averago O(n log n)
//
// TODO implement a better way of choosing pivot point in order to
// reduce the chance that the pivot will be the highest or lowest
// value in the element, which would cause it to run be O(n^2)
function quicksort (arr, lo, hi) {
  if (lo < hi) {
    const pivotIndex = partition(arr, lo, hi)
    quicksort(arr, lo, pivotIndex - 1) // sort the low partition
    quicksort(arr, pivotIndex + 1, hi) // sort the high partition
  }
}

function partition (arr, lo, hi) {
  const pivot = arr[hi] // the element to compare against
  let wall = lo // the index to swap at

  for (let i = lo; i < hi; i++) {
    // if the current element is less than the pivot, swap it with the
    // index at wall and move the wall over by one
    if (arr[i] < pivot) {
      swap(arr, i, wall)
      wall++
    }
  }

  swap(arr, hi, wall)
  return wall
}

function swap (arr, i, j) {
  const tmp = arr[i] // swap in-place O(1)
  arr[i] = arr[j]
  arr[j] = tmp
}