[C] 선택정렬 SelectSort 코드

[C] 선택정렬 SelectSort 코드

선택정렬은 배열의 첫번째 항목부터 배열의 최소값을 탐색하여 교환하며 정렬하는 방식이다.

선택정렬의 장점은 교환이 최소화 된다는 것이다.

비교 횟수는 최소 값을 찾기 위해 N의제곱/2 이지만 교환 횟수는 많아야 N번이다.

이런 특징으로 선택 정렬은 큰 레코드와 작은 키를 직접 정렬할 때 굉장히 유용하다.

하지만 비교를 위한 이중 루프를 돌기 때문에 O()의 성능을 가진다.

그래서 선택 정렬은 N의 수가 커지면 그 실행 시간은 제곱으로 늘어난다.

#include <stdio.h> // 선택 정렬 void select_sort(int a[], int n){     int min;     int minindex;     int i, j;     for (i = 0; i < n - 1; i++){         minindex = i;         min = a[i];         for (j = i + 1; j < n; j++){             if (min > a[j]){                 min = a[j];                 minindex = j;             }         }         a[minindex] = a[i];         a[i] = min;     } }

위의 선택 정렬 함수는 int 형 배열에만 해당된다.

char 나 다른 형태의 배열에 사용하기 위해서는 형별로 함수를 만들어줘야 하는 문제가 있다.

따라서 void 형 포인터를 사용하여 다양한 형의 배열에 사용할 수 있도록 할 수 있다.

#include <stdio.h> #include <string.h> #include <malloc.h> #include <memory.h> // 모든 타입에 대한 선택 정렬 void gen_select_sort(void *base, size_t nelem, size_t width,     int(*fcmp)(const void*, const void*)){          void *min;     int minindex;     int i, j;     min = malloc(width);     for (i = 0; i < nelem - 1; i++){         minindex = i;         memcpy(min, (char*)base + i*width, width);    // min= a[i]         for (j = i + 1; j < nelem; j++){             if (fcmp(min, (char*)base + j*width) > 0){                 memcpy(min, (char*)base + j*width, width);    // min = a[j];                 minindex = j;             }         }         memcpy((char*)base + minindex*width, (char*)base + i*width, width);         memcpy((char*)base + i*width, min, width);     }     free(min); }

gen_select_sort() 함수는 정수 배열 정렬 함수 select_sort()에 비하여 매우 느린 속도를 나타낸다.

그 이유는 복잡한 포인터 연산을 하는데다가 min > a[j] 와 같은 비교 연산에 함수를 호출하고, 값 복사에서도 memcpy() 와 같은 함수를 호출해야 한다.

함수 호출은 속도 저하를 초래한다.

하지만 gen_select_sort() 함수는 함수의 변경 없이 어떤 형의 자료라도 정렬할 수 있는 장점이 있다.

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