Rosetta Code

Sorting algorithms/Quicksort: Difference between revisions

Page Discussion

Sorting algorithms/Quicksort (view source)

Revision as of 23:04, 25 March 2024

2,199 bytes added ,  1 month ago
→‎{{header|Bruijn}}
imported>Rcmlz
(25 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 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)
'''WARNING: The implementation of QuickSort in Fortran below is flawed:'''
use inserts, only:insertion_sort !Not included in this posting
# If the largest element is in the last slot, the call to QSort(A(marker:),nA-marker+1) goes beyond the end of the array. This can cause exceptions and bad results.
implicit none
# The use of a random number causes non reproducible performance.
!
 
! PARAMETER definitions
'''Instead of this algorithm rather use https://gist.github.com/t-nissie/479f0f16966925fa29ea'''
!
 
integer, parameter :: changesize = 64
<syntaxhighlight lang="fortran">MODULE qsort_mod
!
 
! Dummy arguments
IMPLICIT NONE
!
 
real, dimension(:) ,contiguous :: a
TYPE group
intent (inout) a
INTEGER :: order ! original order of unsorted data
!
REAL :: VALUE ! values to be sorted by
! Local variables
END TYPE group
!
 
integer :: first = 1
CONTAINS
integer :: i
 
integer :: j
RECURSIVE SUBROUTINE QSort(a,na)
integer :: last
 
! DUMMY ARGUMENTSlogical :: stay
INTEGER, INTENT(in) real :: nA t
TYPE (group), DIMENSION(nA),real INTENT(in out) :: A x
!
 
!*Code
! LOCAL VARIABLES
!
INTEGER :: left, right
REAL :: randomlast = size(a, 1)
if( (last - first)<changesize )then
REAL :: pivot
call insertion_sort(a(first:last))
TYPE (group) :: temp
INTEGER :: marker return
end if
 
IF j = shiftr(nA(first >+ last), 1) THEN+ 1
!
 
