삽입 정렬 (Insertion Sort)

삽입 정렬(Insertion Sort) 소개

삽입 정렬은 비교적 간단하고 직관적인 정렬 알고리즘입니다. 작은 데이터를 정렬할 때는 매우 효율적이지만, 데이터의 양이 많아지면 비효율적이 될 수 있습니다. 삽입 정렬의 기본 아이디어는 이미 정렬된 부분 배열을 확장해 나가면서 새로운 요소를 올바른 위치에 삽입하는 것입니다.

 

삽입 정렬의 의사 코드

배열에서 두 번째 요소를 선택하여 시작합니다.
두 번째 요소를 이전 요소와 비교하고 필요한 경우 스왑합니다.
다음 요소로 계속 진행하고, 잘못된 순서일 경우 정렬된 부분(즉, 왼쪽)을 반복하여 요소를 올바른 위치에 배치합니다.
배열이 정렬될 때까지 이 과정을 반복합니다.

 

삽입 정렬 구현

다음은 삽입 정렬을 JavaScript의 ES6 문법으로 구현한 예제입니다:

const 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;
};

// 사용 예시
let array = [5, 2, 9, 1, 5, 6];
console.log(insertionSort(array)); // [1, 2, 5, 5, 6, 9]

이 코드에서는 insertionSort 함수가 주어진 배열을 삽입 정렬 방식으로 정렬합니다. for 루프를 통해 배열의 두 번째 요소부터 시작하여 각 요소를 이미 정렬된 부분 배열에 삽입합니다. 내부 for 루프는 현재 요소가 올바른 위치에 삽입될 때까지 이전 요소들과 비교하여 요소들을 한 칸씩 뒤로 이동시킵니다.

 

삽입 정렬 빅오(Big-O) 복잡도

삽입 정렬의 시간 복잡도는 다음과 같습니다:

최악의 경우: O(n^2)
배열이 역순으로 정렬되어 있는 경우가 최악의 경우입니다.
최선의 경우: O(n)
배열이 이미 정렬되어 있는 경우가 최선의 경우입니다.

삽입 정렬의 특징

1. 안정성: 삽입 정렬은 안정 정렬 알고리즘입니다. 이는 같은 값의 요소들이 정렬 후에도 기존의 순서를 유지한다는 것을 의미합니다.
2. 적응성: 거의 정렬된 배열에 대해 매우 효율적입니다. 이는 최선의 경우 시간 복잡도가 O(n)인 이유입니다.
3. 간단함: 구현이 매우 간단하고 직관적입니다.

 

삽입 정렬의 장단점

장점

• 구현이 쉽고, 이해하기 쉽습니다.
• 적은 데이터나 거의 정렬된 데이터에 대해 효율적입니다.
• 안정 정렬 알고리즘입니다.

 

단점

• 데이터의 양이 많아질수록 비효율적입니다.
• 최악의 경우 시간 복잡도가 O(n^2)입니다.

 

결론

삽입 정렬은 그리 복잡하지 않으면서도 작동 방식이 매우 직관적입니다. 작은 데이터 세트나 이미 어느 정도 정렬된 데이터에 대해 효율적으로 사용할 수 있습니다. 그러나 큰 데이터 세트에 대해서는 다른 정렬 알고리즘(예: 퀵 정렬, 병합 정렬)보다 성능이 떨어질 수 있습니다. 따라서 상황에 맞게 적절한 정렬 알고리즘을 선택하는 것이 중요합니다.

이 글에서는 삽입 정렬의 기본 개념과 구현 방법, 그리고 시간 복잡도와 특징에 대해 알아보았습니다. 이를 통해 삽입 정렬의 작동 방식을 이해하고, 실제로 코드로 구현할 수 있을 것입니다.