[알고리즘] 정렬(2) - 삽입 정렬

삽입 정렬(Insort Sort)

정렬 방식

• 리스트에서 순차적으로 순회하면서 정렬이 안 된 부분을 찾고, 해당 부분을 적절한 위치에 삽입하여 정렬하는 방식이다.

정렬 과정

• 해당 예제에서는 오름차순으로 한다.
• 정렬 대상 범위 선정
  • 정렬 대상의 범위는 2개로 시작해서 '자료구조 크기-1'로 1씩 커진다.
• 마지막 요소가 정렬 범위 안에서 최댓값인지 아닌지 확인한다.
  • 최댓값이면 그대로 둡니다.
  • 최댓값이 아니면 정렬 범위 안에서 위치시킬 곳을 찾은 다음, 해당 부분의 오른쪽 데이터들을 범위 안에서 1칸씩 오른쪽으로 옮기고 빈 부분에 데이터를 삽입합니다.

1번째 루프

2번째 루프

2번째 루프는 이미 정렬이 되어있다.

3번째 루프

4번째 루프

삽입 정렬의 성능

최악의 경우 - 역순으로 정렬될 경우

루프마다 범위 안 데이터를 모두 비교하고 위치 변경을 한다.

$$ 비교 횟수: 1+2+..+(n-2)+(n-1) = n(n-1)/2 => O(n^{2}) $$

$$ ∵ 시간 복잡도: O(n^{2}) $$

 

최선의 경우 - 모두 올바르게 정렬된 경우

범위 안 마지막 데이터가 바로 앞에 있는 데이터보다 큰지 비교만 하면 된다.

$$ 시간 복잡도: O(n) $$

 

삽입 정렬은 정렬이 어느 정도 되어있는 자료구조에서 효과적이다.

코드 - [언어: C]

#include <stdio.h>
#include <string.h>

int main() {

    int value;

    int data[] = {4,1,5,2,3};
    int length = sizeof(data) / sizeof(data[0]);

    // 삽입 정렬
    for(int i = 1; i < length; i++){

        // 마지막 데이터와 마지막 바로 앞 데이터와 비교
        if(data[i-1] <= data[i])
            continue;

        value = data[i]; // 옮길 데이터

        for(int j = 0; j < i; j++){
            if(data[j] > value){
                // 오른쪽으로 밀기
                // memmove(목적지 메모리 주소, 이동할 데이터 주소, 이동시킬 데이터 양(byte))
                memmove(&data[j+1], &data[j], sizeof(data[0]) * (i-j)); 
                data[j] = value;
                break;
            }
        }
    }


    // 삽입 정렬 출력
    for(int i = 0; i < length; i++){
        printf("%d ", data[i]);
    }
    printf("\n");

    
    return 0;
}