삽입정렬(Insertion Sort)

Insertion Sort

2번째 아이템부터 시작하며, 앞에서부터 차례대로 정렬된 부분과 비교하여 자신의 위치를 찾아 삽입하여 정렬하는 알고리즘입니다.

 

Process

1부터 6까지 랜덤으로 들어 있는 배열이 있습니다.

Ascending(오름차순)으로 정렬합니다.

 

1. 비교하고자 하는 값(2번째 아이템)을 가지고 비교를 시작합니다.
2. 첫 번째 아이템이 작으면 삽입을 진행하지 않습니다. (현재 사이클 종료)

1 사이클이 종료되었습니다.

 

2사이클 시작

1. 세 번째 아이템을 비교 값으로 가지고 있습니다.
2. 두 번째 아이템과 비교하여 두 번째 아이템이 크면 교환 크지 않으면 사이클 종료
3. 여기서는 두 번째 아이템이 더 크기 때문에 교환 후 다음 비교를 진행합니다.
4. 첫 번째 아이템과 비교 했을때는 비교 값이 더 크기 때문에 현재 사이클을 종료하고 다음 사이클로 넘어 갑니다.

3번째 사이클 시작하여 다음과 같은 과정을 마지막 아이템까지 반복합니다.

이렇게 삽입정렬은 비교하고자 하는 값을 정렬된 부분과 비교하여 해당 위치에 삽입하면서 정렬하는 방식입니다.

 

Code

void insertionSort(int arr[], int length)
{
    int temp = 0;
    int minIndex = 0;
    for (int i=1; i < length; i++) // 첫번째 원소는 비교 대상이 없기 때문에 두번째 원소부터 비교합니다.
    {
        temp = arr[i];
        minIndex = i;
        
//        for (int j= i - 1; j>=0 && arr[j] > temp; j--)
//        {
//            arr[j + 1] = arr[j];
//            minIndex = j;
//        }
        
        int prevIndex = i - 1; // 현재 비교 위치
        while (prevIndex >= 0 && arr[prevIndex] > temp) { // 현재값의 인덱스가 0보다 크고, 비교값보다 크면 다음 인덱스로 삽입합니다.
            arr[prevIndex + 1] = arr[prevIndex];
            minIndex = prevIndex;
            prevIndex--;
        }
        
        arr[minIndex] = temp; // 반복문이 종료되면 마지막으로 삽입 된 값의 인덱스에 비교값을 넣어 줍니다.
        
    }
}

 

Time Complexity of Insertion Sort

최악(역순)이나 평균의 경우 값을 다 비교해봐야 하므로 O(n^2) 만큼의 시간 복잡도를 가집니다.

최선인 정렬이 되어 있는 경우에는 O(n)의 시간 복잡도를 가집니다.

https://www.bigocheatsheet.com

 

참고

• https://blog.chulgil.me/algorithm/
• https://www.bigocheatsheet.com