Hi - I know I didn't respond to your query because I'm personally not interested in doing low-level things, like implementing quicksort, in J. It's a well-understood algorithm that's been implemented many thousands of times and does not speak to the strengths of J. You're right to think it's more appropriate in a low-level language like C++.
I understand you're looking at this for pedagogical purposes but it's not clear what implementing algorithms like these in J will get you in terms of better understanding the algorithm or understanding the language. Regards, Devon On Thu, Apr 9, 2009 at 11:53 AM, Yuvaraj Athur Raghuvir < [email protected]> wrote: > 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 > -- Devon McCormick, CFA ^me^ at acm. org is my preferred e-mail ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
