; 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 } }