user
|  |
| --- |
| This page uses content from **Wikipedia**. The original article was at Quicksort. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |

Task

Sort an array (or list) elements using the   quicksort   algorithm.

The elements must have a   strict weak 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.

Quicksort, also known as   *partition-exchange sort*,   uses these steps.

:   :   1. Choose any element of the array to be the pivot.
        2. Divide all other elements (except the pivot) into two partitions.
           * All elements less than the pivot must be in the first partition.
           * All elements greater than the pivot must be in the second partition.
        3. Use recursion to sort both partitions.
        4. Join the first sorted partition, the pivot, and the second sorted partition.

The best pivot creates partitions of equal length (or lengths differing by   **1**).

The worst pivot creates an empty partition (for example, if the pivot is the first or last element of a sorted array).

The run-time of Quicksort ranges from    *O(n* log *n)*    with the best pivots, to    *O(n2)*    with the worst pivots, where    *n*    is the number of elements in the array.

This is a simple quicksort algorithm, adapted from Wikipedia.

```
function quicksort(array)
    less, equal, greater := three empty arrays
    if length(array) > 1  
        pivot := select any element of array
        for each x in array
            if x < pivot then add x to less
            if x = pivot then add x to equal
            if x > pivot then add x to greater
        quicksort(less)
        quicksort(greater)
        array := concatenate(less, equal, greater)

```

A better quicksort algorithm works in place, by swapping elements within the array, to avoid the memory allocation of more arrays.

```
function quicksort(array)
    if length(array) > 1
        pivot := select any element of array
        left := first index of array
        right := last index of array
        while left ≤ right
            while array[left] < pivot
                left := left + 1
            while array[right] > pivot
                right := right - 1
            if left ≤ right
                swap array[left] with array[right]
                left := left + 1
                right := right - 1
        quicksort(array from first index to right)
        quicksort(array from left to last index)

```

Quicksort has a reputation as the fastest sort. Optimized variants of quicksort are common features of many languages and libraries. One often contrasts quicksort with   merge sort,   because both sorts have an average time of    *O(n* log *n)*.

:   *"On average, mergesort does fewer comparisons than quicksort, so it may be better when complicated comparison routines are used. Mergesort also takes advantage of pre-existing order, so it would be favored for using sort() to merge several sorted arrays. On the other hand, quicksort is often faster for small arrays, and on arrays of a few distinct values, repeated many times."* — http://perldoc.perl.org/sort.html

Quicksort is at one end of the spectrum of divide-and-conquer algorithms, with merge sort at the opposite end.

* Quicksort is a conquer-then-divide algorithm, which does most of the work during the partitioning and the recursive calls. The subsequent reassembly of the sorted partitions involves trivial effort.
* Merge sort is a divide-then-conquer algorithm. The partioning happens in a trivial way, by splitting the input array in half. Most of the work happens during the recursive calls and the merge phase.

With quicksort, every element in the first partition is less than or equal to every element in the second partition. Therefore, the merge phase of quicksort is so trivial that it needs no mention!

This task has not specified whether to allocate new arrays, or sort in place. This task also has not specified how to choose the pivot element. (Common ways to are to choose the first element, the middle element, or the median of three elements.) Thus there is a variety among the following implementations.
assistant
```
#| Recursive, single-thread, random pivot, single-pass, quicksort implementation
multi quicksort(\a where a.elems < 2) { a }
multi quicksort(\a, \pivot = a.pick) {
	my %prt{Order} is default([]) = a.classify: * cmp pivot;
	|samewith(%prt{Less}), |%prt{Same}, |samewith(%prt{More})
}
```

### concurrent implementation

The partitions can be sorted in parallel.

```
#| Recursive, parallel, random pivot, single-pass, quicksort implementation
multi quicksort-parallel-naive(\a where a.elems < 2) { a }
multi quicksort-parallel-naive(\a, \pivot = a.pick) {
	my %prt{Order} is default([]) = a.classify: * cmp pivot;
	my Promise $less = start { samewith(%prt{Less}) }
	my $more = samewith(%prt{More});
	await $less andthen |$less.result, |%prt{Same}, |$more;
}
```

Let's tune the parallel execution by applying a minimum batch size in order to spawn a new thread.

