Rosetta Code

Sorting algorithms/Quicksort: Difference between revisions

Page Discussion

Sorting algorithms/Quicksort (view source)

Revision as of 23:04, 25 March 2024

5,390 bytes added ,  1 month ago
→‎{{header|Bruijn}}
(add RPL)
(40 intermediate revisions by 16 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,024 ⟶ 4,081:
#
if mid < (right + left) / 2
call qsort left mid - 1 d[]
left = mid + 1
else
call qsort mid + 1 right d[]
right = mid - 1
.
.
.
funcproc sort . d[] .
call qsort 1 len d[] d[]
.
d[] = [ 29 4 72 44 55 26 27 77 92 5 ]
call sort d[]
print d[]
</syntaxhighlight>
Line 4,334 ⟶ 4,391:
 
=={{header|Elena}}==
ELENA 56.0x :
<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)
<syntaxhighlight lang="fortran">MODULE qsort_mod
use inserts, only:insertion_sort !Not included in this posting
 
implicit none
IMPLICIT NONE
!
 
! PARAMETER definitions
TYPE group
!
INTEGER :: order ! original order of unsorted data
integer, parameter :: changesize = 64
REAL :: VALUE ! values to be sorted by
!
END TYPE group
! Dummy arguments
 
!
CONTAINS
real, dimension(:) ,contiguous :: a
 
intent (inout) a
RECURSIVE SUBROUTINE QSort(a,na)
!
 
! Local variables
! DUMMY ARGUMENTS
!
INTEGER, INTENT(in) :: nA
integer :: first = 1
TYPE (group), DIMENSION(nA), INTENT(in out) :: A
integer :: i
 
! LOCAL VARIABLESinteger :: j
INTEGER integer :: left, rightlast
REAL logical :: random stay
REAL real :: pivot t
TYPE (group) real :: temp x
!
INTEGER :: marker
!*Code
 
!
IF (nA > 1) THEN
last = size(a, 1)
 
if( (last - first)<changesize )then
CALL random_NUMBER(random)
call insertion_sort(a(first:last))
pivot = A(INT(random*REAL(nA-1))+1)%VALUE ! Choice a random pivot (not best performance, but avoids worst-case)
left = 1 return
end right = nAif
j != Partitionshiftr((first loop+ last), 1) + 1
!
DO
x = IF a(left >= rightj) EXIT
i = DOfirst
j = last
IF (A(right)%VALUE <= pivot) EXIT
rightstay = right - 1.true.
do while ( stay END DO)
DOdo while ( a(i)<x )
IF (A(left)%VALUEi >= pivot)i EXIT+ 1
end left = left + 1do
ENDdo DOwhile ( x<a(j) )
IF (left < right) THENj = j - 1
end temp = A(left)do
Aif(left) =j<i A(right)then
A(right) stay = temp.false.
END IFelse
t = a(i) ! Swap the values
END DO
a(i) = a(j)
 
