[4][알고리즘 - 정렬] 삽입정렬(Insertion Sort)이란? javascript 구현

삽입 정렬(Insertion Sort)이란?

출처 - https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC

이미 정렬된 부분의 적절한 위치에

삽입해 가며 정렬하는 방식을

삽입 정렬이라고 합니다.

 

 

https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif

실제로 삽입 정렬의 데이터 이동 흐름은 위와 같습니다.

 

여기서의 핵심은

빨간색 데이터를 위로 잠깐 빼놓고,

값을 비교하여 오른쪽으로 계속 당기는 과정이 핵심입니다.

 

빨간색 데이터와 바로 왼쪽의 데이터를

자리 바꿈으로 정렬을 하는 예제들이 많은데,

그렇게 하면 버블 정렬보다 훨씬 느리답니다 ㅠㅠ

 

그럼 코드로 확인해보겠습니다.

 

// 임의 데이터 생성
const makeRandomValueArr = (length) => {
    const arr = [];
    for (let i = 0; i < length; i++) {
        arr.push(i);
    }

    for (let i = 0; i < arr.length; i++) {
        const randomNum = Math.floor(Math.random() * arr.length);
        [arr[i], arr[randomNum]] = [arr[randomNum], arr[i]];
    }

    return arr;
}

// 삽입 정렬
const insertionSort = (array) => {
    for(let i = 1; i < array.length-1; i++) {
        let curIndex = i - 1;
        let curValue = array[i];
        while(curIndex >= 0 && array[curIndex] > curValue) {
            array[curIndex + 1] = array[curIndex];
            curIndex--;
        }
        array[curIndex + 1] = curValue;
    }
    return array;
}

const arr = makeRandomValueArr(10);

console.log('arr=', arr);
// [4, 3, 8, 2, 5, 7, 1, 6, 0, 9]

console.time('insertion');
const result = insertionSort(arr);
console.timeEnd('insertion');

console.log('result=', result);
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

 

핵심은, while 문 안에서 오른쪽으로 값만 당겨주고,

while 문이 종료된 이후

빼놨던 데이터를 삽입시켜주었습니다.

 

while 문 안에서 바로 curValue와 위치 교환을 하며 정렬을 하게 되면

버블 정렬보다 속도가 훨씬 느려진다는 점

꼭 기억해주세요!

 

실제로 지금까지 알아본

버블, 선택, 삽입 정렬에 대해서

임의로 1만 개의 배열로 실제

속도 비교를 해보았습니다.

 

속도 비교를 해보니 위와 같이 나왔네요.

 

 

다음 알아볼 정렬부터는

속도가 말도 안 되게 빨라지는데

빨리 알아보고 싶습니다!

 

출처 - https://dev.to/mauriciord/do-you-know-what-is-big-o-notation-1hhp