```
#| Recursive, parallel, batch tuned, single-pass, quicksort implementation
sub quicksort-parallel(@a, $batch = 2**9) {
	return @a if @a.elems < 2;

	# separate unsorted input into Order Less, Same and More compared to a random $pivot
	my $pivot = @a.pick;
	my %prt{Order} is default([]) = @a.classify( * cmp $pivot );

	# decide if we sort the Less partition on a new thread
	my $less = %prt{Less}.elems >= $batch
			        ?? start { samewith(%prt{Less}, $batch) }
			        !!         samewith(%prt{Less}, $batch);

	# meanwhile use current thread for sorting the More partition
	my $more = samewith(%prt{More}, $batch);

	# if we went parallel, we need to await the result
	await $less andthen $less = $less.result if $less ~~ Promise;

	# concat all sorted partitions into a list and return
	|$less, |%prt{Same}, |$more;
}
```

### testing

Let's run some tests.

```
say "x" x 10 ~ " Testing " ~ "x" x 10;
use Test;
my @functions-under-test = &quicksort, &quicksort-parallel-naive, &quicksort-parallel;
my @testcases =
		() => (),
		<a>.List => <a>.List,
		<a a> => <a a>,
		("b", "a", 3) => (3, "a", "b"),
		<h b a c d f e g> => <a b c d e f g h>,
		<a 🎮 3 z 4 🐧> => <a 🎮 3 z 4 🐧>.sort
		;

plan @testcases.elems * @functions-under-test.elems;
for @functions-under-test -> &fun {
	say &fun.name;
	is-deeply &fun(.key), .value, .key ~ "  =>  " ~ .value for @testcases;
}
done-testing;
```

```
xxxxxxxxxx Testing xxxxxxxxxx
1..18
quicksort
ok 1 -   =>
ok 2 - a  =>  a
ok 3 - a a  =>  a a
ok 4 - b a 3  =>  3 a b
ok 5 - h b a c d f e g  =>  a b c d e f g h
ok 6 - a 🎮 3 z 4 🐧  =>  3 4 a z 🎮 🐧
quicksort-parallel-naive
ok 7 -   =>
ok 8 - a  =>  a
ok 9 - a a  =>  a a
ok 10 - b a 3  =>  3 a b
ok 11 - h b a c d f e g  =>  a b c d e f g h
ok 12 - a 🎮 3 z 4 🐧  =>  3 4 a z 🎮 🐧
quicksort-parallel
ok 13 -   =>
ok 14 - a  =>  a
ok 15 - a a  =>  a a
ok 16 - b a 3  =>  3 a b
ok 17 - h b a c d f e g  =>  a b c d e f g h
ok 18 - a 🎮 3 z 4 🐧  =>  3 4 a z 🎮 🐧
```

### benchmarking

and some benchmarking

```
say "x" x 11 ~ " Benchmarking " ~ "x" x 11;
use Benchmark;
my $runs = 5;
my $elems = 10 * Kernel.cpu-cores * 2**10;
my @unsorted of Str = ('a'..'z').roll(8).join xx $elems;
my UInt $l-batch = 2**13;
my UInt $m-batch = 2**11;
my UInt $s-batch = 2**9;
my UInt $t-batch = 2**7;

say "elements: $elems, runs: $runs, cpu-cores: {Kernel.cpu-cores}, large/medium/small/tiny-batch: $l-batch/$m-batch/$s-batch/$t-batch";

my %results = timethese $runs, {
	single-thread         => { quicksort(@unsorted) },
	parallel-naive        => { quicksort-parallel-naive(@unsorted) },
	parallel-tiny-batch   => { quicksort-parallel(@unsorted, $t-batch) },
	parallel-small-batch  => { quicksort-parallel(@unsorted, $s-batch) },
	parallel-medium-batch => { quicksort-parallel(@unsorted, $m-batch) },
	parallel-large-batch  => { quicksort-parallel(@unsorted, $l-batch) },
}, :statistics;

my @metrics = <mean median sd>;
my $msg-row = "%.4f\t" x @metrics.elems ~ '%s';

say @metrics.join("\t");
for %results.kv -> $name, %m {
	say sprintf($msg-row, %m{@metrics}, $name);
}
```

```
xxxxxxxxxxx Benchmarking xxxxxxxxxxx
elements: 40960, runs: 5, cpu-cores: 4, large/medium/small/tiny-batch: 8192/2048/512/128
mean	median	sd
2.9503	2.8907	0.2071	parallel-small-batch
3.2054	3.1727	0.2078	parallel-tiny-batch
5.6524	5.0980	1.2628	parallel-naive
3.4717	3.3353	0.3622	parallel-medium-batch
4.6275	4.7793	0.4930	parallel-large-batch
6.5401	6.2832	0.5585	single-thread

```