[자료구조와 알고리즘] 유데미 강의 "JavaScript 알고리즘 & 자료구조 마스터클래스" 정리(섹션 11, 12, 13, 14: 버블, 선택, 삽입 정렬)

섹션 11: 버블 정렬

버블 정렬은-오름차순인 경우-순회하면서 가장 큰 수를 가장 뒤로 보내는 정렬 방식이다.

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

console.log(bubbleSort([9, 3, 5, 2, 1]));

 

스왑 여부를 체크하여 스왑이 일어나지 않을 경우에는 반복을 중단하여 최적화하였다.
일반적으로 O(n^2), 가능한 최고의 경우 O(n)이다.

function bubbleSort(arr) {
  let noSwaps;
  for (let i = arr.length; i > 0; i--) {
    noSwaps = true;
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // swap
        noSwaps = false;
      }
    }
    console.log(arr);
    if (noSwaps) break;
  }
  return arr;
}

console.log(bubbleSort([2, 1, 3, 5, 9]));

 

섹션 12: 선택 정렬

선택 정렬은-오름차순인 경우-순회하면서 가장 작은 수를 앞쪽으로 보내는 정렬 방식이다.

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let lowest = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[lowest] > arr[j]) {
        lowest = j;
      }
    }
    // 최소값 인덱스와 i가 같은 경우에는 스왑하지 않는 방식으로 최적화하였다.
    if (i !== lowest) {
      [arr[i], arr[lowest]] = [arr[lowest], arr[i]]; // swap
    }
  }
  return arr;
}

console.log(selectionSort([2, 1, 3, 5, 9]));

 

섹션 13: 삽입 정렬

삽입 정렬은-오름차순인 경우-순회하면서 앞쪽을 정렬된 상태로 만드는데 해당 인덱스의 값이-이미 정렬된 구간에서-자기 자리를 찾아가기 위해 스왑을 반복적으로 진행하여 정렬하는 방법이다.

강의 예제는 var의 호이스팅을 이용한 코드였다. 여기에는 var를 사용하지 않고 -임의로 작성한-let을 사용한 코드를 소개하고자 한다.

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let idx = i
        for (let j = i - 1; j >= 0; j--) {
            if (arr[j] > arr[idx]) {
                [arr[j], arr[idx]] = [arr[idx], arr[j]]
                idx--
            } else {
                break
            }
        }
    }
    return arr
}

console.log(insertionSort([2, 1, 9, 7, 4, 3]));

 

섹션 14: 버블, 선택, 삽입 정렬 비교

정렬이-거의-되어 있는 상태로 가정하여 진행한다면 버블, 삽입의 경우 O(n)의 시간 복잡도를 가질 수 있다. 

Algorithm	Time Complexity (Best)	Time Complexity (Average)	Time Complexity (Worst)	Space Complexity
Bubble Sort	O(n)	O(n2)	O(n2)	O(1)
Insertion Sort	O(n)	O(n2)	O(n2)	O(1)
Selection Sort	O(n2)	O(n2)	O(n2)	O(1)