자바스크립트로 구현해보는 다양한 정렬

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

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

function insertionSort(arr) {
  const result = [...arr]

  for (let i = 1; i < result.length; i++) {
    let temp = result[i]
    let aux = i - 1

    // 배열 요소가 0보다 같거나 크고, 왼쪽 값이 더 클 때마다 계속해서 바꿔 나간다.
    while (aux >= 0 && result[aux] > temp) {
      result[aux + 1] = result[aux]
      aux--
    }

    result[aux + 1] = temp
  }

  return result
}

function quickSort(array) {
  if (array.length < 2) {
    return array
  }

  const pivot = [array[0]]
  const left = []
  const right = []

  for (let i = 1; i < array.length; i++) {
    if (array[i] < pivot) {
      left.push(array[i])
    } else if (array[i] > pivot) {
      right.push(array[i])
    } else {
      pivot.push(array[i])
    }
  }
  return [quickSort(left).concat(pivot, quickSort(right))].flat(Infinity)
}

function mergeSort(arr) {
  // 이미 배열 한개짜리는 정렬되었다.
  if (arr.length === 1) return arr

  const middleIndex = Math.floor(arr.length / 2)
  const left = arr.slice(0, middle)
  const right = arr.slice(middle)

  return merge(mergeSort(left), mergeSort(right))
}

function merge(left, right) {
  const result = []
  let leftIndex = 0
  let rightIndex = 0

  while (leftIndex < left.length && rightIndex < right.index) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex])
      leftIndex++
    } else {
      result.push(right[rightIndex])
      rightIndex++
    }
  }

  return [...result, ...left.slice(leftIndex), ...right.slice(rightIndex)]
}