삽입 정렬 (Insertion Sort)

소개

버블 정렬, 선택 정렬과 비슷합니다.
한번에 하나의 항목을 정렬할 위치에 삽입해서 정렬된 배열을 점진적으로 구축해나가는 방법입니다.

• 두번째 요소부터 시작합니다.
• 이전요소(여기서는 첫번째 요소)와 크기를 비교하고 필요하다면 자리를 교체합니다.
• 다음 요소를 선택하고 이전 요소들과 비교를 하면서 데이터가 정렬되어야 할 위치에 위치시킵니다.
• 반복합니다.

구현

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([8,5,22,16,94,77])

삽입 정렬의 Big-O

구현에서도 볼 수 있듯이 O(n2)입니다.
데이터가 거의 정렬되어 있을때는 좋은 방법일 수 있습니다. 하지만 데이터가 반대로 정렬되어 있거나 거의 정렬되어 있지 않을때는 좋지 못합니다.

새로운 값을 하나씩 받아서 정렬할떄는 필요한 위치로 정렬시킬 수 있어서 장점이 될 수 있을것 같습니다.