Sorting algorithms/Quicksort: Difference between revisions
Content added Content deleted
(Add Seed7 example) |
No edit summary |
||
Line 2: | Line 2: | ||
{{Sorting Algorithm}} |
{{Sorting Algorithm}} |
||
In this task, the goal is to sort an array of elements using the [http://en.wikipedia.org/wiki/Quicksort Quicksort] algorithm. The elements must have a total order and the index of the array can be of any discrete type. For languages where this is not possible, sort an array of integers. |
In this task, the goal is to sort an array (or list) of elements using the [http://en.wikipedia.org/wiki/Quicksort Quicksort] algorithm. The elements must have a total order and the index of the array can be of any discrete type. For languages where this is not possible, sort an array of integers. |
||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
Line 149: | Line 149: | ||
dup 2 < if 2drop exit then |
dup 2 < if 2drop exit then |
||
1- cells over + qsort ; |
1- cells over + qsort ; |
||
=={{header|Haskell}}== |
|||
The famous two-liner, reflecting the underlying algorithm directly: |
|||
qsort [] = [] |
|||
qsort (x:xs) = qsort [y | y <- xs, y <= x] ++ [x] ++ qsort [y | y <- xs, y > x] |
|||
A more efficient version, doing only one comparison per element: |
|||
import Data.List |
|||
qsort [] = [] |
|||
qsort (x:xs) = qsort ys ++ x : qsort zs where (ys, zs) = partition (<= x) xs |
|||
==[[IDL]]== |
==[[IDL]]== |