[자료구조] 정렬(Sorting) 10-1(삽입 정렬)

삽입 정렬 : 이해와 구현

삽입 정렬은 보는 관점에 따라서 별도의 메모리를 필요로 하지 않는 "개선된 선택 정렬"과 유사하다고 느낄 수 있지만 전혀 다른 방법으로 정렬을 이뤄나간다.

위 그림의 배열은 정렬이 완료된 부분과 완료되지 않은 부분으로 나뉘어 있다.
이렇듯 삽입 정렬은 정렬 되지 않은 부분을 정렬된 부분에 삽입해가면서 정렬을 진행하는 알고리즘이다.

먼저 첫번째 데이터와 두번째 데이터 비교 후 나머지 정렬되지 않은 부분들을 삽입하며 정렬을 이어 나간다.
물론..

정렬된 상태로 삽입하기 위해서는 특정위치를 비워야 하고, 비우기 위해서는 데이터들을 한 칸씩 뒤로 미는 연산을 수행해야한다.

즉

"정렬이 완료된 영역의 다음에 위치한 데이터가 그 다음 정렬 대이상이다. "

"삽입할 위치를 발견하고 데이터를 한 칸씩 뒤로 밀수도 있지만, 데이터를 한 칸씩 뒤로 밀면서 삽입할 위치를 찾을 수도 있다."

보아라!

3과 비교하면서 뒤로 한 칸씩 밀며 삽입할 위치를 찾아 삽입하는 과정을 !

이렇듯, 위치를 찾는 과정과 공간 마련과정을 구분할 필요가 없다!
둘다 동시에 진행하기 때문이다 !!

이제 구현의 예를 보자 !

#include <stdio.h>

void InsertSort(int arr[], int n)
{
    int i,j;
    int insData;
    
    for(i=1;i<n;i++)
    {
        insData = arr[i]; // 정렬 대상을 ins에 저장
        
        for(j=i-1;j>=0;j--)
        {
            if(arr[j]>insData)
                arr[j+1]=arr[j];//비교. 대상을 한 칸 뒤로 밀기
            else
                break; //삽입 위치 찾음 !
        }
        arr[j+1] = insData;
    }
}

int main(void)
{
    int arr[5] = {5,3,2,4,1};
    int i;
    
    InsertSort(arr, sizeof(arr)/sizeof(int));
    
    for(i=0;i<5;i++)
    printf("%d ",arr[i]);
    
    printf("\n");
    return 0;
}

이 또한 이중for문의 이해가 필요하다 !
무엇보다도 첫번째는 이미 정렬완료 되었다고 생각하고있고 확인후 삽입한다는것을 생각하고 있는것이 이해하는데 도움이 되는것 같다.

삽입 정렬 : 성능 평가

삽입 정렬은 정렬대상의 대부분이 이미 정렬되어 있는 경우 매우 빠르게 동작한다.
정렬된 상태라면 else문이 실행되어 break문을 실행하게된다.
하지만.. 최악의 경우 앞서 보인 정렬들과 동일하다.

비교연산과 이동연산에 대한 빅-오가 똑같이 등차수열을 이뤄 O(n^2)이 됨을 알 수 있다.