C로 구현한 여러 정렬 함수

bubble_sort.c

#include "sort.h"

/**
 * sort array by using bubble sort
 * @param void* base: array's pointer
 * @param int n: number of  elements in array
 * @param int size: size of value type
 * @param int(*cmp)(const void*, const void*): compare function
 * cmp(a, b) : returns 1 if a > b, 0 if a == b, 0 otherwise.
 */
void bubbleSort(void* base, int length, int size, int(*cmp)(const void*, const void*)){
    int j;
    void *temp = malloc(size);
    void *next_position;
    int changed = 0;
    while(1){
        changed = 0;
        for(j=0;j<length-1;j++){
            next_position = base + (j+1)*size;
            if(cmp(next_position, base+(j*size)) < 0){
                // swapping
                swap(next_position, base+(j*size), size);
                changed = 1;
            }
        }
        if(changed==0){
            free(temp);
            return;
        }
    }
}



int main(){
    test(bubbleSort);
    return 0;
}

heap_sort.c

# include "sort.h"
/**
   힙 소트 

   배열을 정렬되지 않은 힙으로 보고 힙을 정렬하는 방식으로 배열을 정렬한다. 

   # 힙만들기 (perc_donw)

   1. i번째 원소의 두 자식 l, r 이 있다고 가정한다. l = i * 2 + 1, r = i * 2 + 2 로 구한다.
   부모, 왼쪽 자식, 오른쪽 자식 중 가장 큰 것을 찾는다.  
   2. 먼저 l번째 원소(왼쪽 자식)이 부모(i번 원소)보다 크면 max 는 l 이다. 
   3. 다시 max번째 원소(왼쪽 자식과 부모 중 큰 것)보다 r번째 원소가 크면 max는 r이 된다. 
   4. 두 자식 중 부모보다 큰 원소가 있으면 부모와 위치를 교환한다. 
   5. 다시 교환이 일어난 자식의 위치에서 더 큰 자식을 찾는 1~4의 과정을 반복한다. 

   # heapify 과정을 순차적으로 돌려주면 가장 큰 원소가 루트가 되는 것이 보장된다. 

   1. 루트(현재 가장 큰 값)을 맨 끝의 원소와 교체한다. 루트 위치로 새로 올라온 원소는 heapify에 의해서 제자리를 찾아간다. (여기서 루트는 나머지 중에서 가장 큰 값)
   2. 다시 맨끝에서 인덱스를 1 내린 값을 루트(이제는 두번째로 큰 값) 다시 새로 올라간 원소는 heapify()로 처리한다. 
   3. 2번째 원소에 다다를 때까지 2를 반복한다. 
   4. 정렬이 끝난다. 

 **/

void heap_sort(void * base, int length, int size, int( * cmp)(const void * ,
            const void * ));
void heapify(void * base, int size, int end, int i, int( * cmp)(const void * ,
            const void * ));


void heapify(void * base, int size, int end, int i, int( * cmp)(const void * ,
            const void * )) {
    // 양쪽 자식(있다면) 과 현재노드 중에서 가장 큰 값의 인덱스 max를 찾는다.
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    int max = i;
    if (l < end && cmp(base + (i * size), base + (l * size)) < 0) {
        max = l;
    }
    if (r < end && cmp(base + (max * size), base + (r * size)) < 0) {
        max = r;
    }
    // max가 원래 노드가 아니면(자식이 더 크면) 이를 교환하고, 해당 가지에 대해서 
    // 재귀적으로 탐색한다. 
    if (max != i) {
        swap(base + i * size, base + max * size, size);
        heapify(base, size, end, max, cmp);
    }
}

void heap_sort(void * base, int length, int size, int( * cmp)(const void * ,
            const void * )) {
    int end = length;
    int start = end / 2 - 1;
    int i;
    // 역순으로 자신보다 큰 자식을 끌어올려 가장 큰 값이 루트로 가게 한다. 
    // 이 과정이 끝나면 "대략적으로 정렬된 상태"가 된다. 
    for (i = start; i > -1; i--) {
        heapify(base, size, end, i, cmp);
    }

    // 루트를 맨 끝 원소와 교체한다음, heapify()하여 그 다음 큰 값이 루트로
    // 오도록한다.
    for (i = end - 1; i > 0; i--) {
        swap(base + i * size, base, size);
        heapify(base, size, i, 0, cmp);
    }
}

int main(void) {
    test(heap_sort);
    return 0;
}

insertion_sort.c

#include "sort.h"

