From af137@torfree.net Fri May 30 10:58:10 1997 Received: by noc.ntua.gr with ESMTP id KAA14216 ; Fri, 30 May 1997 10:58:10 +0300 (EET DST) Received: by achilles.noc.ntua.gr via NTUAnet with SMTP id KAA21519 ; Fri, 30 May 1997 10:59:59 +0300 (EET DST) Received: from localhost by queen.torfree.net (/\==/\ Smail3.1.28.1 #28.6; 16-jun-94) via sendmail with stdio idfor Y.Adamopoulos@noc.ntua.gr; Fri, 30 May 97 03:50 EDT Date: Fri, 30 May 1997 03:50:32 -0400 (EDT) From: Al Aab Subject: carlos selection sort (fwd) Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: OR =-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- al aab, seders moderator sed u soon it is not zat we do not see the s o l u t i o n -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-+ ---------- Forwarded message ---------- Date: Fri, 30 May 1997 01:59:25 +0100 From: Carlos J. G. Duarte To: af137@torfree.net Subject: selection sort this is my implementation of selection sort. usage: sed -f selsort.sed your_SMALL_file :) #! /usr/bin/sed -f # selsort.sed, implementing selection sort with sed # # $Id: selsort.sed,v 1.1 1997/05/28 23:37:11 cdua Exp cdua $ # Carlos Duarte, 970529 # How does this work? # # o first all lines are joined in this format # # \na line_a \nA # \nb line_b \nB # \nl next_line \nL # \nl next_line \nL # ... # # o general markers are of the form \n (and a \n can not appear alone) # # o the following algorithm is used: # # start at 2 # 1. a = a+1 # 2. a at end? yes: exit, no: continue # 3. make b = a+1 # 4. sort a vs b # 5. b at end? yes: goto 1; no: continue # 6. b = b+1; goto 4 # # o the sorting by itself is done this way: # # . after isolating the line a and b, add a table, with order we want # . then match the initial common part of both lines, for instance # line_a: xxxx1 # line_b: xxx22 # it would store xxx x1 22, i.e. common rest_of_a rest_of_b # . if the RE \(first_char_of_a\) \(first_char_of_b\) \1.*\2 exist # then the line is sorted already, do nothing # . else swap them # # (for instance, "a" is \1 "g" is \2, then \1.*\2 exist, because table # is abcdefg..., but if \1 was "k", then \1.*\2 do not exit on table) # # # setup H $!d g s/.// s/\n/&L&l/g s/^/\ a/ s/\nL/\ A/ s/$/\ L/ # have now: \na ln1 \nA \nl ln2 \nL \nl ln3 \nL ... b start # advance \na .. \nA to next line : inca s/\(\na\)\(.*\)\(\nA\)\(\n[lb]\)\([^ ]*\)\(\n[LB]\)/\4\2\6\1\5\3/ # ln_a is at the end, then sort is over : start /\nA$/ b exit # b = a+1 s/\nb/\ l/ s/\nB/\ L/ s/\(\na.*\nA\)\nl\([^ ]*\)\nL/\1\ b\2\ B/ : sort h s/.*\na\(.*\)\nA.*\nb\(.*\)\nB.*/\1\ \2\ !"#$%\&()*+,-.\/0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~/ # work on a temp space: common \n rest_a \n rest_b \n table s/^\(.*\)\(.*\n\)\1\(.*\n.*\)/\1\ \2\3/ # a is empty and b not: keep this order /.*\n\n..*\n/b keep # a is not empty and b is: swap order /.*\n..*\n\n/b swap # if RE fail, swap, else keep order.. /.*\n\(.\).*\n\(.\).*\n.*\1.*\2/b keep : swap s/\(\n.*\)\(\n.*\)\n/\2\1\ / : keep s/\(.*\)\n\(.*\)\n\(.*\)\n.*/\1\2\ c\1\3\ d/ # merge with main buffer G s/^\(.*\)\nc\(.*\na\)\(.*\)\(\nA\)/\2\1\4/ s/^\(.*\)\nd\n\(.*\nb\)\(.*\)\(\nB\)/\2\1\4/ # b at end? /\nB$/ b inca # nope, then make b = b+1 s/\(\nb\)\(.*\)\(\nB\)\(\nl\)\([^ ]*\)\(\nL\)/\4\2\6\1\5\3/ b sort # here: ^ \nl..\nL...\na..\nA $ : exit s/\n[ablA]//g s/\n[BL]/\ /g