クイックソート メモ

いつもクイックソートの書き方がわからなくなる（セグフォとかで正確に実行できない）ことが多いので、メモとしてqsortのC言語によるアルゴリズムを書いておく。今回はCの標準ライブラリであるqsort関数とどちらが実行速度が大きいかを比較した。

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

void myqsort(int left, int right, int A[]) {
    if (left >= right) return;
    int i = left, j = right; // i = 0, j = n-1
    // オーバーフロー対策でこのようにmiddleを求める
    int pivot = (j-i)/2+i;
    int val = A[pivot];
    while(1) {
        // iとjが交わる時は1以下で収まる．交わったらすぐにwhileの条件を満たさなくなるから．
        while(A[i] < val) i++;
        while(A[j] > val) j--;
        if (i >= j) break; 
        int tmp = A[i]; A[i] = A[j]; A[j] = tmp;
        i++; j--;
    }
    // A[i] はvalより大きいが，A[k]は任意のk (<= i-1)でvalより小さい
    myqsort(left, i-1, A);
    // A[i] はvalより小さいが，A[k]は任意のk (>= j+1)でvalより大きい
    myqsort(j+1, right, A);
}

// ライブラリのqsort関数で用いる比較関数
int cmpnum(const void *n1, const void *n2) {
    if (*(int*)n1 > *(int*)n2) {
        return 1;
    } else if (*(int*)n1 < *(int*)n2) {
        return -1;
    } else {
        return 0;
    }
}

int main() {
    int n = 10000;
    int B[n];
    for (int i = 0; i < n; i++) {
        B[i] = rand() % 100000;
    }
    clock_t start = clock();
    // 自作qsort関数
    myqsort(0, n-1, B);
    clock_t end = clock();
    printf("time = %f ", (double)(end - start)/CLOCKS_PER_SEC);

    for (int i = 0; i < n; i++) {
        B[i] = rand() % 100000;
    }
    size_t int_size = sizeof(int);
    clock_t start1 = clock();
    // cの標準ライブラリを使用
    qsort(B, n, int_size, cmpnum);
    clock_t end1 = clock();
    printf("time = %f ", (double)(end1 - start1)/CLOCKS_PER_SEC);
}

実行結果（単位 s）

myqsort	qsort
0.079998	0.160001

意外と自分で作ったqsortの方が早かった。