/**
    삽입정렬의 알고리듬 
    1. 두 번째 인덱스(1)부터 시작한다. 
    2. 바로 직전 인덱스의 값이 자신보다 크거나 같으면 비교 대상을 다시 한 인덱스 앞으로 돌린다. 
    3. 자신보다 작은 인덱스가 나타나면, 그 오른쪽으로 1.의 인덱스의 값을 삽입한다. 
    4. 삽입할 위치로부터, 1의 왼쪽 위치까지의 값을 한 칸씩 오른쪽으로 밀고 (memmove로 이동)
    5. 원래 값을 그 자리에 밀어 넣는다. 
**/
void insertion_sort(void *base, int length, int size, int(*cmp)(const void*, const void*)){
    void* saved = malloc(size);
    void* value;
    int i, j;
    for(j=1;j<length;j++){
        value = base+j*size;
        i = 1;
        while(j-i>=0){
            if(cmp(base+(j-i)*size, value) >= 0){
                i += 1;
            } else {
                break;
            }
        }
        if(i>1){
            i-=1;
            memmove(saved, value, size);
            memmove(base+(j-i+1)*size, base+(j-i)*size, i*size);
            memmove(base+(j-i)*size, saved, size);
        }
    }
    free(saved);
}

int main(){
    test(insertion_sort);
    return 0;
}

merge_sort.c

#include "sort.h"

/**
    병합정렬 : 병합정렬은 2개 이상의 비슷한 크기를 가진 배열로 원래 배열을 쪼갠 후, 
    각 부분배열을 재귀적으로 정렬하고 그 결과를 병합하는 방법을 사용한다. 부분집합을 만들기 위해서 
    추가적인 메모리를 할당해야 한다는 부담은 있지만, 정렬성능은 좋은 편이며, 
    메모리가 부족한 경우, 외부 IO에 데이터를 보관한 후 이를 조금씩 나눠 정렬함으로써, 
    실제 가용메모리보다 큰 데이터를 정렬하는 것도 가능하다. 

    # 알고리듬

    1. 배열의 길이가 0, 1인 경우에는 이미 정렬된 것으로 간주하고 바로 리턴한다. 
    2. 배열의 길이를 반으로 나누어 temp1, temp2의 부분 배열을 새로 할당한다. 
    3. 각 부분 배열을 재귀적으로 병합정렬한다. 
    4. 정렬된 부분집합 L, R에 대해서 각 배열의 맨 앞의 인덱스의 값을 비교, 작은 값을 원배열의 첫번째 원소로 복사한다.
    그리고 값을 추출한 배열은 인덱스를 1 증가시킨다. 
    5. 4의 과정을 반복한다. 
    6. 하나의 부분배열이 소진되면 나머지 부분 배열로부터 차례로 원소를 복사해넣는다. 
    7. 정렬이 끝났으므로 부분 배열을 해제하고 리턴한다. 

**/

void mergesort(void* base, int length, int size, int(*cmp)(const void*, const void*));

void mergesort(void* base, int length, int size, int(*cmp)(const void*, const void*)){
    if(length < 2) return;

    void* temp1;
    void* temp2;
    int l_length = length / 2;
    int r_length = length - l_length;

    temp1 = malloc(l_length * size);
    temp2 = malloc(r_length * size);
    memcpy(temp1, base, l_length*size);
    memcpy(temp2, base+l_length*size, r_length*size);

    mergesort(temp1, l_length, size, cmp);
    mergesort(temp2, r_length, size, cmp);

    int k, li, ri;
    li = 0;
    ri = 0;
    void* value;
    for(k=0;k<length;k++){
        if(li == l_length){
            value = temp2 + ri*size;
            ri += 1;

        }
        else if(ri == r_length){
            value = temp1 + li*size;
            li += 1;
        }
        else {
            if(cmp(temp1+li*size, temp2+ri*size)<0){
                value = temp1+li*size;
                li += 1;
            } else {
                value = temp2+ri*size;
                ri += 1;
            }
        }
        memcpy(base+k*size, value, size);
    }
    free(temp1);
    free(temp2);
}

int main(){
    test(mergesort);
    return 0;
}

quick_sort.c

#include "sort.h"

