정렬 알고리즘 (3) - 삽입 정렬

강의: 구름에듀 "안경잡이개발자가 알려주는 실전 알고리즘 강좌"
링크: 안경잡이개발자가 알려주는 실전 알고리즘 강좌
(강의는 알고리즘 풀이를 C/C++ 언어로 진행합니다.)

내용 정리 출처: [JS/Sorting] 버블 정렬, 삽입 정렬, 선택 정렬 자바스크립트로 구현하기 (Bubble Sort, Insertion Sort, Selection Sort in JavaScript)

정렬 알고리즘

대체로 알고리즘을 공부할 때 가장 먼저 나오는 개념이 정렬 알고리즘인 이유는 효율성의 차이를 가장 극명하게 보여주기 때문

삽입 정렬

각 숫자를 적절한 위치에 삽입하는 방법
선택 정렬과 버블 정렬은 무조건 위치를 바꾸는 방식이었다면, 삽입 정렬은 '필요할 때'만 위치를 바꾸게 됨

의사코드를 작성한다면?

인덱스가 1인 요소를 curValue에 할당한다.
인덱스가 0인 요소가 curValue보다 크면 인덱스가 0인 요소에 curValue를 할당하고, 하나씩 뒤로 땡긴다.
(인덱스가 0인 요소가 curValue보다 작을 경우 아무일도 벌어지지 않음)
인덱스가 2인 요소를 curValue에 할당한다.
인덱스가 1, 2인 요소가 curValue보다 크면 인덱스가 0인 요소에 curValue를 할당하고, 하나씩 뒤로 땡긴다.
(인덱스가 0인 요소가 curValue보다 작을 경우 아무일도 벌어지지 않음)
반복..

코드로 작성한다면?

function solution (arr) {
    for (let i = 1; i < arr.length; i++) {
        let curValue = arr[i];

      	let j;
        for (j = i - 1; j > 0 && arr[j] > curValue; j--) {
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = curValue;
    }
    
    return arr;
}

console.log(solution(arr1));

시간 복잡도

BigO

• Worst Case(정렬이 하나도 안되어있는 경우): O(N^2)
• Best Case(이미 정렬이 되어있는 경우): O(N)

장점

• 삽입 정렬은 in place 알고리즘이기 때문에 메모리가 절약
• 이미 정렬된 데이터를 순회하는 경우 O(n)번만 순회하면 되기 때문에 정렬이 되었는지 안되었는지 테스트하는 용도로 사용 가능
• 삽입 정렬은 중복 데이터가 있을 경우 데이터의 위치를 교환하지 않고 지나가기 때문에 stable한 정렬

단점

• 자료의 개수가 많아질수록 성능이 매우 떨어진다는 점