; three quadratic sorts
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] }
function sort(A,n, i,switched,t) {
do {
switched = 0
for (i=2; i<=n; i++)
if (A[i] < A[i-1]) {
t = A[i-1]; A[i-1] = A[i]; A[i] = t
switched = 1 }
} while (switched) }
function sort(A,n, i,j,min,t) {
for (i=1; i<=n; i++) {
min = i
for (j=i+1; j<=n; j++)
if (A[j] < A[min])
min = j
t = A[min]; A[min] = A[i]; A[i] = t } }
function sort(A,n, i,j,t) {
for (i=2; i<=n; i++) {
t = A[i]
for (j=i; j>1 && t < A[j-1]; j--)
A[j] = A[j-1]
A[j] = t } }