# quick sort
BEGIN {
for (i=0; i<=20; i++)
tester(i)
tester(1000) }
function tester(i) {
genid(x,i); sort(x,i); check(x,i); clear(x)
gensort(x,i); sort(x,i); check(x,i); clear(x)
genrev(x,i); sort(x,i); check(x,i); clear(x)
genrand(x,i); sort(x,i); check(x,i); clear(x) }
function genid(x,n, i) {
for (i=1; i<=n; i++)
x[i] = 1 }
function gensort(x,n, i) {
for (i=1; i<=n; i++)
x[i] = i }
function genrev(x,n, i) {
for (i=1; i<=n; i++)
x[i] = n + 1 - i }
function genrand(x,n, i) {
for (i=1; i<=n; i++)
x[i] = int(n * rand()) }
function check(x,n, i) {
for (i=1; i<n; i++)
if (x[i+1]+0 < x[i]+0) {
printf "error in sort"
exit } }
function clear(x, i) {
for (i in x)
delete x[i] }
# simple version using lomuto partition
function swap(A,i,j, t) {
t = A[i]; A[i] = A[j]; A[j] = t }
function qsort(A,lo,hi, i,last) {
if (lo >= hi)
return
swap(A, lo, lo + int((hi-lo+1) * rand()))
last = lo
for (i=lo+1; i<=hi; i++)
if (A[i] < A[lo])
swap(A, ++last, i)
swap(A, lo, last)
qsort(A, lo, last-1)
qsort(A, last+1, hi) }
function sort(A,n) { qsort(A, 1, n) }
# move swaps inline and eliminate recursion
function sort(A,n, lo,hi,i,j,t,s,p) {
lo = 1; hi = n; p = 2
do {
if (hi > lo) {
j = lo + int((hi - lo + 1) * rand())
t = A[lo]; A[lo] = A[j]; A[j] = t
j = lo
for (i=lo+1; i<=hi; i++)
if (A[i] < A[lo]) {
j++; t = A[j]; A[j] = A[i]; A[i] = t }
t = A[lo]; A[lo] = A[j]; A[j] = t
if ((j - lo) < (hi - j)) {
s[p] = lo; s[p+1] = j - 1; lo = j + 1 }
else { s[p] = j + 1; s[p+1] = hi; hi = j - 1 }
p += 2 }
else { p -= 2; lo = s[p]; hi = s[p+1] }
} while (p > 0) }
# insert sort small sub-arrays
function sort(A,n, lo,hi,i,j,t,s,p) {
lo = 1; hi = n; p = 2
do {
if (hi - lo > 10) {
j = lo + int((hi - lo + 1) * rand())
t = A[lo]; A[lo] = A[j]; A[j] = t
j = lo
for (i=lo+1; i<=hi; i++)
if (A[i] < A[lo]) {
j++; t = A[j]; A[j] = A[i]; A[i] = t }
t = A[lo]; A[lo] = A[j]; A[j] = t
if ((j - lo) < (hi - j)) {
s[p] = lo; s[p+1] = j - 1; lo = j + 1 }
else { s[p] = j + 1; s[p+1] = hi; hi = j - 1 }
p += 2 }
else { p -= 2; lo = s[p]; hi = s[p+1] }
} while (p > 0)
for (i=2; i<=n; i++) {
t = A[i]
for (j=i; j>1 && A[j-1] > t; j--)
A[j] = A[j-1]
A[j] = t } }
# approaching-pointers partition
function sort(A,n, lo,hi,i,j,t,v,s,p) {
lo = 1; hi = n; p = 2
do {
if (hi - lo > 10) {
i = lo + int((hi - lo + 1) * rand())
t = A[lo]; A[lo] = A[i]; A[i] = t
j = lo + int((hi - lo + 1) * rand())
t = A[hi]; A[hi] = A[j]; A[j] = t
if (A[hi] < A[lo]) {
t = A[lo]; A[lo] = A[hi]; A[hi] = t }
v = A[hi]; i = lo; j = hi
do {
do { i++ } while (A[i] < v)
do { j-- } while (v < A[j])
t = A[i]; A[i] = A[j]; A[j] = t
} while (i < j)
t = A[i]; A[i] = A[hi]; A[hi] = t
if ((i - lo) > (hi - i)) {
s[p] = lo; s[p+1] = i - 1; lo = i + 1 }
else { s[p] = i + 1; s[p+1] = hi; hi = i - 1 }
p += 2 }
else { p -= 2; lo = s[p]; hi = s[p+1] }
} while (p > 0)
for (i=2; i<=n; i++) {
t = A[i]
for (j=i; j>1 && A[j-1] > t; j--)
A[j] = A[j-1]
A[j] = t } }