[알고리즘] 삽입 정렬(Insertion Sort) - 코딩밥상

삽입 정렬이란?

삽입 정렬은 책장에 꽂힌 책을 정리하는 과정과 비슷합니다.

예를들어 시리즈 만화를 순서에 맞게 정리하자고 생각해 봅시다. 일단 책장의 왼쪽부터 오른쪽 방향으로 각 권이 옳은 순서로 꽂혀 있는지 확인하고, 잘못된 위치에 꽂혀 있는 책은 뽑아서 올바른 위치에 삽입해나가면 됩니다.

즉 삽입 정렬은 자료구조를 순차적으로 순회하면서 순서에 어긋나는 요소를 찾고, 그 요소를 올바른 위치에 다시 삽입해나가는 정렬 알고리즘입니다.

1. 범위는 첫 2개 요소로 시작하며 알고리즘 수행을 반복하면서 1씩 증가하고 최대 '자료구조의 크기 - 1'까지 수행한다.
2. 범위 마지막에 있는 요소가 정렬 범위 안에서 가장 큰 값을 갖는지 점검하고, 가장 큰 값이 맞으면 그대로 두고 그렇지 않으면 정렬 범위에서  적절한 곳(첫 요소와 원래 위치 사이 중 해당 요소보다 작은 요소가 없는 곳)을 찾는다.
3. 정렬 대상에서 삽입할 값보다 큰 값을 가진 모든 요소를 한 자리씩 뒤로 이동시키고 새로 생긴 빈 자리에 삽입시킨다.
4. 전체 자료구조의 정렬이 완료될 때까지 반복한다.

예를들어

5 1 6 4 2 3 을 오름차순으로 삽입 정렬 하면,

5 1 6 4 2 3 -> 1 5 6 4 2 3

1 5 6 4 2 3 -> 1 5 6 4 2 3

1 5 6 4 2 3 -> 1 4 5 6 2 3

1 4 5 6 2 3 -> 1 2 4 5 6 3

1 2 4 5 6 3 -> 1 2 3 4 5 6

 

삽입 정렬은 시간 복잡도 O(n^2)으로 매우 비효율적이지만 

구현이 쉽습니다.

 

삽입 정렬은 버블 정렬과 다르게 이미 범위 내의 자료구조가 정렬되어 있다면 비교 과정을 거치지 않기때문에 버블 정렬보다는 성능이 뛰어납니다.

삽입 정렬은 반드시 n(n-1)/2 회만큼의 비교를 거치지만, 버블 정렬은 최악의 경우와 최선의 경우 각각 비교 연산에 차이가 있기에 그 평균값으로 생각하면 {n(n-1)/2 + (n-1)}/2 = (n^2+n-2)/2 가 되겠네요.

---

코드 구현

void InsertionSorting(int DataSet[], int Length){
    int value = 0;
    
    for(int i=1; i<Length; i++){
        if(DataSet[i-1] <= DataSet[i]) continue;
        
        value = DataSet[i];
        
        for(int j=0; j<i; j++){
            if(DataSet[j] > value){
                memmove(&DataSet[j+1], &DataSet[j], sizeof(DataSet[0] * (i-j)));
                DataSet[j] = value;
                break;
            }
        }
    }
}