[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;
            }
        }
    }
}

選択ソートは、swapによって最大値mを最後に移動しない改良されたBubbleソートです.
これは、大きな値を探して、最後の要素と交互にする方法です.
したがって,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;
    }
}

要点
泡ソートは最後からソートし、選択ソートは前からソートしない!!!
前から並んで、後ろから、速度は同じです.
以上のように、選択ソートはBubbleソートに対する改良アルゴリズムである.これは以下のビデオで確認できます.
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ではなく各バイトを交換するように設計されています.
そこで,この2つの方法の性能を試験した.

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;
}