Essays/Quicksort
< Essays
Jump to navigation
Jump to search
In Quicksort, a "pivot" item is chosen at random from the array to be sorted. The overall sorted result is the catenation of:
- the sorted result of the part less than the pivot
- the part equal to the pivot
- the sorted result of the part greater than the pivot
An implementation can be found in the if. page of the dictionary:
sel=: 1 : 'u # ['
quicksort=: 3 : 0
if. 1 >: #y do. y
else.
(quicksort y <sel e),(y =sel e),quicksort y >sel e=.y{~?#y
end.
)
A one-line tacit definition is also possible:
quicksort=: (($:@(<#[) , (=#[) , $:@(>#[)) ({~ ?@#)) ^: (1<#)
There is an amusing variant that replaces the first comma by ; and the second by ,&<
qsort=: (($:@(<#[) ; (=#[) ,&< $:@(>#[)) ({~ ?@#)) ^: (1<#)
The result of qsort is a triple of triples, where the left tine is the part less than the pivot, the middle tine the part equal to the pivot, and the right tine the part greater than the pivot. For example:
] v=: 13 ?@$ 10 5 4 0 9 0 0 7 9 8 1 1 7 2 qsort v ┌──────────────────────────────────┬─┬───────┐ │┌─────────┬───┬──────────────────┐│8│┌┬───┬┐│ ││┌┬─────┬┐│1 1│┌──────┬─┬───────┐││ │││9 9│││ ││││0 0 0│││ ││┌─┬─┬┐│5│┌┬───┬┐│││ │└┴───┴┘│ ││└┴─────┴┘│ │││2│4│││ │││7 7│││││ │ │ ││ │ ││└─┴─┴┘│ │└┴───┴┘│││ │ │ ││ │ │└──────┴─┴───────┘││ │ │ │└─────────┴───┴──────────────────┘│ │ │ └──────────────────────────────────┴─┴───────┘ ; < S: 0 qsort v 0 0 0 1 1 2 4 5 7 7 8 9 9 quicksort v 0 0 0 1 1 2 4 5 7 7 8 9 9
<!> Note: This essay is meant to explore the workings of a classical algorithm. To actually sort data in J, it is more convenient and more efficient to use /:~ .
See also
Contributed by Roger Hui.