삽입 정렬(Insertion Sort)

특징

• '각 데이터를 적절한 위치에 삽입한다'는 아이디어에서 만들어진 알고리즘입니다.
• 삽입 정렬의 독특한 점은 현재 데이터 앞의 데이터는 정렬이 되어있다고 가정한다는 점입니다. 현재 데이터를 그보다 앞의 데이터와 비교-교환하며 더 작은 데이터와 비교한 시점에 교환을 종료합니다. 이때 원래 데이터가 들어간 위치가 적절한 삽입 위치입니다.
• 데이터를 비교, 교환하며 정렬되기 때문에 비교 정렬로 분류됩니다.

효율

• 시간복잡도
  
  • 최선의 경우: Ω(N)
    • 데이터가 정렬되어 있는 상태일 수록 효율이 높아집니다. 정렬된 상태에서는 교환이 일어나지 않고 N번의 비교만 수행됩니다.
  • 최악의 경우: O(N²)
• 공간복잡도 - O(N)

구현

function insertionSort(input) {
    for (let i = 1; i < input.length; i++) {
        let j = i;
        while (j > 0) {
            // 앞의 데이터가 더 크면 교환
            if (input[j - 1] > input[j]) {
                let temp = input[j - 1];
                input[j - 1] = input[j];
                input[j] = temp;
            } else {
                break; // 앞의 데이터가 더 작으면 '적절한' 위치에 삽입된 것으로 간주하고 교환 종료
            }
            j--
        }
        console.log(...input);
    }
}

let sample = [7, 3, 2, 8, 9, 4, 6, 1, 5];
insertionSort(sample);
/* 정렬 과정 출력
3 7 2 8 9 4 6 1 5
2 3 7 8 9 4 6 1 5
2 3 7 8 9 4 6 1 5
2 3 7 8 9 4 6 1 5
2 3 4 7 8 9 6 1 5
2 3 4 6 7 8 9 1 5
1 2 3 4 6 7 8 9 5
1 2 3 4 5 6 7 8 9
*/