📋 삽입 정렬 알고리즘

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

말로만 듣는다면 어떤 방식인지 이해하기 힘들 것이다.
작동방식을 시각화한 자료를 통해 직접 확인해보자.

---

📌 1. 삽입 정렬 작동 방식

https://visualgo.net/en/sorting

배열의 두 번째 원소부터 루프를 돌며 해당 값을 이전 값과 비교해가며 알맞는 위치에 배치하고 이를 반복한다.

---

📌 2. 삽입 정렬 구현

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

---

📌 3. 삽입 정렬의 시간 복잡도

삽입 정렬의 시간 복잡도는 최상의 경우엔 O(n)이다.
하지만 이는 완벽히 정렬되어있는 경우이고 최악, 평균의 경우엔 O(n^2)의 시간 복잡도를 가진다.

이런 삽입 정렬이 유용한 흥미로운 상황이 있다.

온라인에서 실시간으로 데이터를 받고 있고 이를 모아서 정렬해야 하는 코드를 작성해야 할 때, 삽입 정렬은 배열의 한 쪽에 정렬된 부분을 두고 한 번에 하나씩 요소들을 삽입하는 방식이기 때문에 이런 경우엔 삽입 정렬이 유용하게 사용될 수 있다.

---

📌 4. 버블, 선택, 삽입 정렬 시간 복잡도 비교

지금까지 알아본 버블, 선택, 삽입 정렬 알고리즘의 시간 복잡도를 비교하는 테이블이다.

평균, 최악의 시간 복잡도는 모두 O(n^2)이고 버블과 삽입 정렬의 최상의 시간 복잡도는 O(n), 선택 정렬의 최상의 시간 복잡도는 O(n^2)인 것을 확인할 수 있다.