/**
    *임의의 배열 포인터에 대한 퀵소트 구현 

    1. 퀵소트 함수는 1)배열의 시작번지, 2)배열의 길이, 3)비교함수를 받아 배열을 퀵소트 알고리듬을 
    통해 제자리에서 정렬한다. 
    2. 퀵소트 함수는 내부적으로 헬퍼함수를 이용, 배열이 잘려지는 위치를 파악하고 재귀적으로 동작한다. 


    *알고리듬 

    다음은 헬퍼함수의 알고리듬이다.

    1. 배열의 시작 위치(base)를 피봇으로 한다. 
    2. left는 피봇의 옆 위치 
    3. right는 배열의 마지막 원소의 위치. 만약 right가 left보다 크지 않다면 -1을 리턴한다.
    4. left의 원소가 pivot보다 작고, left가 end까지 도달하지 않았다면 left를 한 칸씩 증가한다.
        (증가 단위는 size만큼)
    5. right의 원소가 pivot보다 크고, right가 base의 옆 위치까지 도달하지 않았다면, right를 한 칸씩
        감소시킨다. (역시 size만큼씩) 이 때 mark는 1씩 증가한다.
    6. 4~5를 한 번씩 되풀이 한 후, right가 left보다 작다면, 교차가 발생했다고 표시한다. (met = 1)
    7. 6에서 교차가 발생했다면 right와 pivot의 값을 교환한다음, mark를 리턴한다. 
    8. 6에서 교차가 발생하지 않았다면 left와 right의 값을 서로 교환한 다음 4부터 다시 시작한다. 

    퀵소트는 먼저 주어진 배열의 구간에 대해 헬퍼함수를 한 번 돌린다. 그리고 

    1. 주어진 리턴값이 -1이면 더 이상 쪼개어 정렬할 수 없으므로 바로 리턴한다. 
    2. 주어진 리턴값이 0이상이면, 그 값을 기준으로 쪼갠다. 이 값은 배열의 뒤로부터의 인덱스이다. 
       이 인덱스를 포함하지 않는 왼쪽 부분집합과 오른쪽 부분집합에 대해서 재귀적으로 각각 퀵소트를 호출한다. 

**/


void quickSort(void *base, int length, int size, int(*cmp)(const void*, const void*));
int  quickSortHelper(void *base, void *end, int size, int(*cmp)(const void*, const void*));


/** 퀵 소트 함수 본체 **/
void quickSort(void *base, int length, int size, int(*cmp)(const void*, const void*)){
    void *end = base+(length-1)*size; // 배열의 길이로부터 오른쪽 끝 위치를 구한다. 
    int idx = quickSortHelper(base, end, size, cmp);
    if(idx > -1 ){
        // !!! idx는 0부터 시작하기 때문에,
        // idx를 포함하지 않는 왼쪽의 개수는 length-1에서 idx를 뺀 값. 
        quickSort(base, length-idx-1, size, cmp); 
        // idx는 0일 수 있다. 따라서 0인 경우에는 길이 1인것처럼 한다. 
        quickSort(base+(length-idx)*size, idx?, size, cmp);
    }
}

/** 헬퍼함수 실제로 부분 소트를 하고, 새로운 피봇의 인덱스를 리턴한다. **/
int quickSortHelper(void *base, void *end, int size, int(*cmp)(const void*, const void*)) {
    void* left = base+size; // 왼쪽 마크의 위치 
    void* right = end; // 오른쪽 마크의 위치 
    if(left >= right){ return -1;} // 만약 배열 길이가 0이나 1이면 -1을 리턴한다. 

    void* pivot = base; // 피봇
    int mark = 0; // right가 이동한 거리를 기록
    int met = 0; // 교차여부를 기록

    while(met != 1){
        while(left < end && cmp(left, pivot) <= 0){
            // left는 pivot보다 작으면 오른쪽으로 이동한다. 
            // 최대 end 까지 갈 수 있다. 
            left += size;
        }

        while(right > base+size && cmp(right, pivot) >= 0){
            // right는 pivot보다 크면 왼쪽으로 이동한다. 
            // 최대 base의 바로 오른쪽 칸 까지 갈 수 있다. 
            right -= size;
            mark += 1;
        }
        if(right > left){
            // 교차가 아직 일어나지 않음.
            swap(left, right, size);
        } else if(right <= left){
            // 교차가 일어남
            met = 1;
        }
    }
    swap(pivot, right, size);
    return mark;
}


int main(){
    test(quickSort); // test는 정렬함수 테스트용 함수 
    return 0;
}

selection_sort.c

#include "sort.h"

