[JS] 삽입 정렬 구현

JavaScript 알고리즘 & 자료구조 마스터클래스

 

삽입 정렬은 배열을 순회하며 원소를 하나씩 삽입합니다.

배열의 왼쪽 부분은 계속 정렬되어있고, 이 정렬된 부분에 하나씩 삽입합니다.

 

http://visualgo.net/en/sorting

 

아래는 삽입 정렬을 구현한 코드입니다.

function insertionSort(arr){
    for(let i = 1; i < arr.length; i++){
        let cur= arr[i];
        
        for(let j = i - 1; j >= 0 && arr[j] > cur; j--){
            arr[j+1] = arr[j];
        }
        arr[j+1] = cur;
    }
    return arr;
}

 

정렬된 부분을 도는 j 반복문에서 
arr[j] > cur 조건에 걸린다면 오른쪽으로 밀어주는 코드가
이해하는데 많이 어려웠습니다.

 

 

38의 왼쪽 부분은 정렬되어있고, 38을 어디다 삽입해야할지 찾는 차례가 되었을 때, 44를 비교해보면(j는 1) 38보다 크기 때문에 arr[j] > cur 조건에 걸립니다.

 

 

이 때 44를 오른쪽으로 밀어줍니다. arr[j+1] = arr[j]

넣을 곳을 찾아야하는 38이라는 값은 cur 변수에 계속 저장하고 있기 때문에 괜찮습니다.

 

 

 

 

 

그 다음에 j는 0이 되어,

배열에서 3과 비교했을 때는 38이 더 크기 때문에

j 반복문은 멈추고 1번 인덱스(j + 1)에 38을 넣습니다.

 

arr[j+1] = cur

이제 3부터 44까지는 정렬되어 있습니다.

 

 

시간 복잡도는 O(n^2) 입니다.

배열을 정렬하면서 새로운 항목이 자주 추가되고 정렬해야 하는 경우에 유리합니다.