Insertion Sort

 

삽입 정렬 : 소개

삽입정렬 의사코드

1. 배열에서 두 번째 요소를 선택하여 시작한다.

2. 이제 두 번째 요소를 이전 요소와 비교하고 필요한 경우 스왑한다.

3. 다음 요소로 계속 이동하고 순서가 잘못된 경우 정렬된 부분(즉, 왼쪽)을 반복하여 올바른 위치에 요소를 배치한다.

4. 배열이 정렬될 때까지 반복한다.

---

https://visualgo.net/en/sorting

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

삽입 정렬 : 구현

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

insertionSort([2,1,9,76,4])

삽입 정렬 : 빅오 복잡도

O(n²) - Worst, Average

O(n) - Best