[C] 선택정렬 SelectSort 코드[C] 선택정렬 SelectSort 코드

Posted at 2015.02.23 23:13 | Posted in C



facebook에 글올리기



[C] 선택정렬 SelectSort 코드


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


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

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

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


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

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



 Colored By Color Scripter

#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 형 포인터를 사용하여 다양한 형의 배열에 사용할 수 있도록 할 수 있다.



 Colored By Color Scripter

#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() 함수는 함수의 변경 없이 어떤 형의 자료라도 정렬할 수 있는 장점이 있다.

저작자 표시 비영리 변경 금지
신고
이웃추가
facebook에 글올리기

Name __

Password __

Link (Your Website)

Comment

SECRET | 비밀글로 남기기

티스토리 툴바