快速排序

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

int cmp(const void *pa, const void *pb) {
    return *(int*)pa - *(int*)pb;
}

void printArr(int a[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

void swap(int arr[], int a, int b) {
    int tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
}

void qsortKR(int arr[], int left, int right) {
    if (left >= right) {
        return;
    }
    int last = left;
    swap(arr, left, (left+right)/2);
    for (int i = left+1; i < right; i++) {
        if (arr[i] < arr[left]) {
            swap(arr, i, ++last);
        }
    }
    swap(arr, left, last);
    qsortKR(arr, left, last);
    qsortKR(arr, last+1, right);
}

int main(int argc, char **argv)
{
    printf("%ld\n", sizeof(int));
    int num = atoi(argv[1]);
    int *arr = (int*)malloc(sizeof(int) * num);
    int *arr2 = (int*)malloc(sizeof(int) * num);
    for (int i = 0; i < num; i++) {
        arr[i] = rand();
        arr2[i] = arr[i];
    }

    clock_t start1 = clock();
    qsort(arr, num, sizeof(int), cmp);
    clock_t start2 = clock();
    //printArr(arr, num);

    clock_t start3 = clock();
    qsortKR(arr2, 0, num);
    clock_t start4 = clock();
    //printArr(arr2, num);
    
    for(int i = 0; i < num; i++) {
        if (arr[i] != arr2[i]) {
            printf("error!\n");
            break;
        }
    }

    printf("stdlib %lf qsortKR %lf\n", (start2-start1)*1.0/CLOCKS_PER_SEC, (start4-start3)*1.0/CLOCKS_PER_SEC);

    return 0;
}