For 1718:
- don't use #asSortedCollection for sorting.
- SortedCollection uses quicksort, not merge sort as stated in a comment.
That's why #asSortedCollection is slow when there are only a few different
values. Quicksort performance degrades to O(n^2) in this case, but that's
totally valid. However merge sort has guaranteed O(n*log(n)) runtime.
On Fri, 19 Nov 2010, Stephan Eggermont wrote:
I would be interested in improvements. This is just a straight translation
of the java code.
It has some errors. If you define this method in Array, replace 'array'
with 'self' and evaluate this code, it'll raise an error:
a := (1 to: 50) asArray.
[ a dualPivotQuicksort: 1 to: a size split: 3 ] bench
It's also not general. #sort: #sorted: and #asSortedCollection: use
a single block for comparison, while this method uses #<, #>, #= and #~=
in a mixed way.
Yaroslavskiy's Dual-Pivot Quicksort seems to perform better for large
collections:
A straightforward
defaultSort: i to: j
self dualPivotQuicksort: i to: j split: 3
dualPivotQuicksort: left to: right split: div
|len third m1 m2 pivot1 pivot2 less great dist newDiv|
len := right - left.
newDiv := div.
len < 27 ifTrue: [
left+1 to: right do: [ :i | | j |
j := i.
[(j>left) and: [(array at:j) < (array at: (j-1))]]
whileTrue: [
array swap: j with: j-1.
j := j-1]]]
That looks like an optimized bubble sort, ouch.
Levente
ifFalse: [
third := len // div.
m1 := left+third.
m2 := right-third.
m1 <= left ifTrue: [m1 := left+1].
m2 >= right ifTrue: [m2 := right-1].
(array at: m1) < (array at: m2) ifTrue: [
array swap: m1 with: left.
array swap: m2 with: right]
ifFalse: [
array swap: m1 with: right.
array swap: m2 with: left].
pivot1 := array at: left.
pivot2 := array at: right.
less := left+1.
great := right-1.
less to: great do: [ :k |
(array at: k) < pivot1 ifTrue: [
array swap: k with: less.
less := less+1.]
ifFalse: [
(array at: k ) > pivot2 ifTrue: [
[(k < great and: [(array at: great) >
pivot2])] whileTrue: [
great := great -1].
array swap: k with: great.
great := great-1.
(array at: k) < pivot1 ifTrue: [
array swap: k with: less.
less := less+1]
]
]].
dist := great-less.
dist < 13 ifTrue: [ newDiv := div+1].
array swap: (less-1) with: left.
array swap: (great+1) with: right.
self dualPivotQuicksort: left to: (less-2) split: newDiv.
self dualPivotQuicksort: (great+2) to: right split: newDiv.
(dist > (len -13) and: [ pivot1 ~= pivot2]) ifTrue:[
less to: great do: [ :k |
(array at: k) = pivot1 ifTrue: [
array swap: k with: less.
less := less+1]
ifFalse: [
(array at: k) = pivot2 ifTrue: [
array swap: k with: great.
great := great - 1.
(array at: k) = pivot1 ifTrue: [
array swap: k with:
less.
less := less+1]
]
]
]
].
pivot1 < pivot2 ifTrue: [
self dualPivotQuicksort: less to: great split: newDiv]
]
Do we have a performance test set for sorting?
