[C] 쉘정렬 사용 예제[C] 쉘정렬 사용 예제

Posted at 2015.03.09 21:58 | Posted in C



facebook에 글올리기



[C] 쉘정렬 사용 예제


삽입 정렬은 이미 정렬된 배열이나 대충 정렬된 배열에 대해서는 매우 뛰어난 성능을 보이지만 그렇지 않은 경우에는 속도가 매우 느리다. 이것은 삽입 정렬이 바로 인접한 요소와 비교를 하기 때문이다.


쉘 정렬은 이 같은 문제점을 해결하기 위해서 h만큼의 간격으로 떨어진 레코드를 삽입 정렬하는 방법이다.


쉘 정렬은 안정성이 없다


쉘 정렬은 h 값에 의해 성능이 좌우된다.

h = 3 * h +1  이 가장 효율이 좋다고 한다.



Colored By Color Scripter

#include <stdio.h>
#include <malloc.h>

// 최대 효율 h 지정 h = 3*h+1
void shell_sort1(int a[], int n){
    int i, j, k, h, v;
    for (h = 1; h < n; h = 3 * h + 1);    // n보다 작은 h의 최대값을 찾는다.
    for (h /= 3; h > 0; h /= 3){
        for (i = 0; i < h; i++){
            for (j = i + h; j < n; j += h){
                v = a[j];
                k = j;
                while (k>h - 1 && a[k - h] > v){
                    a[k] = a[k - h];
                    k -= h;
                }
                a[k] = v;
            }
        }
    }

}


쉘 정렬은 4중 루프로 구성되어 있어 속도가 매우 느릴 것 같지만, 속도면에서는 성능이 좋은 알고리즘이다.


* 일반화된 쉘 정렬



Colored By Color Scripter

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


void gen_shell_sort(void *base, size_t nelem, size_t width,
    int(*fcmp)(const void*, const void*)){

int i, j, k, h;
    void *v;
    v = malloc(width);

    for (h = 1; h < nelem; h = 3 * h + 1);
    for (h /= 3; h > 0; h /= 3){
        for (i = 0; i < h; i++){
            for (j = i + h; j < nelem; j += h){
                memcpy(v, (char*)base + j*width, width);
                k = j;
                while (k>h - 1 && fcmp((char*)base + (k - h)*width, v) > 0){
                    memcpy((char*)base + k*width, (char*)base + (k - h)*width, width);
                    k -= h;
                }
                memcpy((char*)base + k*width, v, width);
            }
        }
    }
    free(v);
}


저작자 표시 비영리 변경 금지
신고

'C' 카테고리의 다른 글

[C] 퀵정렬 예제 정리  (0) 2015.03.14
[C] 분포수 세기 정렬 예제  (0) 2015.03.09
[C] 쉘정렬 사용 예제  (0) 2015.03.09
[C] 버블 정렬 예제 정리  (0) 2015.03.01
[C] 삽입 정렬 예제 정리  (0) 2015.02.24
[C] 선택정렬 SelectSort 코드  (0) 2015.02.23
이웃추가
facebook에 글올리기

Name __

Password __

Link (Your Website)

Comment

SECRET | 비밀글로 남기기

티스토리 툴바