quick-sort.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 20
 
/** ___        _      _     ____             _   
 * / _ \ _   _(_) ___| | __/ ___|  ___  _ __| |_ 
 *| | | | | | | |/ __| |/ /\___ \ / _ \| '__| __|
 *| |_| | |_| | | (__|   <  ___) | (_) | |  | |_ 
 * \__\_\\__,_|_|\___|_|\_\|____/ \___/|_|   \__|
 */
 
 
void qcsort(int left, int right);
int partition(int left, int right);
void swap(int i, int j);
 
int data[N];
 
void check(){
    int i;
    printf("[");
    for(i=0;i<N;i++){
        printf("%d,", data[i]);
    }
    printf("]\n");
}
 
int main(void){
    srand(time(NULL));
    int i;
 
    printf("[");
    for(i=0;i<N;i++){
        data[i] = rand() % 100 + 1;
        printf("%d,", data[i]);
    }
    printf("]\n");
    qcsort(0, N-1);
    check();
    return 0;
}   
 
void qcsort(int left, int right){
    int j;
    if(left < right){
        j = partition(left, right);
        qcsort(left, j-1);
        qcsort(j+1, right);
    }
}
 
int partition(int left, int right){
    int pivot,i,j;
    pivot = data[left];
    i = left + 1;
    j = right;
    while(i<=j){
        while(i<=right && data[i] < pivot){
            i += 1;
        }
        while(data[j] > pivot){
            j -= 1;
        }
        if(i<=j){
            swap(i, j);
            i += 1;
            j -= 1;
        }
    }
    swap(left, j);
    return j;
}
 
void swap(int i, int j){
    int tmp;
    tmp = data[i];
    data[i] = data[j];
    data[j] = tmp;
}