삽입 정렬

버블정렬 및 선택 정렬과 비슷한 점이 많습니다. 하지만 차이점도 당연히 갖고 있죠

정렬 원리는 배열에서 비교하면서 바로 정렬된 배열을 구성하는 방식입니다. 글로는 헷갈리기 때문에 그림으로 보겠습니다.

처음에 8과 7을 비교해서 [7,8] 순서를 만들고 다음에 5와 비교해서 [5,7,8]을 만들어 줍니다. 이런식으로 하나씩 진행하면서 앞부분은 이미 정렬이 완성된 상태를 만들어주는 것이죠. 비교해서 올바른 위치에 삽입해주는 것 이것이 삽입 정렬입니다.

삽입 정렬 구현 및 빅오

의사코드

• 배열에서 두번째 요소를 선택해서 시작합니다 (첫번째는 이미 정렬로 쳐도됨)
• 두번째 값과 앞에있는 값을 비교해서 필요하다면 스왑(위치 교환)합니다.
• 다음 요소에서 계속해서 확인 후 스왑 합니다. 그러면 배열의 왼쪽 부분에서 어느 위치에 있어야할 지 판단 후 정렬합니다.
• 위의 방식을 반복해줍니다.

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^2)입니다. 유리한 상황의 예로는 데이터를 실시간으로 받아서 정렬하는 상황입니다. 바로바로 정렬된 배열을 만들 수 있기 때문입니다.