Quicksort (AWK)

From LiteratePrograms

Other implementations: AWK | C | C++ | Eiffel | Erlang | Forth | Haskell | Java | JavaScript | Mathematica | Mercury | Oz | Python | Python, arrays | Scala | Sed | Standard ML | Visual Basic .NET | XProc

If one really wants sorted output using awk, probably the best method is something on the order of:

awk '{print|"sort"}'

but here we implement a traditional quicksort, with the slight difference that the subsorts run in new processes instead of just new stack frames.

<<quicksort.awk>>=
#!/bin/awk -f
find pivot
partition elements
sort sublists

Finding a pivot is simple; we take the first element,

<<find pivot>>=
NR == 1         { pivot=$0; next }

and then with each of the remaining elements, if it is less than the pivot we send it immediately to the lower sorting process, otherwise we save it to send to the higher sorting process.

<<partition elements>>=
NR > 1          { if($0 <= pivot)       print | recurse
                  else                  high = (high ? high "\n" $0 : $0) }
END             { close(recurse)
                  if(NR > 0)            print pivot
                  if(high)              print high | recurse }

Finally, for each of the sub-sorts, we merely invoke another instance of the same program.

<<sort sublists>>=
BEGIN           { recurse = "awk -f quicksort.awk" }

Unfortunately, this means we must run in the same directory as the quicksort.awk file, invoking the program from the command line in the same way as the recursion:

> awk -f quicksort.awk

Exercise: rewrite the recurse string so it gives the sub-awk the entire program as an immediate argument, as in " awk 'prog' ", instead of " awk -f filename "... cf. Category:Quine

Download code