[C] 삽입 정렬 예제 정리

[C] 삽입 정렬 예제 정리

삽입 정렬은 이미 정렬이 된 부분에 새로운 키를 적절한 장소에 삽입하는 동작을 반복적으로 하는 정렬 방법이다.

삽입 정렬은 선택 정렬과 달리 같은 키에 대한 순서가 보장되므로 안정성이 있다.

(단, 작은 값 비교시 <= 로 비교하면 안정성을 보장할 수 없다)

#include <stdio.h> // 삽입정렬 void insert_sort(int a[], int n){     int i, j, t;     for (i = 1; i < n; i++){         t = a[i];         j = i;         while (j > 0 && a[j - 1] > t){             a[j] = a[j - 1];             j--;         }         a[j] = t;     } }

위의 코드에서 사실 변수 t 는 불필요하다. 하지만 굳이 t를 쓴 이유는 속도 향상을 위해서이다.

이 부분에서 a[i]를 쓰는 것과 단순한 t를 쓰는 것은 차이가 있다.

a[i]를 쓸 경우 컴파일러는 a의 값(주소)를 읽어서 i를 더하는 식의 복잡한 처리를 하지만, 단순히 t를 쓸 때는 t의 값을 읽어오는 것으로 처리는 끝난다.

자주 호출이 필요한 내부 루프의 경우는 이렇게 임시 변수를 많이 사용한다.

* 삽입 정렬의 특징

(1) 삽입 정렬은 이미 정렬된 배일일 경우 매우 빠른 속도를 가진다.

- 알고리즘 상으로 이미 정렬된 배열의 경우 교환은 한번도 일어나지 않으며 비교는 N번 밖에 하지 않는다.

(2) 삽입 정렬은 역순의 경우 최악의 경우가 된다.

(3) 난수 배열인 경우에는 선택 정렬보다 훨씬 효율이 좋다

(4) 대충 졍렬된 배열의 경우 삽입 정렬은 속도가 굉장히 빠르다.

- 대충 정렬된 배열의 경우에는 비교와 교환의 횟수가 작아지므로 빨라질 수 밖에 없다.

-> 삽입 정렬은 입력 자료의 정렬된 정도에 따라 효율이 좋을 수도 있고 안 좋을 수도 있다.

삽입 정렬의 경우 작은 크기의 대충 정렬된 배열에 대해서는 제일의 선택이 된다.

그래서 퀵 정렬을 개선하는 방법으로 작은 크기의 배열에 대해서 삽입 정렬을 하는 것은 굉장한 효율을 가진다.

삽입 정렬은 비교 횟수는 적고 교환 횟수가 많다. 그래서 큰 레코드를 정렬할 때는 삽입 정렬은 부적절하다.

삽입 정렬은 O()의 성능을 나타낸다

* 간접 정렬

삽입 정렬에서 간접 정렬을 고려하는 이유는 삽입 정렬이 비교 횟수는 적지만 교환 횟수가 많기 때문이다.

간접 정렬은 레코드의 배열은 전혀 손대지 않고 따로 만든 인덱스의 배열을 조작하는 방법이다.

#include <stdio.h> #include <malloc.h> // 인덱스를 이용한 간접 정렬 void indirect_insert_sort(int a[], int index[], int n){     int i, j, t;     for (i = 0; i < n; i++){         index[i] = i;     }     for (i = 1; i < n; i++){         t = index[i];         j = i;         while (j>0 && a[index[j - 1]] > a[t]){             index[j] = index[j - 1];             j--;         }         index[j] = t;     } } // 간접정렬 index를 사용하여 실제 배열 정렬 void rerange(int a[], int index[], int n){     int *p;     int i;     p = (int*)malloc(sizeof(int)*n);     for (i = 0; i < n; i++){         p[i] = a[index[i]];     }     for (i = 0; i < n; i++){         a[i] = p[i];     }     free(p); }

간접정렬인 indirect_insert_sort 의 경우 비교를 위해서는 a 배열을 사용하지만 while 루프 내의 실제의 교환 작업은 index 배열을 사용한다.

이렇게 간접 정렬을 하고나면 실제로 a 배열에는 아무 변동이 없다. 그러나 그 정렬된 순서는 index 배열에 저장되어 있다. 여기서 실제로 a 배열을 정렬해야 된다면 rerange() 함수를 사용하면 된다.

* 일반화된 삽입 정렬

void 포인터와 함수 포인터를 이용하여 일반화된 정렬 함수를 만들 수 있다.

#include <stdio.h> #include <malloc.h> #include <memory.h> #include <string.h> // 일반화된 함수 작성 void gen_insert_sort(void *base, size_t nelem, size_t width,     int(*fcmp)(const void*, const void*)){          int i, j;     void *t;     t = malloc(width);     for (i = 1; i < nelem; i++){         memcpy(t, (char*)base + i*width, width);         j = i;         while (fcmp((char*)base + (j - 1)*width, t) > 0 && j > 0){             memcpy((char*)base + j*width, (char*)base + (j - 1)*width, width);             j--;         }         memcpy((char*)base + j*width, t, width);     }     free(t); }

출처: https://hyeonstorage.tistory.com/357?category=622873 [개발이 하고 싶어요]