I encourage you to persist in this effort. J is suitable for testing sorting ideas, for the same reasons that it is suited for testing other programming ideas: interactive environment, conciseness, expressiveness, etc. One of the first uses of APL (the predecessor of J) was in sorting; see Chapter 6 of Ken Iverson's "A Programming Language". http://www.jsoftware.com/jwiki/Doc/A_Programming_Language
There are a few existing essays on sorting: http://www.jsoftware.com/jwiki/Essays/Quicksort http://www.jsoftware.com/jwiki/Essays/Sorting_versus_Grading http://www.jsoftware.com/jwiki/Essays/Order_Statistics You do have to be careful when you are comparing times. Two algorithms may be the same order but the fact may be obscured by the large constants involved. ----- Original Message ----- From: Yuvaraj Athur Raghuvir <[email protected]> Date: Thursday, April 9, 2009 8:54 Subject: Re: [Jprogramming] Efficient Quick Sort? To: Programming forum <[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
