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
