[Algorithm] Bubble sort, Insert sort, Select sort, Radix sort

기존에 작성되어있는것을 지우고 다시 쓰려고 했지만, 내가 얼마나 초짜인지 각성하기위해 새롭게 포스팅을 합니다.
맨처음 작성한 소스 부끄러운 내소스 입니다.

 

기존에 DATA_TYPE을 한 이유가 대입과 swap때문에 했는데,

그럴필요없이, memxxx함수를 이용해 가능하다는것을 알고, (qsort에서 그렇게 하는것을 보고) 다시 짜보았습니다.

 

와.....너무좋다. 이렇게 간단한걸, 노가다로 짠 내자신이....흑흑

 

main.c

#include "dol9_sort.h"

int compare(const void *data1, const void *data2)
{
    return *(char*)data1 - *(char*)data2;
}

int main(int argc, char *argv[])
{
    int input[10] = {3, 2, 5, 6, 1, 4, 8, 9, 7, 0};
    //char input[10] = {'d', 'c', 'e', 'b', 'w', 'z', 'q', 'x'};
    int i;

    for (i = 0; i < 10; i++) {
        printf("input[%d] : %d\t", i, input[i]);
        if (i % 3 == 0)
            printf("\n");
    }

    //select_sort(input, 8, sizeof(char), compare);
    insert_sort(input, 10, sizeof(int), compare);
    //bubble_sort(input, 8, sizeof(char), compare);

    for (i = 0; i < 10; i++) {
        printf("input[%d] : %d\t", i, input[i]);
        if (i % 3 == 0)
            printf("\n");
    }

    return 0;
}

dol9_sort.h

#ifndef _DOL9_SORT_H_
#define _DOL9_SORT_H_

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

#ifdef TEST
#define LOG(x)  (printf x)
#else
#define LOG(x)
#endif

typedef int (*cmp)(const void* , const void*);

int bubble_sort(void *data, int max, int data_size, cmp compare);
int insert_sort(void *data, int max, int data_size, cmp compare);
int select_sort(void *data, int max, int data_size, cmp compare);
int radixsort(int *data, int max, int maxdigit,	 int system);

#endif

 

dol9_sort.c

#include "dol9_sort.h"
#include <string.h>
#include <stdlib.h>

void memswap(void *m1, void *m2, int n);

int bubble_sort(void *data, int max, int data_size, cmp compare)
{
    int i, j;

    for(i = max; i > 0; i--) {
        for(j = 0; j < i-1; j++) {
            LOG((" %d %c  %c  ", j, *(char*)(data+(j*data_size)), *(char*)(data+((j+1)*data_size))));
            LOG(("compare value :%d\n",compare(data+(j*data_size), data+((j+1)*data_size))));
            if(compare((data+(j*data_size)), (data+((j+1)*data_size))) > 0) {
                memswap(data+(j*data_size), data+((j+1)*data_size), data_size);
            }
        }
    }
    return 1;
}

int select_sort(void *data, int max, int data_size, cmp compare)
{
    int i, j;
    int minidx;

    minidx = 0;
    for (i = 0; i < max; i++) {
        minidx = i;
        for (j = i+1; j < max; j++) {
            if (compare(data+(minidx*data_size), data+(j*data_size)) == 1) {
                minidx = j;
            }
        }
        memswap(data+(i*data_size), data+(minidx*data_size), data_size);
    }
    return 1;
}

int insert_sort(void *data, int max, int data_size, cmp compare)
{
    void *ivalue;
    int i, j;

    ivalue = malloc(data_size);
    for (i = 1; i < max; i++) {
        //정렬이 이미 된경우
        if (compare(data+((i-1)*data_size), data+(i*data_size)) < 1)
            continue;
        memcpy(ivalue, data+(i*data_size), data_size);
        for (j = 0; compare(ivalue, data+(j*data_size))>0 && j<i; j++) ;

LOG(("%c  %c ", *(char*)(data+i), *(char*)(data+j)));

        if (j != i) {
            memmove(data+((j+1)*data_size), data+(j*data_size), ((i-j)*data_size));
            memmove(data+(j*data_size), ivalue, data_size);
        }
    }
    free(ivalue);

    return 1;
}

nt radixsort(int *data, int max,	// nums of data
                int maxdigit,	// ex) if max Num is 20321,  maxdigit is 5
                int system)		// digit = 10, oct = 8, hex = 16
{
    int i, n;
    int pval, idx;
    int *count, *temp;

    count = (int*)malloc(system*sizeof(int));
    temp = (int*)malloc(max*sizeof(int));

    for (n = 0; n < maxdigit; n++) {
        for (i = 0; i < system; i++) {
            count[i] = 0;
        }
        pval = (int)pow((double)system, n);

        for (i = 0; i < max; i++) {
            idx = (data[i]/pval) % system;
            count[idx]++;
        }
        for (i = 1; i < system; i++) {
            count[i] = count[i] + count[i-1];
        }

        for (i = max-1; i >=0; i--) {
            idx = (int)(data[i]/pval) % system;
            memcpy(temp+(count[idx]-1), data+i, sizeof(int));
            count[idx] = count[idx]-1;
        }

        memcpy(data, temp, sizeof(int) * max);
    }
    free(temp);
    free(count);
    return 0;
}

//http://forge.voodooprojects.org/p/chameleon/source/tree/HEAD/branches/meklort/i386/modules/klibc/memswap.c

void memswap(void *m1, void *m2, int n)
{
    char *p = m1;
    char *q = m2;
    char tmp;

    while (n--) {
        tmp = *p;
        *p = *q;
        *q = tmp;

        p++; q++;
    }
}