#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define LARGEARRAYSIZE 1000000
#define VERYLARGEARRAYSIZE 100000000
extern void quicksort( int [], int );
extern void swap( int [], int, int );
extern void print( int [], int );
extern void stressTest0();
extern int cmpInts( int *, int *);
extern int arrayCompare( int [], int [], int );
extern int *arrayDup( int [], int );
extern void randomTest( int, int );
extern void autoCheck( int [], int, char * );
int main() {
// simple usage
int A[] = {3,2,1,5,4};
int N = sizeof(A)/sizeof(A[0]);
quicksort( A, N );
print(A, N);
// stress test on random values with automated checker
randomTest(LARGEARRAYSIZE, INT_MAX);
randomTest(VERYLARGEARRAYSIZE, INT_MAX);
// stress test on array with only two values
randomTest(LARGEARRAYSIZE, 2);
randomTest(VERYLARGEARRAYSIZE, 2);
return 0;
}
void randomTest(int N, int range) {
int *A
= malloc( N
* sizeof(int) ); int i;
for ( i = 0 ; i < N; i++ ) {
}
autoCheck( A, N, "randomTest" );
}
void autoCheck( int A[], int N, char *name ) {
int *Adup = arrayDup( A, N);
quicksort(A, N);
qsort( Adup
, N
, sizeof(int), cmpInts
); if ( 0 == arrayCompare( Adup, A, N ) ) {
} else {
}
}
int *
arrayDup( int A[], int N ) {
int i;
int *dup
= malloc( N
* sizeof( int ) ); for ( i = 0 ; i < N; i++ ) {
dup[i] = A[i];
}
return dup;
}
int arrayCompare( int *A, int *B, int N ) {
int i;
for ( i = 0 ; i < N; i++ ) {
if ( A[i] != B[i] ) {
return 0;
}
}
return 1;
}
int cmpInts( int *x, int *y ) {
if ( *x < *y ) {
return -1;
} else if ( *x > *y ) {
return 1;
} else {
return 0;
}
}
/* quicksort: sort v[0]...v[n-1] into increasing order */
void quicksort(int v[], int n) {
int i, last;
if (n <= 1) /* nothing to do */
return;
swap
(v
, 0, rand() % n
) ; /* move pivot elem to v[0] */ last = 0;
for (i=1; i<n; i++) { /* partition a */
if (v[i] < v[0]) {
swap(v, ++last, i);
}
}
swap(v, 0, last); /* restore pivot */
quicksort(v, last); /* recursively sort */
quicksort(v+last+1, n-last-1); /* each part */
}
/* swap: interchange v [i] and v[j] */
void swap(int v[], int i, int j) {
int temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
void print( int A[], int N ) {
int i;
for ( i = 0; i < N; i++ ) {
printf("%d%c", A
[i
], ( i
== N
- 1 ) ? '\n' : ',' ); }
}
CiNpbmNsdWRlIDxzdGRpby5oPgojaW5jbHVkZSA8c3RkbGliLmg+CiNpbmNsdWRlIDxsaW1pdHMuaD4KCiNkZWZpbmUgTEFSR0VBUlJBWVNJWkUgMTAwMDAwMAojZGVmaW5lIFZFUllMQVJHRUFSUkFZU0laRSAxMDAwMDAwMDAKCmV4dGVybiB2b2lkIHF1aWNrc29ydCggaW50IFtdLCBpbnQgKTsKZXh0ZXJuIHZvaWQgc3dhcCggaW50IFtdLCBpbnQsIGludCApOwpleHRlcm4gdm9pZCBwcmludCggaW50IFtdLCBpbnQgKTsKZXh0ZXJuIHZvaWQgc3RyZXNzVGVzdDAoKTsKZXh0ZXJuIGludCBjbXBJbnRzKCBpbnQgKiwgaW50ICopOwpleHRlcm4gaW50IGFycmF5Q29tcGFyZSggaW50IFtdLCBpbnQgW10sIGludCApOwpleHRlcm4gaW50ICphcnJheUR1cCggaW50IFtdLCBpbnQgKTsKZXh0ZXJuIHZvaWQgcmFuZG9tVGVzdCggaW50LCBpbnQgKTsKZXh0ZXJuIHZvaWQgYXV0b0NoZWNrKCBpbnQgW10sIGludCwgY2hhciAqICk7CgoKaW50IG1haW4oKSB7CiAgLy8gc2ltcGxlIHVzYWdlCiAgaW50IEFbXSA9IHszLDIsMSw1LDR9OwogIGludCBOID0gc2l6ZW9mKEEpL3NpemVvZihBWzBdKTsKICBxdWlja3NvcnQoIEEsIE4gKTsKICBwcmludChBLCBOKTsKCiAgLy8gc3RyZXNzIHRlc3Qgb24gcmFuZG9tIHZhbHVlcyB3aXRoIGF1dG9tYXRlZCBjaGVja2VyCiAgcmFuZG9tVGVzdChMQVJHRUFSUkFZU0laRSwgSU5UX01BWCk7CiAgcmFuZG9tVGVzdChWRVJZTEFSR0VBUlJBWVNJWkUsIElOVF9NQVgpOwoKICAvLyBzdHJlc3MgdGVzdCBvbiBhcnJheSB3aXRoIG9ubHkgdHdvIHZhbHVlcwogIHJhbmRvbVRlc3QoTEFSR0VBUlJBWVNJWkUsIDIpOwogIHJhbmRvbVRlc3QoVkVSWUxBUkdFQVJSQVlTSVpFLCAyKTsKCiAgcmV0dXJuIDA7Cn0KCnZvaWQgcmFuZG9tVGVzdChpbnQgTiwgaW50IHJhbmdlKSB7CiAgaW50ICpBID0gbWFsbG9jKCBOICogc2l6ZW9mKGludCkgKTsKICBpbnQgaTsKICBmb3IgKCBpID0gMCA7IGkgPCBOOyBpKysgKSB7CiAgICBBW2ldID0gcmFuZCgpICUgcmFuZ2U7CiAgfQogIGF1dG9DaGVjayggQSwgTiwgInJhbmRvbVRlc3QiICk7Cn0KCgp2b2lkIGF1dG9DaGVjayggaW50IEFbXSwgaW50IE4sIGNoYXIgKm5hbWUgKSB7CiAgaW50ICpBZHVwID0gYXJyYXlEdXAoIEEsIE4pOwogIHF1aWNrc29ydChBLCBOKTsKICBxc29ydCggQWR1cCwgTiwgc2l6ZW9mKGludCksIGNtcEludHMgKTsKICBpZiAoIDAgPT0gYXJyYXlDb21wYXJlKCBBZHVwLCBBLCBOICkgKSB7CiAgICBwcmludGYoIiVzIGZhaWxlZFxuIiwgbmFtZSApOwogIH0gZWxzZSB7CiAgICBwcmludGYoIiVzIHBhc3NlZFxuIiwgbmFtZSApOwogIH0KfQoKaW50ICoKYXJyYXlEdXAoIGludCBBW10sIGludCBOICkgewogIGludCBpOwogIGludCAqZHVwID0gbWFsbG9jKCBOICogc2l6ZW9mKCBpbnQgKSApOwogIGZvciAoIGkgPSAwIDsgaSA8IE47IGkrKyApIHsKICAgIGR1cFtpXSA9IEFbaV07CiAgfQogIHJldHVybiBkdXA7Cn0KCmludCBhcnJheUNvbXBhcmUoIGludCAqQSwgaW50ICpCLCBpbnQgTiApIHsKICBpbnQgaTsKICBmb3IgKCBpID0gMCA7IGkgPCBOOyBpKysgKSB7CiAgICBpZiAoIEFbaV0gIT0gQltpXSApIHsKICAgICAgcmV0dXJuIDA7CiAgICB9CiAgfQogIHJldHVybiAxOwp9CgoKaW50IGNtcEludHMoIGludCAqeCwgaW50ICp5ICkgewogIGlmICggICp4IDwgKnkgKSB7CiAgICByZXR1cm4gLTE7CiAgfSBlbHNlIGlmICggKnggPiAqeSApIHsKICAgIHJldHVybiAxOwogIH0gZWxzZSB7CiAgICByZXR1cm4gMDsKICB9Cn0KCgoKLyogcXVpY2tzb3J0OiBzb3J0IHZbMF0uLi52W24tMV0gaW50byBpbmNyZWFzaW5nIG9yZGVyICovCnZvaWQgcXVpY2tzb3J0KGludCB2W10sIGludCBuKSB7CiAgaW50IGksIGxhc3Q7CiAgaWYgKG4gPD0gMSkgLyogbm90aGluZyB0byBkbyAqLwogIHJldHVybjsKICBzd2FwKHYsIDAsIHJhbmQoKSAlIG4pIDsgLyogbW92ZSBwaXZvdCBlbGVtIHRvIHZbMF0gKi8KICBsYXN0ID0gMDsKICBmb3IgKGk9MTsgaTxuOyBpKyspIHsgLyogcGFydGl0aW9uIGEgKi8KICAgIGlmICh2W2ldIDwgdlswXSkgewogICAgICBzd2FwKHYsICsrbGFzdCwgaSk7CiAgICB9CiAgfQogIHN3YXAodiwgMCwgbGFzdCk7IC8qIHJlc3RvcmUgcGl2b3QgKi8KICBxdWlja3NvcnQodiwgbGFzdCk7IC8qIHJlY3Vyc2l2ZWx5IHNvcnQgKi8KICBxdWlja3NvcnQoditsYXN0KzEsIG4tbGFzdC0xKTsgLyogZWFjaCBwYXJ0ICovCn0KCi8qIHN3YXA6IGludGVyY2hhbmdlIHYgW2ldIGFuZCB2W2pdICovCnZvaWQgc3dhcChpbnQgdltdLCBpbnQgaSwgaW50IGopIHsKICBpbnQgdGVtcDsKICB0ZW1wID0gdltpXTsKICB2W2ldID0gdltqXTsKICB2W2pdID0gdGVtcDsKfQoKdm9pZCBwcmludCggaW50IEFbXSwgaW50IE4gKSB7CiAgaW50IGk7CiAgZm9yICggaSA9IDA7IGkgPCBOOyBpKysgKSB7CiAgICBwcmludGYoIiVkJWMiLCBBW2ldLCAoIGkgPT0gTiAtIDEgKSA/ICdcbicgOiAnLCcgKTsKICB9Cn0=