[알고리즘] 삽입 정렬 [Insertion Sort]

[알고리즘] 삽입 정렬 [Insertion Sort]

삽입 정렬은 카드 게임을 할 때 손에 든 카드를 정렬하는 방식과 유사한 간단한 정렬 알고리즘입니다.

이 알고리즘은 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하는 방식으로 작동합니다.

 

 

 

삽입 정렬의 작동 방식

1. 두 번째 원소부터 시작합니다.
2. 현재 원소를 이전의 원소들과 비교합니다.
3. 현재 원소보다 큰 원소를 만나면, 그 원소를 오른쪽으로 이동시킵니다.
4. 작은 원소를 만나거나 배열의 시작에 도달하면, 현재 원소를 그 위치에 삽입합니다.
5. 이 과정을 배열의 마지막 원소까지 반복합니다.

 

 

 

 

예시 1

배열 [5, 2, 4, 6, 1, 3]을 오름차순으로 정렬

 

1단계: [5, 2, 4, 6, 1, 3] (2를 5 앞으로 이동)

2단계: [2, 5, 4, 6, 1, 3] (4를 5 앞으로 이동)

3단계: [2, 4, 5, 6, 1, 3] (6은 이미 올바른 위치에 있음)

4단계: [1, 2, 4, 5, 6, 3] (1을 맨 앞으로 이동)

5단계: [1, 2, 3, 4, 5, 6] (3을 4 앞으로 이동)

 

 

 

예시 2

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

// 사용 예
const arr = [5, 2, 4, 6, 1, 3];
console.log("정렬 전:", arr);
console.log("정렬 후:", insertionSort(arr));

 

 

 

 

 

삽입 정렬의 특징

시간 복잡도

• 최악의 경우: O(n^2) (역순으로 정렬된 배열)
• 최선의 경우: O(n) (이미 정렬된 배열)
• 평균: O(n^2)

• 공간 복잡도: O(1) - 추가 메모리를 거의 사용하지 않습니다.
• 안정성: 안정 정렬입니다. (동일한 값의 상대적 위치가 유지됨)

 

장점

• 구현이 간단합니다.
• 작은 데이터셋에 효율적입니다.
• 거의 정렬된 배열에 대해 매우 효율적입니다.
• 다른 복잡한 정렬 알고리즘의 일부로 사용되기도 합니다.

 

단점

• 큰 데이터셋에서는 비효율적일 수 있습니다.

 

 

 

 

결론

삽입 정렬은 간단하면서도 효과적인 정렬 알고리즘입니다.

특히 거의 정렬된 데이터나 작은 데이터셋에 대해 뛰어난 성능을 보입니다.

또한, 온라인 알고리즘으로도 사용할 수 있어, 데이터가 실시간으로 들어오는 상황에서도 유용합니다.

비록 대규모 데이터에 대해서는 퀵 정렬이나 병합 정렬 같은 더 효율적인 알고리즘들이 있지만,

삽입 정렬은 그 단순함과 특정 상황에서의 효율성 때문에 여전히 중요한 정렬 알고리즘 중 하나로 남아있습니다.