Rosetta Code

Sorting algorithms/Quicksort: Difference between revisions

Page Discussion

Sorting algorithms/Quicksort (view source)

Revision as of 23:04, 25 March 2024

10,785 bytes added ,  1 month ago
→‎{{header|Bruijn}}
(Sorting algorithms/Quicksort in Yabasic)
(44 intermediate revisions by 18 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 3,741 ⟶ 3,798:
items.writeln;
}</syntaxhighlight>
 
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
This quick sort routine is infinitely versatile. It sorts an array of pointers. The advantage of this is that pointers can contain anything, ranging from integers, to strings, to floating point numbers to objects. The way each pointer is interpreted is through the compare routine, which is customized for the particular situation. The compare routine can interpret each pointer as a string, an integer, a float or an object and it can treat those items in different ways. For example, the order in which it compares strings controls whether the sort is alphabetical or reverse alphabetical. In this case, I show an integer sort, an alphabetic string sort, a reverse alphabetical string sort and a string sort by length.
 
<syntaxhighlight lang="Delphi">
{Dynamic array of pointers}
 
type TPointerArray = array of Pointer;
 
procedure QuickSort(SortList: TPointerArray; L, R: Integer; SCompare: TListSortCompare);
{Do quick sort on items held in TPointerArray}
{SCompare controls how the pointers are interpreted}
var I, J: Integer;
var P,T: Pointer;
begin
repeat
begin
I := L;
J := R;
P := SortList[(L + R) shr 1];
repeat
begin
while SCompare(SortList[I], P) < 0 do Inc(I);
while SCompare(SortList[J], P) > 0 do Dec(J);
if I <= J then
begin
{Exchange itesm}
T:=SortList[I];
SortList[I]:=SortList[J];
SortList[J]:=T;
if P = SortList[I] then P := SortList[J]
else if P = SortList[J] then P := SortList[I];
Inc(I);
Dec(J);
end;
end
until I > J;
if L < J then QuickSort(SortList, L, J, SCompare);
L := I;
end
until I >= R;
end;
 
 
 
procedure DisplayStrings(Memo: TMemo; PA: TPointerArray);
{Display pointers as strings}
var I: integer;
var S: string;
begin
S:='[';
for I:=0 to High(PA) do
begin
if I>0 then S:=S+' ';
S:=S+string(PA[I]^);
end;
S:=S+']';
Memo.Lines.Add(S);
end;
 
 
procedure DisplayIntegers(Memo: TMemo; PA: TPointerArray);
{Display pointer array as integers}
var I: integer;
var S: string;
begin
S:='[';
for I:=0 to High(PA) do
begin
if I>0 then S:=S+' ';
S:=S+IntToStr(Integer(PA[I]));
end;
S:=S+']';
Memo.Lines.Add(S);
end;
 
 
function IntCompare(Item1, Item2: Pointer): Integer;
{Compare for integer sort}
begin
Result:=Integer(Item1)-Integer(Item2);
end;
 
 
 
function StringCompare(Item1, Item2: Pointer): Integer;
{Compare for alphabetical string sort}
begin
Result:=AnsiCompareText(string(Item1^),string(Item2^));
end;
 
function StringRevCompare(Item1, Item2: Pointer): Integer;
{Compare for reverse alphabetical order}
begin
Result:=AnsiCompareText(string(Item2^),string(Item1^));
end;
 
 
function StringLenCompare(Item1, Item2: Pointer): Integer;
{Compare for string length sort}
begin
Result:=Length(string(Item1^))-Length(string(Item2^));
end;
 
{Arrays of strings and integers}
 
var IA: array [0..9] of integer = (23, 14, 62, 28, 56, 91, 33, 30, 75, 5);
var SA: array [0..15] of string = ('Now','is','the','time','for','all','good','men','to','come','to','the','aid','of','the','party.');
 
procedure ShowQuickSort(Memo: TMemo);
var L: TStringList;
var PA: TPointerArray;
var I: integer;
begin
Memo.Lines.Add('Integer Sort');
SetLength(PA,Length(IA));
for I:=0 to High(IA) do PA[I]:=Pointer(IA[I]);
Memo.Lines.Add('Before Sorting');
DisplayIntegers(Memo,PA);
QuickSort(PA,0,High(PA),IntCompare);
Memo.Lines.Add('After Sorting');
DisplayIntegers(Memo,PA);
 