IF (left == right a(j) THEN= t
marker i = lefti + 1 ! Adjust the pointers (PIVOT POINTS)
ELSE j = j - 1
markerend = leftif
end END IFdo
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
CALL QSort(A(:marker-1),marker-1)
return
CALL QSort(A(marker:),nA-marker+1)
end subroutine fsort
 
</syntaxhighlight>
END IF
 
END SUBROUTINE QSort
 
END MODULE qsort_mod
! Test Qsort Module
PROGRAM qsort_test
USE qsort_mod
IMPLICIT NONE
 
INTEGER, PARAMETER :: nl = 10, nc = 5, l = nc*nl, ns=33
TYPE (group), DIMENSION(l) :: A
INTEGER, DIMENSION(ns) :: seed
INTEGER :: i
REAL :: random
CHARACTER(LEN=80) :: fmt1, fmt2
! Using the Fibonacci sequence to initialize seed:
seed(1) = 1 ; seed(2) = 1
DO i = 3,ns
seed(i) = seed(i-1)+seed(i-2)
END DO
! Formats of the outputs
WRITE(fmt1,'(A,I2,A)') '(', nc, '(I5,2X,F6.2))'
WRITE(fmt2,'(A,I2,A)') '(3x', nc, '("Ord. Num.",3x))'
PRINT *, "Unsorted Values:"
PRINT fmt2,
CALL random_SEED(put = seed)
DO i = 1, l
CALL random_NUMBER(random)
A(i)%VALUE = NINT(1000*random)/10.0
A(i)%order = i
IF (MOD(i,nc) == 0) WRITE (*,fmt1) A(i-nc+1:i)
END DO
PRINT *
CALL QSort(A,l)
PRINT *, "Sorted Values:"
PRINT fmt2,
DO i = nc, l, nc
IF (MOD(i,nc) == 0) WRITE (*,fmt1) A(i-nc+1:i)
END DO
STOP
END PROGRAM qsort_test</syntaxhighlight>
{{out}}
<pre>
Compiled with GNU Fortran 9.3.0
Unsorted Values:
Ord. Num. Ord. Num. Ord. Num. Ord. Num. Ord. Num.
1 47.10 2 11.70 3 35.80 4 35.20 5 55.30
6 74.60 7 28.40 8 30.10 9 70.60 10 66.90
11 15.90 12 71.70 13 49.80 14 2.60 15 12.80
16 93.00 17 45.20 18 21.50 19 20.70 20 39.50
21 9.20 22 21.60 23 18.60 24 22.80 25 98.50
26 97.50 27 43.90 28 8.30 29 84.10 30 88.80
31 10.30 32 30.50 33 79.30 34 24.40 35 45.00
36 48.30 37 69.80 38 86.00 39 68.40 40 22.90
41 7.50 42 18.50 43 80.40 44 29.60 45 43.60
46 11.20 47 36.20 48 23.20 49 45.30 50 12.30
 
Sorted Values:
Ord. Num. Ord. Num. Ord. Num. Ord. Num. Ord. Num.
14 2.60 41 7.50 28 8.30 21 9.20 31 10.30
46 11.20 2 11.70 50 12.30 15 12.80 11 15.90
42 18.50 23 18.60 19 20.70 18 21.50 22 21.60
24 22.80 40 22.90 48 23.20 34 24.40 7 28.40
44 29.60 8 30.10 32 30.50 4 35.20 3 35.80
47 36.20 20 39.50 45 43.60 27 43.90 35 45.00
17 45.20 49 45.30 1 47.10 36 48.30 13 49.80
5 55.30 10 66.90 39 68.40 37 69.80 9 70.60
12 71.70 6 74.60 33 79.30 43 80.40 29 84.10
38 86.00 30 88.80 16 93.00 26 97.50 25 98.50
</pre>
A discussion about Quicksort pivot options, free source code for an optimized quicksort using insertion sort as a finisher, and an OpenMP multi-threaded quicksort is found at [http://balfortran.org balfortran.org]
 
=={{header|FreeBASIC}}==
Line 5,604 ⟶ 5,589:
val ys = xx.filter fn(el) { el < x }
val zs = xx.filter fn(el) { el >= x }
qsort(ys) ++ [x] ++ qsort(zs)
}
Nil -> Nil
Line 5,615 ⟶ 5,600:
Cons(x,xx) -> {
val (ys, zs) = xx.partition fn(el) { el < x }
qsort(ys) ++ [x] ++ qsort(zs)
}
Nil -> Nil
Line 8,041 ⟶ 8,026:
 
=={{header|Python}}==
<syntaxhighlight lang="python">def quickSortquick_sort(arrsequence):
lesslesser = []
pivotListequal = []
moregreater = []
if len(arrsequence) <= 1:
return arrsequence
pivot = sequence[0]
else:
for element in pivot = arr[0]sequence:
forif ielement in< arrpivot:
if i < pivot:lesser.append(element)
elif element > less.append(i)pivot:
elif i > pivot:greater.append(element)
more.append(i)else:
else:equal.append(element)
lesser = quick_sort(lesser)
pivotList.append(i)
lessgreater = quickSortquick_sort(lessgreater)
return lesser + equal + greater
more = quickSort(more)
 
return less + pivotList + more
 
a = [4, 65, 2, -31, 0, 99, 83, 782, 1]
a = quick_sort(a)
a = quickSort(a)</syntaxhighlight>
</syntaxhighlight>
 
In a Haskell fashion --
Line 8,221 ⟶ 8,207:
 
=={{header|Raku}}==
<syntaxhighlight lang="raku" line>
(formerly Perl 6)
#| Recursive, single-thread, random pivot, single-pass, quicksort implementation
<syntaxhighlight lang="raku" line># Empty list sorts to the empty list
multi quicksort([]\a where a.elems < 2) { ()a }
multi quicksort(\a, \pivot = a.pick) {
my %prt{Order} is default([]) = a.classify: * cmp pivot;
# Otherwise, extract first item as pivot...
|samewith(%prt{Less}), |%prt{Same}, |samewith(%prt{More})
multi quicksort([$pivot, *@rest]) {
}
# Partition.
</syntaxhighlight>
my $before := @rest.grep(* before $pivot);
 
my $after := @rest.grep(* !before $pivot);
===concurrent implementation===
The partitions can be sorted in parallel.
# Sort the partitions.
 
flat quicksort($before), $pivot, quicksort($after)
}</syntaxhighlight lang="raku" line>
#| Recursive, parallel, random pivot, single-pass, quicksort implementation
Note that <code>$before</code> and <code>$after</code> are bound to lazy lists, so the partitions can (at least in theory) be sorted in parallel.
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;
}
</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>,
("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;
</syntaxhighlight>
<pre>
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 🎮 🐧</pre>
 
===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>
 
=={{header|Red}}==
Line 8,610 ⟶ 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,409 ⟶ 9,551:
def last: $(2);
def pivot: $@quicksort($first);
[@: $first(1) + 1, $last ] -> #;
$(2) -> #
 
when <?($(2) <..~$(1)>)@> do
def limit: $(2);
@quicksort($first): $@quicksort($limit);
@quicksort($limit): $pivot;
Line 9,418 ⟶ 9,561:
[ $limit + 1, $last ] !
 
when <?($@quicksort($(2)) <$pivot~..>)> do
[ $(1), $(2) - 1] -> #
 
when <?($@quicksort($(1)@) <..$pivot>)> do
[@: $(1)@ + 1,; $(2)] -> #
 
otherwise
def temp: $@quicksort($(1)@);
@quicksort($(1)@): $@quicksort($(2));
@quicksort($(2)): $temp;
[@: $(1)@ + 1,; $(2) - 1] -> #
end partial
@: $;
Line 9,899 ⟶ 10,042:
=={{header|Wren}}==
{{libheader|Wren-sort}}
<syntaxhighlight lang="ecmascriptwren">import "./sort" for Sort
 
var asarray = [
[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 asarray) {
System.print("Before: %(a)")
Sort.quick(a)
Line 10,147 ⟶ 10,290:
jp quicksort_a_impl</syntaxhighlight>
Full example with test/debug data for ZX Spectrum is at [[https://gist.github.com/ped7g/0c4e94796b474994ed88d0bdd1bf2f25 github]].
 
=={{header|Zig}}==
 
{{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 quickSort(comptime T: type, arr: []T, comptime compareFn: fn (T, T) bool) void {
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 / 2;
const last_index = arr.len - 1;
 
std.mem.swap(T, &arr[pivot_index], &arr[last_index]);
 
var store_index: usize = 0;
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;
}
}
 
std.mem.swap(T, &arr[store_index], &arr[last_index]);
return store_index;
}</syntaxhighlight>
 
<syntaxhighlight lang="zig">const std = @import("std");
 
pub fn main() void {
const print = std.debug.print;
 
var arr = [_]i16{ 4, 65, 2, -31, 0, 99, 2, 83, 782, 1 };
print("Before: {any}\n\n", .{arr});
 
print("Sort numbers in ascending order.\n", .{});
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>
 
=={{header|zkl}}==
Marvin
55

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/346097...362943"