[JavaScript] 삽입정렬

삽입 정렬 (Insertion Sort)

삽입 정렬은 각 요소를 적절한 위치에 삽입하며 정렬하는 방식으로 동작하는 간단한 정렬 알고리즘입니다.
카드 게임에서 손에 들고 있는 카드를 정렬하는 방식과 비슷하다고 생각하면 됩니다.

---

동작 원리

1. 배열의 두 번째 요소부터 시작합니다.
2. 현재 요소를 이전 요소들과 비교하여, 적절한 위치에 삽입합니다.
3. 이 과정을 배열 끝까지 반복하여 정렬을 완성합니다.

---

장단점

• 장점:
  • 데이터가 거의 정렬되어 있는 경우 매우 빠르며, 최선의 경우 O(n)O(n)O(n)입니다.
  • 추가 메모리를 사용하지 않는 **제자리 정렬 (In-Place Sort)**입니다.
• 단점:
  • 데이터가 정렬되어 있지 않을 때는 비교와 이동이 많아져 O(n2)O(n^2)O(n2)의 성능을 보입니다.
• 적합한 경우:
  • 데이터 크기가 작거나, 이미 정렬에 가까운 데이터 정렬 시 적합합니다.

---

삽입 정렬 구현 (JavaScript)

1. 오름차순 삽입 정렬

const insertionSort = (array) => {
  const arr = array.slice(); // 원본 배열 복사
  const n = arr.length;

  for (let i = 1; i < n; i++) { // 두 번째 요소부터 시작
    let current = arr[i]; // 현재 정렬하려는 값
    let j = i - 1;

    // 현재 값이 이전 값보다 작으면 위치를 변경
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j]; // 값을 오른쪽으로 이동
      j--;
    }
    arr[j + 1] = current; // 올바른 위치에 삽입
  }

  return arr;
};

const an = [5, 1, 4, 2, 8];
console.log(insertionSort(an)); // [1, 2, 4, 5, 8]

 

2. 내림차순 삽입 정렬

const insertionSortDesc = (array) => {
  const arr = array.slice();
  const n = arr.length;

  for (let i = 1; i < n; i++) {
    let current = arr[i];
    let j = i - 1;

    // 내림차순 정렬: 현재 값이 이전 값보다 크면 위치 변경
    while (j >= 0 && arr[j] < current) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current;
  }

  return arr;
};

const an = [5, 1, 4, 2, 8];
console.log(insertionSortDesc(an)); // [8, 5, 4, 2, 1]

 

삽입 정렬 동작 예시

배열: [5, 1, 4, 2, 8] (오름차순 정렬)

1단계 (i = 1):

• 현재 값: 1
• 비교: 1 < 5 → 위치 변경
• 결과: [1, 5, 4, 2, 8]

2단계 (i = 2):

• 현재 값: 4
• 비교: 4 < 5 → 위치 변경
• 결과: [1, 4, 5, 2, 8]

3단계 (i = 3):

• 현재 값: 2
• 비교: 2 < 5 → 위치 변경
• 비교: 2 < 4 → 위치 변경
• 결과: [1, 2, 4, 5, 8]

4단계 (i = 4):

• 현재 값: 8
• 비교: 8 > 5 → 그대로
• 결과: [1, 2, 4, 5, 8]

---

시간 복잡도

• 최선의 경우 (정렬된 배열): O(n)O(n)O(n)
• 평균/최악의 경우: O(n2)O(n^2)O(n2)
  • 매번 삽입 위치를 찾기 위해 최대 nnn번 비교해야 하기 때문.

 

---

한 줄 요약

삽입 정렬은 현재 값을 정렬된 부분의 올바른 위치에 삽입하는 정렬로, 작은 데이터셋에 효율적이고 구현이 간단합니다. 😊