Sorting algorithms/Quicksort: Difference between revisions
→{{header|Bruijn}}
imported>Rcmlz |
|||
(24 intermediate revisions by 11 users not shown) | |||
Line 2,625:
-31 0 1 2 2 4 65 83 99 782
</pre>
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
{{trans|Yabasic}}
<syntaxhighlight lang="qbasic">100 dim array(15)
110 a = 0
120 b = ubound(array)
130 randomize timer
140 for i = a to b
150 array(i) = rnd(1)*1000
160 next i
170 print "unsort ";
180 for i = a to b
190 print using "####";array(i);
200 if i = b then print ""; else print ", ";
210 next i
220 quicksort(array(),a,b)
230 print : print " sort ";
240 for i = a to b
250 print using "####";array(i);
260 if i = b then print ""; else print ", ";
270 next i
280 print
290 end
300 sub quicksort(array(),l,r)
310 size = r-l+1
320 if size < 2 then return
330 i = l
340 j = r
350 pivot = array(l+int(size/2))
360 rem repeat
370 while array(i) < pivot
380 i = i+1
390 wend
400 while pivot < array(j)
410 j = j-1
420 wend
430 if i <= j then temp = array(i) : array(i) = array(j) : array(j) = temp : i = i+1 : j = j-1
440 if i <= j then goto 360
450 if l < j then quicksort(array(),l,j)
460 if i < r then quicksort(array(),i,r)
470 end sub</syntaxhighlight>
==={{header|IS-BASIC}}===
Line 2,845 ⟶ 2,887:
(quick,sober)
(quick,sort)</pre>
=={{header|Bruijn}}==
<syntaxhighlight lang="bruijn">
:import std/Combinator .
:import std/Number .
:import std/List .
sort y [[0 [[[case-sort]]] case-end]]
case-sort (4 lesser) ++ (2 : (4 greater))
lesser (\lt? 2) <#> 1
greater (\ge? 2) <#> 1
case-end empty
:test (sort ((+3) : ((+2) : {}(+1)))) ((+1) : ((+2) : {}(+3)))
</syntaxhighlight>
=={{header|C}}==
Line 4,334 ⟶ 4,391:
=={{header|Elena}}==
ELENA
<syntaxhighlight lang="elena">import extensions;
import system'routines;
Line 4,351 ⟶ 4,408:
auto more := new ArrayList();
self.forEach::(item)
{
if (item < pivot)
Line 4,634 ⟶ 4,691:
=={{header|Fortran}}==
{{Works with|Fortran|90 and later}}
<syntaxhighlight lang="fortran">
recursive subroutine fsort(a)
use inserts, only:insertion_sort !Not included in this posting
implicit none
!
! PARAMETER definitions
!
integer, parameter :: changesize = 64
!
! Dummy arguments
!
real, dimension(:) ,contiguous :: a
intent (inout) a
!
! Local variables
!
integer :: first = 1
integer :: i
integer :: j
integer :: last
!
!*Code
!
if( (last - first)<changesize )then
call insertion_sort(a(first:last))
end if
!
x
i = first
do
do while (
end
if( first<i - 1 )call fsort(a(first:i - 1)) ! We still have some left to do on the lower
if( j + 1<last )call fsort(a(j + 1:last)) ! We still have some left to do on the upper
end
</syntaxhighlight>
=={{header|FreeBASIC}}==
Line 8,047 ⟶ 8,026:
=={{header|Python}}==
<syntaxhighlight lang="python">def
if len(
return
pivot = sequence[0]
for element in
elif element >
lesser = quick_sort(lesser)
return lesser + equal + greater
a = [4, 65, 2, -31, 0, 99, 83, 782, 1]
a = quick_sort(a)
</syntaxhighlight>
In a Haskell fashion --
Line 8,228 ⟶ 8,208:
=={{header|Raku}}==
<syntaxhighlight lang="raku" line>
#| Recursive, single-thread, random pivot, single-pass, quicksort implementation
multi quicksort(
multi quicksort(
my %prt{Order} is default([]) = a.classify: * cmp pivot;
|samewith(%prt{Less}), |%prt{Same}, |samewith(%prt{More})
}
</syntaxhighlight>
===concurrent implementation===
The partitions can be sorted in parallel.
<syntaxhighlight lang="raku" line>
#| Recursive, parallel, random pivot, single-pass, quicksort implementation
multi quicksort-parallel-naive(
multi quicksort-parallel-naive(
my %
my Promise $less = start { samewith(%prt{Less}) }
my $more = samewith(%prt{More});
}
</syntaxhighlight>
Let's tune the parallel execution by applying a minimum batch size in order to spawn a new thread.
<syntaxhighlight lang="raku" line>
#| 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;
}
</syntaxhighlight>
===testing===
Let's run some tests.
<syntaxhighlight lang="raku" line>
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>,
<h b a c d f e g> => <a b c d e f g h>,
;
plan @testcases.elems * @functions-under-test.elems;
for @functions-under-test -> &fun {
say &fun.name;
}
done-testing;
</syntaxhighlight>
<pre>
xxxxxxxxxx Testing xxxxxxxxxx
1..18
quicksort
ok 1 - =>
ok 2 - a => a
ok 3 - a a => a a
ok 4 - b a
ok 5 - h b a c d f e g => a b c d e f g h
ok 6 -
quicksort-parallel-naive
ok
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
ok
ok
ok
ok
ok
===benchmarking===
and some benchmarking
<syntaxhighlight lang="raku" line>
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);
}
</syntaxhighlight>
<pre>
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
</pre>
Line 8,671 ⟶ 8,725:
return</syntaxhighlight>
=={{header|Refal}}==
<syntaxhighlight lang="refal">$ENTRY Go {
, 7 6 5 9 8 4 3 1 2 0: e.Arr
= <Prout e.Arr>
<Prout <Sort e.Arr>>;
};
Sort {
= ;
s.N = s.N;
s.Pivot e.X =
<Sort <Filter s.Pivot '-' e.X>>
<Filter s.Pivot '=' e.X>
s.Pivot
<Sort <Filter s.Pivot '+' e.X>>;
};
Filter {
s.N s.Comp = ;
s.N s.Comp s.I e.List, <Compare s.I s.N>: {
s.Comp = s.I <Filter s.N s.Comp e.List>;
s.X = <Filter s.N s.Comp e.List>;
};
};</syntaxhighlight>
{{out}}
<pre>7 6 5 9 8 4 3 1 2 0
0 1 2 3 4 5 6 7 8 9</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
Line 9,470 ⟶ 9,551:
def last: $(2);
def pivot: $@quicksort($first);
$(2) -> #
when
def limit: $
@quicksort($first): $@quicksort($limit);
@quicksort($limit): $pivot;
Line 9,479 ⟶ 9,561:
[ $limit + 1, $last ] !
when <?($@quicksort($
when <?($@quicksort($
otherwise
def temp: $@quicksort($
@quicksort($
@quicksort($
end partial
@: $;
Line 9,960 ⟶ 10,042:
=={{header|Wren}}==
{{libheader|Wren-sort}}
<syntaxhighlight lang="
var
[4, 65, 2, -31, 0, 99, 2, 83, 782, 1],
[7, 5, 2, 6, 1, 4, 2, 6, 3],
["echo", "lima", "charlie", "whiskey", "golf", "papa", "alfa", "india", "foxtrot", "kilo"]
]
for (a in
System.print("Before: %(a)")
Sort.quick(a)
Line 10,209 ⟶ 10,291:
Full example with test/debug data for ZX Spectrum is at [[https://gist.github.com/ped7g/0c4e94796b474994ed88d0bdd1bf2f25 github]].
=={{header|
{{trans|Rust}}
'''Works with:''' 0.10.x, 0.11.x, 0.12.0-dev.1390+94cee4fb2
<syntaxhighlight lang="zig">const std = @import("std");
pub fn
if (arr.len < 2) return;
const pivot_index = partition(T, arr, compareFn);
quickSort(T, arr[0..pivot_index], compareFn);
quickSort(T, arr[pivot_index + 1 .. arr.len], compareFn);
}
fn partition(comptime T: type, arr: []T, comptime compareFn: fn (T, T) bool) usize {
const pivot_index = arr.len
const last_index = arr.len - 1;
std.mem.swap(T,
var store_index: usize
for (arr[0 .. arr.len - 1]) |*elem_ptr| {
if (compareFn(elem_ptr.*, arr[last_index])) {
std.mem.swap(T, elem_ptr, &arr[store_index]);
store_index += 1;
}
}
return store_index;
}</syntaxhighlight>
<syntaxhighlight lang="zig">const std = @import("std");
pub fn main() void {
const print
var arr = [_]i16{ 4, 65, 2, -31, 0, 99, 2, 83, 782, 1 };
print("Sort numbers in ascending
quickSort(i16, &arr, struct {
fn sortFn(left: i16, right: i16) bool {
return left < right;
}
}.sortFn);
print("After: {any}\n\n", .{arr});
print("Sort numbers in descending order.\n", .{});
quickSort(i16, &arr, struct {
fn sortFn(left: i16, right: i16) bool {
return left > right;
}
}.sortFn);
print("After: {any}\n\n", .{arr});
}</syntaxhighlight>
{{out}}
<pre>
Before: { 4, 65, 2, -31, 0, 99, 2, 83, 782, 1 }
Sort numbers in ascending order.
After: { -31, 0, 1, 2, 2, 4, 65, 83, 99, 782 }
Sort numbers in descending order.
After: { 782, 99, 83, 65, 4, 2, 2, 1, 0, -31 }
</pre>
|