Memo.Lines.Add('');
Memo.Lines.Add('String Sort - Alphabetical');
SetLength(PA,Length(SA));
for I:=0 to High(SA) do PA[I]:=Pointer(@SA[I]);
Memo.Lines.Add('Before Sorting');
DisplayStrings(Memo,PA);
QuickSort(PA,0,High(PA),StringCompare);
Memo.Lines.Add('After Sorting');
DisplayStrings(Memo,PA);
 
Memo.Lines.Add('');
Memo.Lines.Add('String Sort - Reverse Alphabetical');
QuickSort(PA,0,High(PA),StringRevCompare);
Memo.Lines.Add('After Sorting');
DisplayStrings(Memo,PA);
 
Memo.Lines.Add('');
Memo.Lines.Add('String Sort - By Length');
QuickSort(PA,0,High(PA),StringLenCompare);
Memo.Lines.Add('After Sorting');
DisplayStrings(Memo,PA);
end;
 
 
 
</syntaxhighlight>
{{out}}
<pre>
Integer Sort
Before Sorting
[23 14 62 28 56 91 33 30 75 5]
After Sorting
[5 14 23 28 30 33 56 62 75 91]
 
String Sort - Alphabetical
Before Sorting
[Now is the time for all good men to come to the aid of the party.]
After Sorting
[aid all come for good is men Now party. of the the the time to to]
 
String Sort - Reverse Alphabetical
After Sorting
[to to time the the the party. of Now men is good for come all aid]
 
String Sort - By Length
After Sorting
[of is to to men aid all for Now the the the time come good party.]
Elapsed Time: 16.478 ms.
 
</pre>
 
=={{header|Dart}}==
Line 3,835 ⟶ 4,067:
=={{header|EasyLang}}==
<syntaxhighlight lang="text">
funcproc qsort left right . d[] .
while left < right
# partition
piv = d[left]
mid = left
for i = left + 1 to right
if d[i] < piv
mid += 1
swap d[i] d[mid]
.
.
swap d[left] d[mid]
.
swap d[left] d[mid]#
if mid < (right + left) / 2
#
if mid < (right + qsort left) /mid - 1 2d[]
call qsort left = mid -+ 1 d[]
left = mid + 1else
qsort mid + 1 right d[]
else
call qsort mid +right 1= rightmid d[]- 1
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,159 ⟶ 4,391:
 
=={{header|Elena}}==
ELENA 56.0x :
<syntaxhighlight lang="elena">import extensions;
import system'routines;
Line 4,176 ⟶ 4,408:
auto more := new ArrayList();
self.forEach::(item)
{
if (item < pivot)
Line 4,459 ⟶ 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,429 ⟶ 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,440 ⟶ 5,600:
Cons(x,xx) -> {
val (ys, zs) = xx.partition fn(el) { el < x }
qsort(ys) ++ [x] ++ qsort(zs)
}
Nil -> Nil
Line 7,866 ⟶ 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,046 ⟶ 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,435 ⟶ 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 8,491 ⟶ 8,808:
-31 0 1 2 2 4 65 83 99 782
</pre>
 
=={{header|RPL}}==
{{works with|HP|48}}
≪ DUP SIZE → size
≪ '''IF''' size 1 > '''THEN'''
DUP size 2 / CEIL GET { } DUP DUP → pivot less equal greater
≪ 1 size '''FOR''' j
DUP j GET pivot
'''CASE'''
DUP2 < '''THEN''' DROP 'less' STO+ '''END'''
DUP2 == '''THEN''' DROP 'equal' STO+ '''END'''
DROP 'greater' STO+ '''END'''
'''NEXT''' DROP
less <span style="color:blue">QSORT</span>
greater <span style="color:blue">QSORT</span>
equal SWAP + +
≫
'''END'''
≫ ≫ '<span style="color:blue">QSORT</span>' STO
 
=={{header|Ruby}}==
Line 9,215 ⟶ 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,224 ⟶ 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,705 ⟶ 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 9,953 ⟶ 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/338980...362943"