There are some interesting discussions on using J for sort in: http://www.jsoftware.com/jwiki/Stories/HenryRich
There is also an interesting Bubble chart in: http://www.jsoftware.com/jwiki/Plot/Full-Text 2009/4/9, Yuvaraj Athur Raghuvir <[email protected]>: > > Hello, > > Maybe I should add some more context on why I am doing this - I am > (re-)reading up on algorithms and thought I shall use J to experiment. Am I > doing the right thing by choosing J to implement and test these rather low > level algorithms? Maybe for full control on memory and accesses, I should > choose C++ instead. > Comments? > > Regards, > Yuva > > p.s: Not sure if this is programming or chat. For now I am continuing this > thread. > > On Tue, Apr 7, 2009 at 12:25 PM, Yuvaraj Athur Raghuvir < > [email protected]> wrote: > > > Hello, > > > > Inspired by the quicksort defined at > > http://jsoftware.com/help/dictionary/d212.htm as: > > quicksortr=: (($:@(<#[) , (=#[) , $:@(>#[)) ({~ ?...@#)) ^: (1<#) NB. random > > pivot > > > > I wrote a selection sort as so: > > selectsort =: ((<./),$:@(]-. <./))^: (1<#) > > > > Yes, I know that grade(/:) is the J way of doing sorting. I am just > trying > > this out. > > > > To eliminate the random pivot selection, I did the following: > > quicksort=: (($:@(<#[) , (=#[) , $:@(>#[)) (0{])) ^: (1<#) > > > > > > To test, I created these simple verbs: > > cmd =: 'ts ''n1=.selectsort a''';'ts ''n0=.(/:a){a''';'a =. (10 ? 10) { > 22+ > > i. 10' > > cmd =: ('ts ''n3=.quicksort a''';'ts ''n2=.quicksortr a'''),cmd > > cmd =: ('n3-:n2';'n2-:n1';'n1-:n0'),cmd > > > > test=: 4 : ',. > ". L:0 (x # ,. <y)' NB. Am I doing too much work here? > > > > b =.100000 test cmd > > (+/ % #) ;"1 (3 4 5 6 {"1 b) > > 3.01884e_5 3590.4 3.35261e_5 3589.82 2.14828e_5 4744.79 6.48059e_6 > 1384.96 > > > > The data shows that quicksort is faster than quicksortr but is slower > than > > the selectsort on the average. > > > > This is expected since the quicksort does a full scan to choose the items > > lesser/greater than the pivot element. > > > > Is it possible to implement a quicksort faster than the selection sort > that > > is proposed here? > > > > Regards, > > Yuva > > > > p.s: Interestingly, I see that irrespective of the number of trials, I > > loose the first three match results. So, I have > > +/;3&{."1 b > > 299997 > > +/;3&{."1 (100 test cmd) > > 297 > > +/;3&{."1 (10 test cmd) > > 27 > > > > What could be wrong? > > > > > > > > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > -- Björn Helgason, Verkfræðingur Fugl&Fiskur ehf, Þerneyjarsundi 23, Hraunborgum Po Box 127,801 Selfoss , t-póst: [email protected] gsm: +3546985532 Landslags og skrúðgarðagerð, gröfuþjónusta http://groups.google.com/group/J-Programming Tæknikunnátta höndlar hið flókna, sköpunargáfa er meistari einfaldleikans góður kennari getur stigið á tær án þess að glansinn fari af skónum /|_ .-----------------------------------. ,' .\ / | Með léttri lund verður | ,--' _,' | Dagurinn í dag | / / | Enn betri en gærdagurinn | ( -. | `-----------------------------------' | ) | (\_ _/) (`-. '--.) (='.'=) ♖♘♗♕♔♙ `. )----' (")_(") ☃☠ ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
