thisyujeong.dev

JavaScript 알고리즘 & 자료구조 마스터 클래스 강의를 듣고 작성하는 강의노트

삽입 정렬 (Insertion Sort)

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교해, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

• 선택 알고리즘과 유사하지만 좀 더 효율적이다.
• 두 번째 원소부터 시작해 해당 원소를 기준으로 좌측에 나열된 원소들과 비교하고 삽입할 위치를 지정한 후 재배치한다.

정렬 과정

정렬 대상 배열: [5, 3, 4, 1, 2]

• 1회전: [5, 3, 4, 1, 2]
  • 두 번째 원소(3)와 좌측 원소를 비교해 삽입 위치를 지정하여 재배치
  • 1회전 결과: [3, 5, 4, 1, 2]
• 2회전: [3, 5, 4, 1, 2]
  • 세 번째 원소(4)와 좌측 원소들을 비교해 삽입 위치를 지정하여 재배치
  • 2회전 결과: [3, 4, 5, 1, 2]
• 3회전: [3, 4, 5, 1, 2]
  • 세 번째 원소(4)와 좌측 원소들을 비교해 삽입 위치를 지정하여 재배치
  • 3회전 결과: [1 ,3, 4, 5, 2]
• 4회전: [1, 3, 4, 5, 2]
  • 네 번째 원소(4)와 좌측 원소들을 비교해 삽입 위치를 지정하여 재배치
  • 4회전 결과: [1, 2 ,3, 4, 5]

의사코드

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;
}
 
console.log(insertionSort([4, 3, 2, 1, 5, -5, 20, 17]));

시간 복잡도

• Best: O(n)
• Worst: O(n²)
• Average: O(n²)