정렬 (Sort) - 삽입정렬

삽입정렬이란

삽입정렬(Insertion Sort)은 리스트의 요소들을 하나씩 비교하여 정렬된 부분과 비교하고, 알맞은 위치에 삽입하여 정렬하는 방식

1. 두 번째 요소부터 시작하여, 현재 요소를 정렬된 부분의 적절한 위치에 삽입합니다.
2. 이를 위해, 현재 요소보다 큰 요소들을 오른쪽으로 한 칸씩 이동시킵니다.
3. 리스트의 끝까지 이 과정을 반복합니다.

삽입정렬 요약

 

특징	비교 기반의 정렬 알고리즘으로, 리스트의 요소를 하나씩 정렬된 부분에 삽입하여 정렬합니다.
장점	1. 구현이 간단하고 이해하기 쉬움. 2. 대부분 정렬된 리스트에 대해서는 효율적.  3. 제자리 정렬(in-place sort)로, 추가적인 메모리 공간이 필요 없음.
단점	1. 시간복잡도가 O(n^2)로, 큰 데이터셋에서는 비효율적. 2. 요소의 이동이 빈번하여 많은 교환이 발생.
시간복잡도	- 최선: O(n) (리스트가 이미 정렬된 경우) - 평균: O(n^2) - 최악: O(n^2)

자바스크립트 예시

function insertionSort(arr) {
    let n = arr.length;

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

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }

    return arr;
}