[Sort] 정렬 알고리즘

// Time: O(n^2) & Space: O(1)
function bubble(arr) {
  for (let i=0; i<arr.length; i++) {
    for (let j=0; j<arr.length; j++) {
      if (arr[j] > arr[j+1]) {
        const temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
  return arr;
}

// Time: O(n^2) & Space: O(1)
function selectionSort(array) {
  const length = array.length;
  for(let i = 0; i < length; i++){
    // set current index as minimum
    let min = i;
    let temp = array[i];
    for(let j = i+1; j < length; j++){
      if (array[j] < array[min]){
        //update minimum if current is lower that what we had previously
        min = j;
      }
    }
    array[i] = array[min];
    array[min] = temp;
  }
  return array;
}

// Time: O(n^2) & Space: O(1)

function insertionSort(array) {
  const length = array.length;
	for (let i = 0; i < length; i++) {
		if (array[i] < array[0]) {
      //move number to the first position
      array.unshift(array.splice(i,1)[0]);
    } else {
      // only sort number smaller than number on the left of it. This is the part of insertion sort that makes it fast if the array is almost sorted.
      if (array[i] < array[i-1]) {
        //find where number should go
        for (var j = 1; j < i; j++) {
          if (array[i] >= array[j-1] && array[i] < array[j]) {
            //move number to the right spot
            array.splice(j,0,array.splice(i,1)[0]);
          }
        }
      }
    }
  }
}

// Time: O(nlogn) & Space: O(n)

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

function mergeSort (array) {
  if (array.length === 1) {
    return array
  }
  // Split Array into left and right
  const length = array.length
  const middle = Math.floor(length / 2)
  const left = array.slice(0, middle)
  console.log("L: ", left)
  const right = array.slice(middle)
  console.log("R: ", right)
  return merge(
    mergeSort(left),
    mergeSort(right)
  )
}

function merge(left, right){
  const arr = []
  let leftIndex = 0
  let rightIndex = 0
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      arr.push(left[leftIndex])
      leftIndex++
    } else {
      arr.push(right[rightIndex])
      rightIndex++
    }
  }
  return arr.concat(left.slice(leftIndex)).concat(right.slice(rightIndex))
}