function quickSort(arr, left, right) {
  let len = arr.length,
    partitionIndex
  typeof left !== 'number' && (left = 0)
  typeof right !== 'number' && (right = len - 1)
  if (left < right) {
    partitionIndex = partition(arr, left, right)
    quickSort(arr, left, partitionIndex - 1)
    quickSort(arr, partitionIndex + 1, right)
  }
  return arr
}
function partition(arr, left, right) {
  let target = left,
    index = target + 1
  for (let i = index; i <= right; i++) {
    if (arr[i] < arr[target]) {
      swap(arr, i, index)
      index++
    }
  }
  swap(arr, target, index - 1)
  return index - 1
}
function swap(arr, i, j) {
  let temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

console.log(quickSort([12, 36, 37, 109, 39, 33, 34, 35]))

function bubbleSort(arr) {
  let len = arr.length
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1)
      }
    }
  }
  return arr
}

console.log(bubbleSort([12, 36, 37, 109, 39, 33, 34, 35]))

function insertionSort(arr) {
  let len = arr.length
  for (let i = 0; i < len; i++) {
    let target = arr[i],
      j = i - 1
    while (j >= 0 && arr[j] > target) {
      arr[j + 1] = arr[j]
      j--
    }
    arr[j + 1] = target
  }
  return arr
}

console.log(insertionSort([12, 36, 37, 109, 39, 33, 34, 35]))

function selectionSort(arr) {
  let len = arr.length,
    minIndex,
    temp
  for (let i = 0; i < len - 1; i++) {
    minIndex = i
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) minIndex = j
    }
    swap(arr, i, minIndex)
  }
  return arr
}

console.log(selectionSort([12, 36, 37, 109, 39, 33, 34, 35]))