Algorithm #1. Sort algorithm. - 1.2 Insertion Sort algorithm.

흠. 두 번째 포스트군요 ㅇ_ㅇ.

이번 포스트는 앞서 언급했던 정렬 알고리즘들을 세분화하고 그 특징. 그리고 구현법에 대해 알아보죠.

우선, 가장 간단한 것부터 알아보도록 할까요. 우선 삽입 정렬(Insertion Sort)입니다.

삽입 정렬 알고리즘은 보통 카드 게임에서 카드를 정렬하는 것으로 비유하고 있습니다.

카드 몇 장을 이미 받았다고 가정하고, 카드 덱(Card deck) 에서 카드 한 장을 뽑아 손에 쥐어 봅시다.
그리고 나서 무늬에 관계없이 카드를 정렬하려 한다고 가정합시다. 여러분들은 어떻게 하시나요?

일반적으로, 이미 카드 몇 장을 받은 시점에서 카드를 정렬할 겁니다. 우선 처음 두 장을 비교하고, 값 순서대로 배열하겠죠.
그리고 나서 아마 '이미 정렬된' 두 장의 값 범위를 비교하고 나서 - 좌, 우 카드값의 비교겠죠 -  다음 카드를 그 두 장 사이에
'삽입' 했을 겁니다.

이를 반복하면, 결국 손에 쥐고 있던 카드들은 모두 다 정렬되어 있겠죠. 자, 이제 카드 덱에서 뽑은 카드를 어떻게 정렬할까요?
마찬가지겠죠. 이 카드는 '이미 정렬된' 카드 뭉치들의 좌, 우 값들을 비교하고, 그 사이에 '삽입' 할 겁니다.

이제 왜 삽입 정렬(Insertion Sort) 인지 아시겠나요?

이 Insertion Sort 알고리즘은 이런 '이미 정렬된' 부분에 '새로운 키(key) 값'을 삽입합니다. 그러고 나면, 결국 모든 부분은
완벽히 정렬이 되어 있겠죠.

즉, Insertion Sort 알고리즘은 값의 비교는 그렇게 많게는 하지 않습니다. - 좌 , 우 값 비교 뿐이죠. -
단, 새로운 값이 이미 정렬된 부분 사이에 삽입되므로 값의 교환 횟수는 증가하겠죠.

따라서, 입력된 자료의 정렬도에 따라서 효율이 달라질 수 있다고 할 수 있겠습니다.

만약 완벽히 정렬된 배열이라면 교환은 한 회도 발생하지 않습니다. 값의 비교에만 시간이 소요되겠죠.
일부만 정렬되어 있더라도 Inserton Sort 는 좋은 효과를 기대할 수 있습니다. 교환 횟수가 줄어드니까요.
하지만, 역순 정렬의 경우에는 최악의 경우가 발생합니다. 비교 보다 교환이 월등히 많기 때문이죠. 모든 값들을 교환해야 한다는
부담이 존재합니다.
더욱이 큰 레코드의, 거의 정렬되지 않은 자료형에 Insertion Sort를 시도할 경우, 교환 횟수가 매우 커지게 될 겁니다.

- 이런 경우엔 일반적으로 Quick Sort 가 해법입니다. -_-; 물론 다른 방식을 시도하면 훨씬 시간을 단축시킬 수 있긴 하죠. -

자, 이제  Insertion Sort 알고리즘의 특징을 정리해 볼까요.

1. 1. 자료의 정렬 정도에 민감하다 .
        -> 일부 정렬된 작은 레코드의 자료형에 대해서는 최적의 선택일 수 있다.
            그러나, 역순 정렬된 레코드에 대해서는 교환 횟수가 증가하므로, 최악의 선택이다.
            반드시 다른 정렬 알고리즘을 선택할 것.
      
      
   2. 레코드의 크기에도 영향을 크게 받는다.
        -> 물론 모든 정렬 알고리즘은 레코드의 크기에 영향을 받는다.
           그러나, Insertion Sort 처럼 교환 횟수가 큰 정렬 알고리즘의 경우에 이 영향력은 매우 커질 수 있다.

다음으로, Insertion Sort의 코드를 작성해 보았습니다. 간단한 알고리즘이니, C 코드로 구현했죠.

#include <stdio.h> int main() { int input[10]; int min; int i , j; int is_sorted, key; for(i=0 ; i < 10 ; i++) { printf("%d번째 수 입력 : ",i +1); scanf("%d",&input[i]); } for(i=0 ; i<10 ; i++) { is_sorted = 1; min = input[i]; key = i; for(j=i ; j<10 ; j++) { if(min > input[j]) { is_sorted = 0; min = input[j]; key = j; } } if(!is_sorted) { input[i] ^= input[key]; input[key] ^= input[i]; input[i] ^= input[key]; } } for(i=0 ; i < 10 ; i++) { printf("%4d",input[i]); } printf("\n"); }

10개의 레코드를 받아서 정렬하는 코드입니다.

교환부는... 물론 temp 변수를 하나 만들어서 swap 형식으로 해도 됩니다만, 저런 방식으로 XOR 연산자를
이용하시면 조금이나마 더 빠른 정렬 결과를 얻을 수 있지요. -_-a

코드를 보시면 아시겠지만, for 문이 중첩되어 있습니다. 따라서, 일반적으로 O(N^2) 의 성능을 가집니다.

도움이 되셨나요? ㅇ_ㅇ;