x CALL= random_NUMBERa(randomj)
i = first
pivot = A(INT(random*REAL(nA-1))+1)%VALUE ! Choice a random pivot (not best performance, but avoids worst-case)
leftj = 1last
rightstay = nA.true.
do !while Partition( loopstay )
DO do while ( a(i)<x )
IF (left > i = right)i + EXIT1
DOend do
do while ( IF x<a(A(rightj)%VALUE <= pivot) EXIT
right j = rightj - 1
ENDend DOdo
DOif( j<i )then
IF (A(left)%VALUEstay >= pivot) EXIT.false.
left = left + 1else
END DO t = a(i) ! Swap the values
IF (left < right a(i) THEN= a(j)
temp = Aa(leftj) = t
A(left) i = Ai + 1 ! Adjust the pointers (rightPIVOT POINTS)
A(right) j = tempj - 1
ENDend IFif
end END DOdo
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
IF (left == right) THEN
marker = left + 1return
end ELSEsubroutine fsort
</syntaxhighlight>
marker = left
END IF
 
CALL QSort(A(:marker-1),marker-1)
CALL QSort(A(marker:),nA-marker+1) WARNING CAN GO BEYOND END OF ARRAY DO NOT USE THIS IMPLEMENTATION
 
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 8,047 ⟶ 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,227 ⟶ 8,207:
 
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" line>
#| Recursive, single-thread, random pivot, single-pass, quicksort implementation
multi quicksort(@unsorted\a where @unsorteda.elems < 2) { @unsorteda }
multi quicksort(@unsorted\a, \pivot = a.pick) {
my %prt{Order} is default([]) = a.classify: * cmp pivot;
my $pivot = @unsorted.pick;
|samewith(%prt{Less}), |%prt{Same}, |samewith(%prt{More})
my %class{Order} is default([]);
%class = @unsorted.classify: * cmp $pivot;
|quicksort(%class{Less}), |%class{Same}, |quicksort(%class{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(@unsorted\a where @unsorteda.elems < 2) { @unsorteda }
multi quicksort-parallel-naive(@unsorted\a, \pivot = a.pick) {
my %classprt{Order} is default([]) = a.classify: * cmp pivot;
my Promise $less = start { samewith(%prt{Less}) }
my $pivot = @unsorted.pick;
my $more = samewith(%prt{More});
%class = @unsorted.classify( * cmp $pivot );
myawait $less =andthen start|$less.result, { samewith(|%classprt{LessSame}), }|$more;
my $more = samewith(%class{More});
await $less andthen |$less.result, |%class{Same}, |$more
}
#=« Implementation Notes:
* use the current thread for More partition
* recursion on Less partition can create a large number of new threads
* samewith() refactors out the actual name of the routine.
»
</syntaxhighlight>
 
Let's tune the parallel execution by applying a minimum batch size in order to spawn a new thread.
Let's run some tests
 
<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>,
(2,<a 🎮 3, 1,z 4, 5)🐧> => (1,<a 2,🎮 3, z 4, 5),🐧>.sort
;
<a 🎮 3 z 4 🐧> => <a 🎮 3 z 4 🐧>.sort,
 
;
plan @testcases.elems * @functions-under-test.elems;
for &quicksort, &quicksort-parallel -> &fun {
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 b3 => 3 a b
ok 5 - h b a c d f e g => a b c d e f g h
ok 6 - h b a c🎮 d3 fz e4 g🐧 => a3 b4 c d ea fz g🎮 h🐧
quicksort-parallel-naive
ok 7 - 2 3 1 4 5 => 1 2 3 4 5
ok 87 - a 🎮 3 z 4 🐧 => 3 4 a z 🎮 🐧
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 913 - =>
ok 1014 - a => a
ok 1115 - a a => a a
ok 1216 - b a b3 => 3 a b
ok 1317 - h b a c d f e g => a b c d e f g h
ok 1418 - h b a c🎮 d3 fz e4 g🐧 => a3 b4 ca dz e🎮 f g h🐧</pre>
 
ok 15 - 2 3 1 4 5 => 1 2 3 4 5
===benchmarking===
ok 16 - a 🎮 3 z 4 🐧 => 3 4 a z 🎮 🐧
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,672 ⟶ 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,471 ⟶ 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,480 ⟶ 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,961 ⟶ 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,210 ⟶ 10,291:
Full example with test/debug data for ZX Spectrum is at [[https://gist.github.com/ped7g/0c4e94796b474994ed88d0bdd1bf2f25 github]].
 
=={{header|zigZig}}==
 
{{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 quicksortquickSort(comptime tT: type, arr: []tT, comptime compareFn: fn (T, T) bool) void {
if (arr.len < 2) return;
var pivot = arr[@as(usize, @intFromFloat(@floor(@as(f64, @floatFromInt(arr.len)) / 2)))];
var left: usize = 0;
var right: usize = arr.len - 1;
 
const pivot_index = partition(T, arr, compareFn);
while (left <= right) {
quickSort(T, arr[0..pivot_index], compareFn);
while (arr[left] < pivot) {
quickSort(T, arr[pivot_index + 1 .. arr.len], compareFn);
left += 1;
}
}
 
while (arr[right] > pivot) {
fn partition(comptime T: type, arr: []T, comptime compareFn: fn (T, T) bool) usize {
right -= 1;
const pivot_index = arr.len }/ 2;
const last_index = arr.len - 1;
if (left <= right) {
 
const tmp = arr[left];
std.mem.swap(T, &arr[leftpivot_index], = &arr[rightlast_index]);
 
arr[right] = tmp;
var store_index: usize left += 10;
for (arr[0 .. arr.len - 1]) |*elem_ptr| {
right -= 1;
if (compareFn(elem_ptr.*, arr[last_index])) {
std.mem.swap(T, elem_ptr, &arr[store_index]);
store_index += 1;
}
}
 
quicksortstd.mem.swap(tT, &arr[0store_index], .. right + 1&arr[last_index]);
return store_index;
quicksort(t, arr[left..]);
}</syntaxhighlight>
}
 
<syntaxhighlight lang="zig">const std = @import("std");
pub fn main() !void {
const LIST_TYPE = i16;
var arr: [10]LIST_TYPE = [_]LIST_TYPE{ 4, 65, 2, -31, 0, 99, 2, 83, 782, 1 };
var i: usize = 0;
 
pub fn main() void {
while (i < arr.len) : (i += 1) {
const print = std.debug.print("{d} ", .{arr[i]});
}
std.debug.print("\n", .{});
 
var arr = [_]i16{ 4, 65, 2, -31, 0, 99, 2, 83, 782, 1 };
i = 0;
quicksortprint(LIST_TYPE"Before: {any}\n\n", &.{arr});
 
while (i < arr.len) : (i += 1) {
print("Sort numbers in ascending stdorder.debug.print("{d} \n", .{arr[i]});
quickSort(i16, &arr, struct {
}
fn sortFn(left: i16, right: i16) bool {
std.debug.print("\n", .{});
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 }
 
-31 0 1 2 2 4 65 83 99 782
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>
 
Marvin
55

edits

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