선택 정렬

선택 정렬(Selection Sort)는 최솟값을 선택해서 가장 앞으로 보내는 방식의 정렬 알고리즘이다.

• 시간 복잡도: O(N^2)

let selectionSort = (arr) => {
  let minIdx, temp;
  for (let i = 0; i < arr.length; i++) {
    minIdx = i;
    for (let j = i+1; j < arr.length; j++) {
      if (arr[minIdx] > arr[j]) {
        minIdx = j;
      }
    }
    // 최솟값이 변경되면 swap
    if (minIdx !== i) {
      temp = arr[minIdx];
      arr[minIdx] = arr[i];
      arr[i] = temp;
    }
  }
  return arr;
}

버블 정렬

버블 정렬(Bubble Sort)는 옆에 있는 값과 비교해서 더 작은 값을 앞으로 당기는 방식의 정렬 알고리즘이다.

• 시간 복잡도: O(N^2)

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

삽입 정렬

삽입 정렬(Insertion Sort)는 각 숫자를 적절한 위치에 삽입하는 방식의 정렬 알고리즘이다. 정렬할 필요가 있을 경우에만 삽입을 진행하기 때문에 대체로 정렬된 상태에 한정해서는 어떤 정렬 알고리즘보다 빠르다.

• 시간 복잡도: O(N^2)

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