[자료구조] 삽입정렬(Insertion Sort)

삽입정렬이란?

간단하면서도 효과적인 알고리즘중 하나입니다.

두번째 자료부터 시작하여 그 앞의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘 입니다.

 

시간복잡도

Worst : O(n²)

Average : O(n²)

Best : O(n)

 

진행 방법

주어진 배열 : [5, 12, 1, 6, 9]

0번째 인덱스는 정렬되어있다 가정하고 1번째 인덱스부터 왼쪽으로 하나씩 비교를 합니다. 

 

알고리즘으로 구현해보면

• 정렬기준이 되는 배열은 0번째인덱스는 정렬되어있다고 가정하고 1번째부터 하나씩 늘어나며 끝까지 비교합니다.

   i = 1; i < n; i++

 

• 정렬기준이 되는 배열은 기준배열 -1씩 줄어들면서 비교하며 진행. 배열에서 음수배열은 없으므로 0보다 커야합니다.

    j = i; j > 0; j--

 

• 기준이 되는 배열을 빈배열에 넣고 교환할 준비를 한다.

    temp = arr[i]

 

• 기준 배열을 빈 배열에 넣고 기준배열보다 큰 값이 있으면 큰값을 배열자리에넣고 교환하며 비교한다.

    if(arr[j-1] > temp) {

        arr[ j ] = arr[ j - 1 ]

        arr[ j - 1 ] = temp

    }

 

코드작성

function insertionsort(arr) {
    let n = arr.length; 
    for (let i = 1; i < n; i++) { 
        let temp = arr[i];        
        for (let j = i; j > 0 && arr[j-1]>temp; j--) { 
            arr[j]=arr[j-1];                           
            arr[j-1] = temp                           
        }                                              
    }                                                  
    return arr;
}
console.log(insertionsort([5, 12, 1, 6, 9]))

 

 

삽입정렬 장점

1. 구현이 간단합니다.

    - 구현이 간단하여 작은 규모의 데이터에 대해서 효과적일 수 있습니다.

2. 대부분의 정렬된 상태에서 효과적입니다. 

    - 정렬된 부분을 늘려가며 진행하기 때문에 이미 정렬된 데이터에 새로운 원소를 추가할때 효율적입니다.

3. 안정한 정렬방법입니다.

    - 값이 같은 두 원소의 상대적인 순서를 유지하므로 안정정렬에 속합니다.

4. 정렬 중에도 부분적으로 정렬된 경과를 확인할 수 있습니다. 

    - 각 단계에서 현재까지의 정렬 상태를 확인할 수 있어 디버깅이나 중간 경과 확인이 쉽습니다.

 

삽입정렬 단점

1. 시간복잡도가 큽니다.

    - 대용량의 데이터나 정렬이 필요한 상황에서는 효율성이 떨어집니다.

2. 비교횟수가 많습니다.

    - 선택 정렬과 마찬가지로 n(n-1)/2로 많이 발생하며, 비교횟수가 입력 크기에 따라 크게 증가합니다.

3. 원소 이동이 많습니다.

    - 작은 원소를 찾아서 적절한 위치에 삽입하는 작업을 반복하므로 원소의 이동 횟수가 많습니다.

4. 다른 정렬 알고리즘 보다 느립니다.

 

∴ 작은 데이터 셋이나 이미 정렬된 데이터에 유용할 수 있지만, 대부분의 실제 응요엥서는 빠른 정렬 알고리즘들이 선호됩니다.

 

 

 

 

 

참조  - 혀니 c코딩