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