/**
    삽입정렬의 알고리듬 
    1. 두 번째 인덱스(1)부터 시작한다. 
    2. 바로 직전 인덱스의 값이 자신보다 크거나 같으면 비교 대상을 다시 한 인덱스 앞으로 돌린다. 
    3. 자신보다 작은 인덱스가 나타나면, 그 오른쪽으로 1.의 인덱스의 값을 삽입한다. 
    4. 삽입할 위치로부터, 1의 왼쪽 위치까지의 값을 한 칸씩 오른쪽으로 밀고 (memmove로 이동)
    5. 원래 값을 그 자리에 밀어 넣는다. 
**/
void insertion_sort(void *base, int length, int size, int(*cmp)(const void*, const void*)){
    void* saved = malloc(size);
    void* value;
    int i, j;
    for(j=1;j<length;j++){
        value = base+j*size;
        i = 1;
        while(j-i>=0){
            if(cmp(base+(j-i)*size, value) >= 0){
                i += 1;
            } else {
                break;
            }
        }
        if(i>1){
            i-=1;
            memmove(saved, value, size);
            memmove(base+(j-i+1)*size, base+(j-i)*size, i*size);
            memmove(base+(j-i)*size, saved, size);
        }
    }
    free(saved);
}

int main(){
    test(insertion_sort);
    return 0;
}

sort.h

#include <mem.h>
#include <stdio.h>
#include <stdlib.h>

/** 기본 정렬 알고리듬용 공통 헤더 
 *  
 * 기본 비교 함수 
 * 기본 스왑 함수 
 * 정렬 함수 테스트용 함수 
 * 
 * **) 정렬 함수의 기본 시그니처는 
 * void(*)(void* base, int length, int size, int(*cmp)(const void*, const void*))
 * 이며 
 *  - base : 배열 시작 번지
 *  - length: 배열의 원소 개수 
 *  - size: 배열의 원소의 크기 
 *  - cmp: 배열의 비교 함수, 두 원소를 비교하여, 앞의 것이 크면 1, 같으면 0, 작으면 -1을 리턴한다. 
**/


// HELPER MACROs
#define SWAP(a, p1, p2, type){\
    type _tmp__ = a[p1];\
    a[p1] = a[p2];\
    a[p2] = _tmp__;\
}

// fn Declarations
void swap(void *a, void *b, int size);
int compIntegerByPointer(const void* a, const void *b);
int compCharByPointer(const void* a, const void* b);

void printIntArray(void* base, int length);

// 정렬 함수를 테스트하는 함수
// 정렬 함수 포인터를 인자로 받는다. 
// 정렬함수 포인터 자체가 다시 비교 함수 포인터를 인자로 받으므로, 
// 인자의 타입 시그니처가 매우 복잡하다.
void test(void(*sortfn)(void*, int, int, int(*)(void const*, void const*)));


// 비교함수들 
// 정렬함수의 마지막 파라미터 타입과 동일하다. 
int compIntegerByPointer(const void* a, const void *b){
    int x, y;
    x = *(int*)(a);
    y = *(int*)(b);
    if (x > y) { return 1;}
    else if(x == y) { return 0; }
    return -1;
}


int compCharByPointer(const void* a, const void* b){
    int x, y;
    x = *(char*)(a);
    y = *(char*)(b);
    if (x > y) { return 1;}
    else if(x == y) { return 0; }
    return -1;
}

// 스왑함수
// 인자들의 타입을 정할 수 없으므로 임의의 포인터에 메모리를 할당하여 
// 메모리의 값을 바로 복사하도록 한다. 
void swap(void *a, void *b, int size){
    void *c = malloc(size);
    memmove(c, a, size);
    memmove(a, b, size);
    memmove(b, c, size);
    free(c);
}

void printIntArray(void *arr, int length){
    int* a = (int*)arr;
    int i;
    printf(">>> ");
    for(i=0;i<length;i++){
        printf("%d", a[i]);
    }
    printf("\n");
}

void test(void(*sortfn)(void*, int, int, int(*)(void const*, void const*))){
    int arr[] = {4, 6, 8, 9, 5, 1, 3};
    //int arr[] = {9,5,8,6};
    int l = sizeof(arr)/sizeof(int);
    int i;
    int *arr2 = (int*)malloc(sizeof(int) * l);
    memcpy(arr2, arr, sizeof(int)*l);
    for(i=0;i<l;i++){
        printf("%d", arr2[i]);
    }
    printf("\n");
    sortfn(arr2, l, sizeof(int), compIntegerByPointer);
    for(i=0;i<l;i++){
        printf("%d", arr2[i]);
    }
    printf("\n");
    free(arr2);
}