isort.awk # insertion sort
isort.awk 
isort.awk     { A[NR] = $0 }
isort.awk 
isort.awk END { isort(A, NR)
isort.awk       for (i = 1; i <= NR; i++)
isort.awk           print A[i]
isort.awk     }
isort.awk 
isort.awk # isort - sort A[1..n] by insertion
isort.awk 
isort.awk function isort(A,n,     i,j,t) {
isort.awk     for (i = 2; i <= n; i++)
isort.awk         for (j = i; j > 1 && A[j-1] > A[j]; j--) {
isort.awk             # swap A[j-1] and A[j]
isort.awk             t = A[j-1]; A[j-1] = A[j]; A[j] = t
isort.awk         }
isort.awk }
ptest.awk # batch test of sorting routines
ptest.awk 
ptest.awk BEGIN {
ptest.awk     print "    0 elements"
ptest.awk     isort(A, 0); check(A, 0)    
ptest.awk     print "    1 element"
ptest.awk     genid(A, 1); isort(A, 1); check(A, 1)
ptest.awk     
ptest.awk     n = 10
ptest.awk     print "    " n " random integers"
ptest.awk     genrand(A, n); isort(A, n); check(A, n)
ptest.awk     
ptest.awk     print "    " n " sorted integers"
ptest.awk     gensort(A, n); isort(A, n); check(A, n)
ptest.awk     
ptest.awk     print "    " n " reverse-sorted integers"
ptest.awk     genrev(A, n); isort(A, n); check(A, n)
ptest.awk     
ptest.awk     print "    " n " identical integers"
ptest.awk     genid(A, n); isort(A, n); check(A, n)
ptest.awk }
ptest.awk 
ptest.awk function isort(A,n,     i,j,t) {
ptest.awk     for (i = 2; i <= n; i++)
ptest.awk         for (j = i; j > 1 && A[j-1] > A[j]; j--) {
ptest.awk             # swap A[j-1] and A[j]
ptest.awk             t = A[j-1]; A[j-1] = A[j]; A[j] = t
ptest.awk         }
ptest.awk }
ptest.awk 
ptest.awk # test-generation and sorting routines...
ptest.awk 
ptest.awk function check(A,n,   i) {
ptest.awk     for (i = 1; i < n; i++)
ptest.awk         if (A[i] > A[i+1])
ptest.awk             printf("array is not sorted, element %d\n", i)
ptest.awk }
ptest.awk 
ptest.awk function genrand(A,n,  i) { # put n random integers in A
ptest.awk     for (i = 1; i <= n; i++)
ptest.awk         A[i] = int(n*rand())
ptest.awk }
ptest.awk 
ptest.awk function gensort(A,n,  i) { # put n sorted integers in A
ptest.awk     for (i = 1; i <= n; i++)
ptest.awk         A[i] = i
ptest.awk }
ptest.awk 
ptest.awk function genrev(A,n,  i) {  # put n reverse-sorted integers
ptest.awk     for (i = 1; i <= n; i++)  # in A
ptest.awk         A[i] = n+1-i
ptest.awk }
ptest.awk 
ptest.awk function genid(A,n,  i) {   # put n identical integers in A
ptest.awk     for (i = 1; i <= n; i++)
ptest.awk         A[i] = 1
ptest.awk }
scaff.awk BEGIN { srand(1111) }
scaff.awk { print }
scaff.awk # interactive test framework for sort routines
scaff.awk 
scaff.awk /^[0-9]+.*rand/ { n = $1; genrand(A, n); dump(A, n); next }
scaff.awk /^[0-9]+.*id/   { n = $1; genid(A, n); dump(A, n); next }
scaff.awk /^[0-9]+.*sort/ { n = $1; gensort(A, n); dump(A, n); next }
scaff.awk /^[0-9]+.*rev/  { n = $1; genrev(A, n); dump(A, n); next }
scaff.awk /^data/ {   # use data right from this line
scaff.awk 	for (i = 2; i <= NF; i++)
scaff.awk 		A[i-1] = $i
scaff.awk 	n = NF - 1
scaff.awk 	next
scaff.awk }
scaff.awk /q.*sort/ { qsort(A, 1, n); check(A, n); dump(A, n); next }
scaff.awk /h.*sort/ { hsort(A, n); check(A, n); dump(A, n); next }
scaff.awk /i.*sort/ { isort(A, n); check(A, n); dump(A, n); next }
scaff.awk /./  { print "data ... | N [rand|id|sort|rev]; [qhi]sort" }
scaff.awk 
scaff.awk function dump(A, n) {    # print A[1]..A[n]
scaff.awk 	for (i = 1; i <= n; i++)
scaff.awk 		printf(" %s", A[i])
scaff.awk 	printf("\n")
scaff.awk }
scaff.awk 
scaff.awk # test-generation and sorting routines ...
scaff.awk 
scaff.awk function genrand(A,n,    i) { # put n random integers in A
scaff.awk     for (i = 1; i <= n; i++)
scaff.awk         A[i] = int(n*rand())
scaff.awk }
scaff.awk 
scaff.awk function gensort(A,n,    i) { # put n sorted integers in A
scaff.awk     for (i = 1; i <= n; i++)
scaff.awk         A[i] = i
scaff.awk }
scaff.awk 
scaff.awk function genrev(A,n,    i) { # put n reverse-sorted integers in A
scaff.awk     for (i = 1; i <= n; i++)
scaff.awk         A[i] = n+1-i
scaff.awk }
scaff.awk 
scaff.awk function genid(A,n,    i) { # put n identical integers in A
scaff.awk     for (i = 1; i <= n; i++)
scaff.awk         A[i] = 1
scaff.awk }
scaff.awk 
scaff.awk function check(A,n,   i) {
scaff.awk     for (i = 1; i < n; i++)
scaff.awk         if (A[i] > A[i+1])
scaff.awk             printf("error: array is not sorted, element %d\n", i)
scaff.awk }
scaff.awk function isort(A,n,        i,j,t) {
scaff.awk       for (i = 2; i <= n; i++)
scaff.awk           for (j = i; j > 1 && A[j-1] > A[j]; j--) {
scaff.awk               # swap A[j-1] and A[j]
scaff.awk               t = A[j-1]; A[j-1] = A[j]; A[j] = t
scaff.awk           }
scaff.awk }
scaff.awk 
scaff.awk function qsort(A,left,right,   i,last) {
scaff.awk      if (left >= right)  # do nothing if array contains
scaff.awk          return          # at most one element
scaff.awk      swap(A, left, left + int((right-left+1)*rand()))
scaff.awk      last = left
scaff.awk      for (i = left+1; i <= right; i++)
scaff.awk          if (A[i] < A[left])
scaff.awk              swap(A, ++last, i)
scaff.awk      swap(A, left, last)
scaff.awk      qsort(A, left, last-1)
scaff.awk      qsort(A, last+1, right)
scaff.awk }
scaff.awk 
scaff.awk function swap(A,i,j,   t) {
scaff.awk      t = A[i]; A[i] = A[j]; A[j] = t
scaff.awk }
scaff.awk 
scaff.awk function hsort(A,right,  i) {
scaff.awk      for (i = int(right/2); i >= 1; i--)
scaff.awk           heapify(A, i, right)
scaff.awk      for (i = right; i > 1; i--) {
scaff.awk           swap(A, 1, i)
scaff.awk           heapify(A, 1, i-1)
scaff.awk      }
scaff.awk }
scaff.awk 
scaff.awk function heapify(A,left,right,   p,c) {
scaff.awk      for (p = left; (c = 2*p) <= right; p = c) {
scaff.awk          if (c < right && A[c+1] > A[c])
scaff.awk              c++
scaff.awk          if (A[p] < A[c])
scaff.awk              swap(A, c, p)
scaff.awk      }
scaff.awk }
iisort.awk # count comparisons and exchanges in isort
iisort.awk 
iisort.awk     { A[NR] = $0 }
iisort.awk END { comp = exch = 0
iisort.awk       isort(A, NR)
iisort.awk       print "isort", NR, comp, exch
iisort.awk     }
iisort.awk 
iisort.awk function isort(A,n,     i,j,t) {  # insertion sort
iisort.awk     for (i = 2; i <= n; i++)      # with counters
iisort.awk         for (j = i; j > 1 && ++comp &&
iisort.awk           A[j-1] > A[j] && ++exch; j--) {
iisort.awk             # swap A[j-1] and A[j]
iisort.awk             t = A[j-1]; A[j-1] = A[j]; A[j] = t
iisort.awk         }
iisort.awk }
frame.awk # test framework for sort performance evaluation
frame.awk #   input:  lines with sort name, type of data, sizes...
frame.awk #   output: name, type, size, comparisons, exchanges, c+e
frame.awk 
frame.awk {   for (i = 3; i <= NF; i++)
frame.awk         test($1, $2, $i)
frame.awk }
frame.awk 
frame.awk function test(sort, data, n) {
frame.awk     comp = exch = 0
frame.awk     if (data ~ /rand/)
frame.awk         genrand(A, n)
frame.awk     else if (data ~ /id/)
frame.awk         genid(A, n)
frame.awk     else if (data ~ /rev/)
frame.awk         genrev(A, n)
frame.awk     else
frame.awk         print "illegal type of data in", $0
frame.awk     if (sort ~ /q.*sort/)
frame.awk         qsort(A, 1, n)
frame.awk     else if (sort ~ /h.*sort/)
frame.awk         hsort(A, n)
frame.awk     else if (sort ~ /i.*sort/)
frame.awk         isort(A, n)
frame.awk     else print
frame.awk         "illegal type of sort in", $0
frame.awk     print sort, data, n, comp, exch, comp+exch
frame.awk }
frame.awk 
frame.awk # test-generation and sorting routines ...
frame.awk 
frame.awk BEGIN { srand(111) }
frame.awk function genrand(A,n,    i) { # put n random integers in A
frame.awk     for (i = 1; i <= n; i++)
frame.awk         A[i] = int(n*rand())
frame.awk }
frame.awk 
frame.awk function gensort(A,n,    i) { # put n sorted integers in A
frame.awk     for (i = 1; i <= n; i++)
frame.awk         A[i] = i
frame.awk }
frame.awk 
frame.awk function genrev(A,n,    i) { # put n reverse-sorted integers in A
frame.awk     for (i = 1; i <= n; i++)
frame.awk         A[i] = n+1-i
frame.awk }
frame.awk 
frame.awk function genid(A,n,    i) { # put n identical integers in A
frame.awk     for (i = 1; i <= n; i++)
frame.awk         A[i] = 1
frame.awk }
frame.awk 
frame.awk function check(A,n,   i) {
frame.awk     for (i = 1; i < n; i++)
frame.awk         if (A[i] > A[i+1])
frame.awk             printf("error: array is not sorted, element %d\n", i)
frame.awk }
frame.awk function isort(A,n,        i,j,t) {
frame.awk       for (i = 2; i <= n; i++)
frame.awk           for (j = i; j > 1 && ++comp && A[j-1] > A[j] && ++exch; j--) {
frame.awk               # swap A[j-1] and A[j]
frame.awk               t = A[j-1]; A[j-1] = A[j]; A[j] = t
frame.awk           }
frame.awk }
frame.awk 
frame.awk function qsort(A,left,right,   i,last) {
frame.awk      if (left >= right)  # do nothing if array contains
frame.awk          return          # at most one element
frame.awk      swap(A, left, left + int((right-left+1)*rand()))
frame.awk      last = left
frame.awk      for (i = left+1; i <= right; i++)
frame.awk          if (++comp && A[i] < A[left])
frame.awk              swap(A, ++last, i)
frame.awk      swap(A, left, last)
frame.awk      qsort(A, left, last-1)
frame.awk      qsort(A, last+1, right)
frame.awk }
frame.awk 
frame.awk function swap(A,i,j,   t) {
frame.awk      ++exch
frame.awk      t = A[i]; A[i] = A[j]; A[j] = t
frame.awk }
frame.awk 
frame.awk function hsort(A,right,  i) {
frame.awk      for (i = int(right/2); i >= 1; i--)
frame.awk           heapify(A, i, right)
frame.awk      for (i = right; i > 1; i--) {
frame.awk           swap(A, 1, i)
frame.awk           heapify(A, 1, i-1)
frame.awk      }
frame.awk }
frame.awk 
frame.awk function heapify(A,left,right,   p,c) {
frame.awk      for (p = left; (c = 2*p) <= right; p = c) {
frame.awk          if (c < right && ++comp && A[c+1] > A[c])
frame.awk              c++
frame.awk          if (++comp && A[p] < A[c])
frame.awk              swap(A, c, p)
frame.awk      }
frame.awk }
qsort.awk # quicksort
qsort.awk 
qsort.awk     { A[NR] = $0 }
qsort.awk 
qsort.awk END { qsort(A, 1, NR)
qsort.awk       for (i = 1; i <= NR; i++)
qsort.awk           print A[i]
qsort.awk     }
qsort.awk 
qsort.awk # qsort - sort A[left..right] by quicksort
qsort.awk 
qsort.awk function qsort(A,left,right,   i,last) {
qsort.awk      if (left >= right)  # do nothing if array contains
qsort.awk          return          # less than two elements
qsort.awk      swap(A, left, left + int((right-left+1)*rand()))
qsort.awk      last = left   # A[left] is now partition element
qsort.awk      for (i = left+1; i <= right; i++)
qsort.awk          if (A[i] < A[left])
qsort.awk              swap(A, ++last, i)
qsort.awk      swap(A, left, last)
qsort.awk      qsort(A, left, last-1)
qsort.awk      qsort(A, last+1, right)
qsort.awk }
qsort.awk 
qsort.awk function swap(A,i,j,   t) {
qsort.awk      t = A[i]; A[i] = A[j]; A[j] = t
qsort.awk }
hsort.awk # heapsort
hsort.awk 
hsort.awk     { A[NR] = $0 }
hsort.awk 
hsort.awk END { hsort(A, NR)
hsort.awk       for (i = 1; i <= NR; i++)
hsort.awk           { print A[i] }
hsort.awk     }
hsort.awk 
hsort.awk function hsort(A,n,  i) {
hsort.awk     for (i = int(n/2); i >= 1; i--)  # phase 1
hsort.awk          { heapify(A, i, n) }
hsort.awk     for (i = n; i > 1; i--) {        # phase 2
hsort.awk          { swap(A, 1, i) }
hsort.awk          { heapify(A, 1, i-1) }
hsort.awk     }
hsort.awk }
hsort.awk function heapify(A,left,right,   p,c) {
hsort.awk     for (p = left; (c = 2*p) <= right; p = c) {
hsort.awk         if (c < right && A[c+1] > A[c])
hsort.awk             { c++ }
hsort.awk         if (A[p] < A[c])
hsort.awk             { swap(A, c, p) }
hsort.awk     }
hsort.awk }
hsort.awk function swap(A,i,j,   t) {
hsort.awk     t = A[i]; A[i] = A[j]; A[j] = t
hsort.awk }
makeprof # makeprof - prepare profiling version of an awk program
makeprof #   usage:  awk -f makeprof awkprog >awkprog.p
makeprof #   running awk -f awkprog.p data creates a
makeprof #       file prof.cnts of statement counts for awkprog
makeprof 
makeprof     { if ($0 ~ /{/) sub(/{/, "{ _LBcnt[" ++_numLB "]++; ")
makeprof       print
makeprof     }
makeprof 
makeprof END { printf("END { for (i = 1; i <= %d; i++)\n", _numLB)
makeprof       printf("\t\t print _LBcnt[i] > \"prof.cnts\"\n}\n")
makeprof     }
printprof # printprof - print profiling counts
printprof #     usage:  awk -f printprof awkprog
printprof #     prints awkprog with statement counts from prof.cnts
printprof 
printprof BEGIN { while (getline < "prof.cnts" > 0) cnt[++i] = $1 }
printprof /{/   { printf("%5d", cnt[++j]) }
printprof       { printf("\t%s\n", $0) }
tsort.awk # tsort - topological sort of a graph
tsort.awk #   input:  predecessor-successor pairs
tsort.awk #   output: linear order, predecessors first
tsort.awk 
tsort.awk     { if (!($1 in pcnt))
tsort.awk           pcnt[$1] = 0           # put $1 in pcnt
tsort.awk       pcnt[$2]++                 # count predecessors of $2
tsort.awk       slist[$1, ++scnt[$1]] = $2 # add $2 to successors of $1
tsort.awk     }
tsort.awk END { for (node in pcnt) {
tsort.awk           nodecnt++
tsort.awk           if (pcnt[node] == 0)   # if it has no predecessors
tsort.awk               q[++back] = node   # queue node
tsort.awk       }
tsort.awk       for (front = 1; front <= back; front++) {
tsort.awk           printf(" %s", node = q[front])
tsort.awk           for (i = 1; i <= scnt[node]; i++)
tsort.awk               if (--pcnt[slist[node, i]] == 0)
tsort.awk                   # queue s if it has no more predecessors
tsort.awk                   q[++back] = slist[node, i]
tsort.awk       }
tsort.awk       if (back != nodecnt)
tsort.awk           print "\nerror: input contains a cycle"
tsort.awk       printf("\n")
tsort.awk     }
dfs.awk # dfs - depth-first search for cycles
dfs.awk 
dfs.awk function dfs(node,     i, s) {
dfs.awk     visited[node] = 1
dfs.awk     for (i = 1; i <= scnt[node]; i++)
dfs.awk         if (visited[s = slist[node, i]] == 0)
dfs.awk             dfs(s)
dfs.awk         else if (visited[s] == 1)
dfs.awk             print "cycle with back edge (" node ", " s ")" 
dfs.awk     visited[node] = 2
dfs.awk }
rtsort.awk # rtsort - reverse topological sort
rtsort.awk #   input:  predecessor-successor pairs
rtsort.awk #   output: linear order, successors first
rtsort.awk 
rtsort.awk     { if (!($1 in pcnt))
rtsort.awk           pcnt[$1] = 0           # put $1 in pcnt
rtsort.awk       pcnt[$2]++                 # count predecessors of $2
rtsort.awk       slist[$1, ++scnt[$1]] = $2 # add $2 to successors of $1
rtsort.awk     }
rtsort.awk 
rtsort.awk END { for (node in pcnt) {
rtsort.awk           nodecnt++
rtsort.awk           if (pcnt[node] == 0)
rtsort.awk               rtsort(node)
rtsort.awk       }
rtsort.awk       if (pncnt != nodecnt)
rtsort.awk           print "error: input contains a cycle"
rtsort.awk       printf("\n")
rtsort.awk     }
rtsort.awk 
rtsort.awk function rtsort(node,     i, s) {
rtsort.awk     visited[node] = 1
rtsort.awk     for (i = 1; i <= scnt[node]; i++)
rtsort.awk         if (visited[s = slist[node, i]] == 0)
rtsort.awk             rtsort(s)
rtsort.awk         else if (visited[s] == 1)
rtsort.awk             printf("error: nodes %s and %s are in a cycle\n",
rtsort.awk                 s, node)
rtsort.awk     visited[node] = 2
rtsort.awk     printf(" %s", node)
rtsort.awk     pncnt++    # count nodes printed
rtsort.awk }
make.awk # make - maintain dependencies
make.awk 
make.awk BEGIN {
make.awk     while (getline <"makefile" > 0)
make.awk         if ($0 ~ /^[A-Za-z]/) {  #  $1: $2 $3 ...
make.awk             sub(/:/, "")
make.awk             if (++names[nm = $1] > 1)
make.awk                 error(nm " is multiply defined")
make.awk             for (i = 2; i <= NF; i++) # remember targets
make.awk                 slist[nm, ++scnt[nm]] = $i
make.awk         } else if ($0 ~ /^\t/)        # remember cmd for
make.awk             cmd[nm] = cmd[nm] $0 "\n" #   current name
make.awk         else if (NF > 0)
make.awk             error("illegal line in makefile: " $0)
make.awk     ages()      # compute initial ages
make.awk     if (ARGV[1] in names) {
make.awk         if (update(ARGV[1]) == 0)
make.awk             print ARGV[1] " is up to date"
make.awk     } else
make.awk         error(ARGV[1] " is not in makefile")
make.awk }
make.awk 
make.awk function ages(      f,n,t) {
make.awk     for (t = 1; ("ls -t" | getline f) > 0; t++)
make.awk         age[f] = t   # all existing files get an age
make.awk     close("ls -t")
make.awk     for (n in names)
make.awk         if (!(n in age))   # if n has not been created
make.awk             age[n] = 9999  # make n really old
make.awk }
make.awk function update(n,   changed,i,s) {
make.awk     if (!(n in age)) error(n " does not exist")
make.awk     if (!(n in names)) return 0
make.awk     changed = 0
make.awk     visited[n] = 1
make.awk     for (i = 1; i <= scnt[n]; i++) {
make.awk         if (visited[s = slist[n, i]] == 0) update(s)
make.awk         else if (visited[s] == 1)
make.awk             error(s " and " n " are circularly defined")
make.awk         if (age[s] <= age[n]) changed++
make.awk     }
make.awk     visited[n] = 2
make.awk     if (changed || scnt[n] == 0) {
make.awk         printf("%s", cmd[n])
make.awk         system(cmd[n])  # execute cmd associated with n
make.awk         ages()          # recompute all ages
make.awk         age[n] = 0      # make n very new
make.awk         return 1
make.awk     }
make.awk     return 0
make.awk }
make.awk function error(s) { print "error: " s; exit }

.