삽입 정렬 알고리즘(insertion sort Algorithm) - javascript

안녕하세요 기공 준입니다.

이번에는 삽입 정렬에 대해 알아볼 건데요

간단한 설명과 예제 및 코드로 글을 마무리하겠습니다.

 

삽입 정렬은 자료 배열의 모든 요소를 이미 정렬된 배열 부분과 앞에서부터 차례대로 비교하여, 자신의

위치를 찾아 삽입하는 정렬입니다.

배열이 길어질수록 효율이 떨어지지만 구현이 아주 간단하다는 장점이 있습니다.

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

 

예제 

[3,2,5,10,33,51,20,16] 시작

[2,3,5,10,33,51,20,16] 2 삽입

[2,3,5,10,33,51,20,16] 패스

[2,3,5,10,33,51,20,16] 패스

[2,3,5,10,33,51,20,16] 패스

[2,3,5,10,33,51,20,16] 패스

[2,3,5,10,20,33,51,16] 20 삽입

[2,3,5,10,16,20,33,51] 16 삽입

 

const insertionSort = (array) => {
    
    for(let i=1;i<array.length;i++){
        let temp = array[i];
        let idx = i;

        while(idx > 0 && temp < array[idx-1]){
            array[idx] = array[idx-1];
            idx--;
        }
        array[idx] = temp;  
    }
    console.log(array);
}

let arr = [3,2,5,10,33,51,20,16];

insertionSort(arr);