삽입 정렬 (Insertion Sort)

인덱스를 순회하면서 한 값을 골라서 그 값을 적절한 위치에 삽입하는 정렬 알고리즘

기존에 이미 정렬된 값의 덩어리들을 흐트러뜨리지 않고 유지할 수 있다는 장점이 있다.

그러나 삽입을 하면서 값을 밀어낼때 값들을 하나씩 옆으로 복사해서 옮겨야 한다는 점이 단점이다.

https://www.geeksforgeeks.org/insertion-sort/

Insertion Sort - Data Structure and Algorithm Tutorials - GeeksforGeeks

Worst Case: O(n^2)

 

정렬이 많이 되어있는 경우 연산이 적다. (버블 소트와 비슷)

 

// Insertion Sort
{
    for (int i = 1; i < n; i++)
    {
        int selected = arr[i];
        int j = i;
        for (; j > 0 && arr[j - 1] > selected; j--)
        {
            arr[j] = arr[j - 1];
        }
        arr[j] = selected;
    }
}

 

Insertion Sort vs Bubble sort

그러면 버블소트와 비교했을때 성능은?

Insertion Sort가 더 좋다.

값을 바꿔줄때,

Bubble Sort는 swap을 하면서 3개의 value의 값변환이 필요한데 반해(3 value assignments per swap)

Insertion Sort는 값을 밀어주는(shift) 하는 방식이기 때문에 1개의 값만 변화시키면 된다. (1 value assignment per spot)

그 외에도 loop가 돌아가는 횟수 자체가 더 적기도 하다.

https://stackoverflow.com/questions/17270628/insertion-sort-vs-bubble-sort-algorithms

Insertion sort vs Bubble Sort Algorithms