[JS] Insertion & Bubble & Selection Sort 구현하기

1. 삽입정렬(Insertion Sort)

• 2번째 요소부터 시작하여 정렬된 좌측배열과 비교하며 정렬
  완전히 무작위인 배열보다 거의 정렬되어 있는 배열에서 더 빠름

성능

• Best Case : $O(n)$
• Worst Case: $O(n^2)$
• Average Case : $O(n^2)$

구현코드

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

2. 버블정렬(Bubble Sort)

• 서로 인접한 원소를 비교하여 swap하는 정렬
  완전히 무작위인 배열보다 거의 정렬되어 있는 배열에서 더 빠름

성능

• Best Case : $O(n^2)$
• Worst Case: $O(n^2)$
• Average Case : $O(n^2)$

구현코드

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      console.log(arr, arr[j], arr[j + 1]);
      if (arr[j] > arr[j + 1]) {
        // 전통적인 swap
        // let temp = arr[j];
        // arr[j] = arr[j + 1];
        // arr[j + 1] = temp;
        //ES2015문법 swap
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
    console.log(`${i + 1}회 째 수행중입니다!!!`);
  }
  return arr;
};

3. 선택정렬(Selection Sort)

• 가장 작은 값을 맨 앞으로 보내는 정렬

성능

• Best Case : $O(n^2)$
• Worst Case: $O(n^2)$
• Average Case : $O(n^2)$

구현코드

function selectionSort(array) {
  for (let i = 0; i < array.length; i++) {
    let minIndex = i;
    for (let j = i + 1; j < array.length; j++) {
      if (array[minIndex] > array[j]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      let swap = array[minIndex];
      array[minIndex] = array[i];
      array[i] = swap;
    }
    console.log(`${i}회전: ${array}`);
  }

  return array;
}