ABOUT ME

-

인기 태그


kafka elastic_search redis
Today
-
Yesterday
-
Total
-
  • [Algorithm] Bubble sort, Insert sort, Select sort, Radix sort
    개발하면서/Algorithm,DS,PS 2011. 1. 5. 22:22

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

     

    기존에 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++;
        }
    }

    댓글 0

Designed by Tistory.