[Algorithm] [Sort] Bubble, Selection

버블 정렬은 정렬을 하는 모습이 수면위의 물방울이 튀는것과 비슷해 버블 정렬이라고 한다.

버블 정렬의 원리는 가장 큰 값을 맨 뒤로 보내는 작업을 n-1번 반복한다.

n-1번을 반복하는 이유는 n개의 데이터에서 n-1개의 데이터를 정렬하면 나머지 1개는 자동으로 정렬되기 때문이다.

void bsort(int* base, int sz) {
    int i, j;
    for (i = 0; i < sz-1; i++){
        for (j = 0; j < sz-1-i; j++){
            if (base[j]>base[j + 1]){
                int t=base[j];
                base[j]=base[j+1];
                base[j+1]=t;
            }
        }
    }
}

선택 정렬은 버블정렬을 개선한 정렬로, 가장 큰값인 m을 swap을 통해 맨 뒤로 옮기는 것이 아닌,

큰 값을 찾아서, 맨뒤의 원소와 교체하는 방식이다.

따라서 swap연산의 횟수를 줄여 속도를 개선한다.

void ssort(int* base, int sz) {
    int i, j;
    for (i = 0; i < sz - 1; i++){
        int m = 0;
        for (j = 1; j < sz - i - 1; j++){
            if (base[m] < base[j]){
                m = j;
            }
        }
        int t = base[m];
        base[m] = base[sz - 1 - i];
        base[sz - 1 - i] = t;
    }
}

요점

버블정렬은 맨 뒤부터 정렬, 선택정렬은 앞에서부터 정렬이 되는것이 아니다!!!!

앞에서부터 정렬을 하나, 뒤에서부터 하나 속도는 같다.

위에서 보듯이 선택정렬은 버블정렬을 개선한 알고리즘이다. 이는 아래 동영상으로 확인 할 수 있다.

https://youtu.be/ZZuD6iUe3Pc

이 bubble sort 을 C언어에서 Generic하게 구현을 하면 아래와 같다.

void bsort(void* base, size_t numOfElement, size_t sizeOfElement, int(*cmp)(const void*, const void*)) {
    size_t i, j, k;
    for (i = 0; i < numOfElement - 1; i++){
        for (j = 0; j < numOfElement - i - 1; j++){
            if (cmp(((char*)base) + (j*sizeOfElement), ((char*)base) + ((j + 1)*sizeOfElement))>0){
                char* a = ((char*)base) + (j*sizeOfElement);
                char* b = ((char*)base) + ((j + 1)*sizeOfElement);
                for (k = 0; k < sizeOfElement; k++){
                    char t = *a;
                    *a = *b;
                    *b = t;
                    a++;
                    b++;
                }
            }
        }
    }
}

void* 인 자료에 대한 swap 연산은 alloca + memcpy가 아닌 각 바이트를 swap 하는 방식으로 설계하였다.

그래서 이 두가지 방법에 대한 성능을 측정 해 보았다.

gcc 에서는 최적화와 아닌것 모두 별반 차이가 없지만 VS에서는 alloca+memcpy 방식이 최적화시에 매우 빨랐다.

아래는 성능측정에 사용한 코드이다.

#include<stdio.h>
#include<malloc.h>
#include<memory.h>
#include<time.h>
#include<stdlib.h>
void bsort(void* base, size_t numOfElement
    , size_t sizeOfElement, int(*cmp)(const void*, const void*)) {
    size_t i, j, k;
    char t;
    for (i = 0; i < numOfElement - 1; i++){
        for (j = 0; j < numOfElement - i - 1; j++){
            if (cmp(((char*)base) + (j*sizeOfElement), ((char*)base) + ((j + 1)*sizeOfElement))>0){
                char* a = ((char*)base) + (j*sizeOfElement);
                char* b = ((char*)base) + ((j + 1)*sizeOfElement);
                k = sizeOfElement;
                while (k--){
                    t = *a;
                    *a = *b;
                    *b = t;
                    a++;
                    b++;
                }
            }
        }
    }
}
void bsort2(void* base, size_t numOfElement
    , size_t sizeOfElement, int(*cmp)(const void*, const void*)) {
    size_t i, j;
    void* temp = _alloca(sizeOfElement);
    for (i = 0; i < numOfElement - 1; i++){
        for (j = 0; j < numOfElement - i - 1; j++){
            if (cmp(((char*)base) + (j*sizeOfElement), ((char*)base) + ((j + 1)*sizeOfElement))>0){
                char* a = ((char*)base) + (j*sizeOfElement);
                char* b = ((char*)base) + ((j + 1)*sizeOfElement);
                memcpy(temp, a, sizeOfElement);
                memcpy(a, b, sizeOfElement);
                memcpy(b, temp, sizeOfElement);
            }
        }
    }
}
int compare(const void* a, const void* b) {
    return *(int*)a<*(int*)b ? -1 : *(int*)a>*(int*)b;
}
#define MAXN 10000
int main() {
    int* arr = (int*)calloc(MAXN, sizeof(int));
    int* arr2 = (int*)calloc(MAXN, sizeof(int));
    int i;
    for (i = 0; i < MAXN; i++){
        arr[i] = rand();
    }
    double start;
    double a = 0.0,b = 0.0;
    for (i = 0; i < 10; i++){
        memcpy(arr2, arr, MAXN*sizeof(int));
        start = clock();
        bsort2(arr2, MAXN, sizeof(int), compare);
        b += (clock() - start) / CLOCKS_PER_SEC;

        memcpy(arr2, arr, MAXN*sizeof(int));
        start = clock();
        bsort(arr2, MAXN, sizeof(int), compare);
        a += (clock() - start) / CLOCKS_PER_SEC;



    }
    printf("char swap : %f\n", a/10);
    printf("mem swap : %f\n", b/10);
    return 0;
}