[자료구조/TS] 삽입정렬

삽입 정렬

선택 정렬/버블 정렬과 정반대로 착상한 정렬이다. 선택 정렬과 버블 정렬은 정렬되지 않은 배열의 크기를 n부터 하나씩 줄이는데 삽입 정렬은 정렬된 배열의 크기를 1에서 시작하여 하나씩 늘린다. 삽입 정렬의 핵심 작업은 이미 정렬된 i개짜리 배열에 하나의 원소를 더하여 정렬된 i+1 배열을 만드는 과정이다.
최악의 경우 시간복잡도가 $O(n^2)$가 드는 비효율적인 정렬 알고리즘이지만 배열이 정렬된 상태로 입력된다면 가장 매력적인 알고리즘이 된다.
삽입 정렬은 선택 정렬이나 버블 정렬보다는 빠르며, 10만개의 원소를 임의 생성해서 정렬해서 앞의 정렬들과 비교해보면 삽입 정렬은 선택 정렬보다 3배 빠르고, 버블 정렬보다는 14배 정도 빠르다.

사용처

1. 소규모 데이터 세트
   삽입 정렬은 데이터 양이 적은 경우(보통 10~20개 이하의 요소) 매우 효율적이며, 그 이유는 알고리즘의 오버헤드가 적고, 구현이 간단하기 때문이다.
2. 거의 정렬된 데이터
   이미 정렬된 데이터나 거의 정렬된 데이터에 대해 매우 빠른 성능을 보인다. 평균적으로 $O(n)$의 시간 복잡도로 동작할 수 있다. 이는 기존 요소들이 거의 정렬된 상태에 있을 때, 삽입 정렬이 최소한의 교환만으로 완료되기 때문이다.
3. 실시간 처리
   실시간 시스템에서는 데이터가 추가될 때마다 정렬 상태를 유지해야 할 경우, 삽입 정렬이 적합하다. 예를 들어, 키 입력이나 클릭 이벤트로 수집된 데이터를 실시간으로 정렬해야 하는 경우에 유용하다.
4. 연속된 메모리 공간
   삽입 정렬은 메모리 사용이 간단하고, 추가적인 메모리 공간이 거의 필요하지 않다. 이 점에서 메모리 사용이 중요한 경우에 유리하다.
5. 정렬과 검색의 혼합 작업
   삽입 정렬은 정렬 과정에서 새로운 값을 쉽게 삽입할 수 있는 특성이 있기 때문에, 정렬과 검색을 동시에 처리해야 하는 상황에서 유용하게 사용될 수 있다.
6. 개선된 정렬 알고리즘의 일부
   고급 정렬 알고리즘(예: 병합 정렬, 퀵 정렬)의 하위 알고리즘으로 사용될 수 있다. 데이터가 작을 때는 삽입 정렬을 사용하여 효율을 높이는 경우가 많다.

insertionSort

const insertionSort = (list : number[]) => {

    for(let i=1; i < list.length; i++){

        let loc = i-1;
        let newItem = list[i];

        while(loc >= 0 && newItem < list[loc]){
            list[loc+1] = list[loc];
            loc--;
        }

        list[loc+1] = newItem;
    }

    console.log(list.join(`-`));
}

insertionSort([3,12,2,1,15,8]);
// 결과 : 1-2-3-8-12-15