report/qsort.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

void quicksort(int arr[], int lo, int hi) {
    if (lo >= 0 && hi >= 0 && lo < hi) {
        int p = partition(A, lo, hi) 
        quicksort(A, lo, p)
        quicksort(A, p + 1, hi) 
    }
}

int partition(int arr[], int lo, int hi) {
    int pivot = arr[lo];
    int i = lo - 1, j = hi + 1;
    while (true) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        if (i >= j) break;
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    return j;
}