알고리즘, Sort, Insertion Sort

삽입 정렬(Insertion Sort)은 간단하고 직관적인 정렬 알고리즘 중 하나로, 배열을 부분적으로 정렬된 상태로 유지하면서 새로운 요소를 올바른 위치에 삽입하는 방식입니다. 삽입 정렬은 작은 데이터 세트에 대해서는 효율적이고, 거의 정렬된 배열에 대해서도 효율적입니다.

기본 개념

삽입 정렬의 기본 개념은 다음과 같습니다:

1. 부분 정렬 유지: 배열의 첫 번째 요소는 이미 정렬된 상태로 간주하고, 두 번째 요소부터 시작하여 배열을 부분적으로 정렬된 상태로 유지합니다.
2. 삽입 위치 찾기: 현재 요소를 이미 정렬된 부분 배열과 비교하여 적절한 위치를 찾습니다.
3. 삽입: 현재 요소를 올바른 위치에 삽입합니다.
4. 반복: 배열의 모든 요소에 대해 이 과정을 반복합니다.

예제

다음은 자바스크립트로 구현한 삽입 정렬의 예제입니다.

function insertionSort(arr) {
  var currentVal;

  for (var i = 1; i < arr.length; i++) {
    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;
}

console.log(insertionSort([2, 1, 9, 76, 4]));

// currentnValue: 1 ,  [ 1, 2, 9, 76, 4 ]
// currentnValue: 9 ,  [ 1, 2, 9, 76, 4 ]
// currentnValue: 76 , [ 1, 2, 9, 76, 4 ]
// currentnValue: 4 ,  [ 1, 2, 4, 9, 76 ]

 

시간 복잡도

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

• 최악의 경우 시간 복잡도: O(n^2)
  • 배열이 역순으로 정렬된 경우 모든 요소를 비교하고 이동해야 합니다.
• 평균 시간 복잡도: O(n^2)
• 최선의 경우 시간 복잡도: O(n)
  • 배열이 이미 정렬된 경우 한 번의 비교만으로 정렬이 완료됩니다.

특징

1. 단순함: 삽입 정렬은 이해하고 구현하기 매우 쉽습니다.
2. 제자리 정렬(In-place Sort): 별도의 추가 메모리를 거의 사용하지 않으며, 주어진 배열 내에서 정렬이 이루어집니다.
3. 안정성: 삽입 정렬은 안정적입니다. 동일한 값의 요소들이 입력 순서를 유지합니다.
4. 효율성: 삽입 정렬은 작은 배열이나 거의 정렬된 배열에 대해서 매우 효율적입니다. 그러나, 큰 배열에 대해서는 비효율적입니다.

결론

삽입 정렬은 간단하고 직관적인 정렬 알고리즘으로, 이해하기 쉽고 구현이 간단합니다. 작은 데이터 세트나 거의 정렬된 배열에 대해서는 매우 효율적이며, 안정적인 정렬 알고리즘입니다. 그러나, 시간 복잡도가 O(n^2)이기 때문에 큰 배열에 대해서는 비효율적이며, 이 경우 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort)과 같은 더 효율적인 정렬 알고리즘을 사용하는 것이 좋습니다.