> - it's still outrageously slow; quicksorting the list of 8 (base-one)
> integers at the end of the example takes around 350000 function calls,
> eight seconds on my laptop. This is due in part to linearly searching
> the rule database for every rewrite.
Mine seems to have similar timing:
8.95user 0.06system 0:09.11elapsed 98%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (399major+380minor)pagefaults 0swaps
So I tried allowing myself the luxury
of (very small) base-10 integers and
a more mature (though more primitive)
rewrite system:
> echo "31240056" | time ./qsort.sed
00123456
0.01user 0.00system 0:00.02elapsed 35%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (87major+15minor)pagefaults 0swaps
Expansion to arbitrary-length integers
is left as an exercise for the reader.
-Dave
#!/bin/sed -f
# Dave Long, 2002-11-10
################################################################################
## Q S O R T
##
## A Quicksort in sed -- the state of the "recursion"
## is encoded in the data structure (using {}-brackets
## to indicate focus), so we don't need a code stack.
##
################################################################################
# find a string of digits, and <sort> them
#-----------------------------------------
s/[^0-9]*\([0-9]*\).*/{\1}/
b sort
: part
################################################################################
# move all elements greater than the pivot
# to list at the end
################################################################################
# pattern space: ... {input pivot table moved} ...
################################################################################
# (find one element to move, then <part> again
# to handle the rest)
# +-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
# everything ordered? we must be done.
# (remove the lookup table, place the focus
# on the initial partitition, and <sort>)
#------------------------------------------
s/{\([^ ]*\) \(.\) \([^ ]*\) \([^}]*\)}/{\1} \2 \4/
: sort
# (for algorithm animation, uncomment the 'l' below)
# l
################################################################################
# check the focused chunk. if it's small
# enough to be trivially sorted, shift to
# the next chunk. otherwise, <part> the
# chunk around its head element.
################################################################################
# pattern space: output {focus} rest of input
################################################################################
# empty list is trivially sorted
#-------------------------------
s/[ ]*{} \([^ ]*\)/ {\1}/
t sort
# one element list is trivially sorted
#-------------------------------------
s/[ ]*{\(.\)} \([^ ]*\)/\1 {\2}/
t sort
# but anything larger we must partition
# (choose pivot off the front, and add
# a lookup table for <part>)
#--------------------------------------
s/{\(.\)\([^ ]*\)}/{\2 \1 9876543210 }/
t part
# no match? we must be done.
# (clean up focus brackets)
#----------------------------
s/{}//
