Quicksort (Sed)
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
Contents |
theory
Perform a Quicksort:
q(x/xs) = q(as) x q(zs)
practice
A bog-standard quicksort: partition around a pivot. This is a recursive algorithm, but the state of the recursion is encoded in the data structure, so not only don't we need a code stack, we won't have any explicit code to recurse -- we run until convergence instead.
(to animate the algorithm, uncomment the l command)
<<quicksort>>= : part partition : sort # l pivot
First we look for pivots. At this point the pattern space consists of bracketed {input} chunks, interspersed with already sorted output.
To sort a nontrivial chunk, we choose a pivot digit from the front and add a lookup table
so we can invoke the partitioning code.
<<pivot>>= except for trivial chunks s/{\(.\)\([^}]*\)}/{\2 \1 9876543210 }/ t part
Of course, every recursion has to bottom out somewhere, and for us that is at empty chunks.
<<except for trivial chunks>>= s/{}// t sort
the crux
Actually partitioning the unsorted digit string is the crux move. We use the technique of Greg Ubben's lookup table tutorial to pick out the elements of the lower partition which are greater than the pivot and move them to the upper partition.
<<partition>>= # +-1: input before element # | +-2: element to move # | | +-3: remainder of input # | | | +-4: pivot # | | | | +-5: table (codes \2 vs. \4 ordering) # | | | | | s/{\([0-9]*\)\(.\)\([0-9]*\) \(.\) \([0-9]*\2[0-9]*\4[0-9]*\) /{\1\3 \4 \5 \2/ t part cleanup
After all that heavy lifting converges, the cleanup is straightforward: rewrite the pattern space into:
so we can look for pivots in the subchunks.
<<cleanup>>= s/{\([^ ]*\) \(.\) \([^ ]*\) \([^}]*\)}/{\1}\2{\4}/ b sort
wrapping up
Finally, we arrange for a rudimentary input: find a string of digits in the input line, and turn it into a {chunk} for sorting.
<<quicksort.sed>>= #!/usr/bin/sed -f s/[^0-9]*\([0-9]*\).*/{\1}/ b sort quicksort
Let's try a simple sanity check:
> echo "31415926535897931" | sed -f quicksort.sed 11123334555678999
| Download code |