Sorting algorithms/Quicksort: Difference between revisions
→{{header|Python}}
| (490 intermediate revisions by more than 100 users not shown) | |||
Line 1:
{{task|Sorting Algorithms}}
{{Sorting Algorithm}}
[[Category:Sorting]]
[[Category:Recursion]]
{{Wikipedia|Quicksort}}
;Task:
Sort an array (or list) elements using the [https://en.wikipedia.org/wiki/Quicksort ''quicksort''] algorithm.
The elements must have a [https://en.wikipedia.org/wiki/Weak_ordering 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.
::# Choose any element of the array to be the pivot.
::# 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.
::# Use recursion to sort both partitions.
::# Join the first sorted partition, the pivot, and the second sorted partition.
<br>
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 <big> ''[[O]](n ''log'' n)'' </big> with the best pivots, to <big> ''[[O]](n<sup>2</sup>)'' </big> with the worst pivots, where <big> ''n'' </big> is the number of elements in the array.
This is a simple quicksort algorithm, adapted from Wikipedia.
Line 49 ⟶ 64:
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|merge sort]], because both sorts have an average time of <big> ''[[O]](n ''log'' n)''. </big>
: ''"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
Line 58 ⟶ 73:
* 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.
<br>
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.
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F _quicksort(&array, start, stop) -> Void
I stop - start > 0
V pivot = array[start]
V left = start
V right = stop
L left <= right
L array[left] < pivot
left++
L array[right] > pivot
right--
I left <= right
swap(&array[left], &array[right])
left++
right--
_quicksort(&array, start, right)
_quicksort(&array, left, stop)
F quicksort(&array)
_quicksort(&array, 0, array.len - 1)
V arr = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]
quicksort(&arr)
print(arr)</syntaxhighlight>
{{out}}
<pre>
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
</pre>
=={{header|360 Assembly}}==
{{trans|REXX}}
Structured version with ASM & ASSIST macros.
<syntaxhighlight lang="360asm">* Quicksort 14/09/2015 & 23/06/2016
QUICKSOR CSECT
USING QUICKSOR,R13 base register
B 72(R15) skip savearea
DC 17F'0' savearea
STM R14,R12,12(R13) prolog
ST R13,4(R15) "
ST R15,8(R13) "
LR R13,R15 "
MVC A,=A(1) a(1)=1
MVC B,=A(NN) b(1)=hbound(t)
L R6,=F'1' k=1
DO WHILE=(LTR,R6,NZ,R6) do while k<>0 ==================
LR R1,R6 k
SLA R1,2 ~
L R10,A-4(R1) l=a(k)
LR R1,R6 k
SLA R1,2 ~
L R11,B-4(R1) m=b(k)
BCTR R6,0 k=k-1
LR R4,R11 m
C R4,=F'2' if m<2
BL ITERATE then iterate
LR R2,R10 l
AR R2,R11 +m
BCTR R2,0 -1
ST R2,X x=l+m-1
LR R2,R11 m
SRA R2,1 m/2
AR R2,R10 +l
ST R2,Y y=l+m/2
L R1,X x
SLA R1,2 ~
L R4,T-4(R1) r4=t(x)
L R1,Y y
SLA R1,2 ~
L R5,T-4(R1) r5=t(y)
LR R1,R10 l
SLA R1,2 ~
L R3,T-4(R1) r3=t(l)
IF CR,R4,LT,R3 if t(x)<t(l) ---+
IF CR,R5,LT,R4 if t(y)<t(x) |
LR R7,R4 p=t(x) |
L R1,X x |
SLA R1,2 ~ |
ST R3,T-4(R1) t(x)=t(l) |
ELSEIF CR,R5,GT,R3 elseif t(y)>t(l) |
LR R7,R3 p=t(l) |
ELSE , else |
LR R7,R5 p=t(y) |
L R1,Y y |
SLA R1,2 ~ |
ST R3,T-4(R1) t(y)=t(l) |
ENDIF , end if |
ELSE , else |
IF CR,R5,LT,R3 if t(y)<t(l) |
LR R7,R3 p=t(l) |
ELSEIF CR,R5,GT,R4 elseif t(y)>t(x) |
LR R7,R4 p=t(x) |
L R1,X x |
SLA R1,2 ~ |
ST R3,T-4(R1) t(x)=t(l) |
ELSE , else |
LR R7,R5 p=t(y) |
L R1,Y y |
SLA R1,2 ~ |
ST R3,T-4(R1) t(y)=t(l) |
ENDIF , end if |
ENDIF , end if ---+
LA R8,1(R10) i=l+1
L R9,X j=x
FOREVER EQU * do forever --------------------+
LR R1,R8 i |
SLA R1,2 ~ |
LA R2,T-4(R1) @t(i) |
L R0,0(R2) t(i) |
DO WHILE=(CR,R8,LE,R9,AND, while i<=j and ---+ | X
CR,R0,LE,R7) t(i)<=p | |
AH R8,=H'1' i=i+1 | |
AH R2,=H'4' @t(i) | |
L R0,0(R2) t(i) | |
ENDDO , end while ---+ |
LR R1,R9 j |
SLA R1,2 ~ |
LA R2,T-4(R1) @t(j) |
L R0,0(R2) t(j) |
DO WHILE=(CR,R8,LT,R9,AND, while i<j and ---+ | X
CR,R0,GE,R7) t(j)>=p | |
SH R9,=H'1' j=j-1 | |
SH R2,=H'4' @t(j) | |
L R0,0(R2) t(j) | |
ENDDO , end while ---+ |
CR R8,R9 if i>=j |
BNL LEAVE then leave (segment finished) |
LR R1,R8 i |
SLA R1,2 ~ |
LA R2,T-4(R1) @t(i) |
LR R1,R9 j |
SLA R1,2 ~ |
LA R3,T-4(R1) @t(j) |
L R0,0(R2) w=t(i) + |
MVC 0(4,R2),0(R3) t(i)=t(j) |swap t(i),t(j) |
ST R0,0(R3) t(j)=w + |
B FOREVER end do forever ----------------+
LEAVE EQU *
LR R9,R8 j=i
BCTR R9,0 j=i-1
LR R1,R9 j
SLA R1,2 ~
LA R3,T-4(R1) @t(j)
L R2,0(R3) t(j)
LR R1,R10 l
SLA R1,2 ~
ST R2,T-4(R1) t(l)=t(j)
ST R7,0(R3) t(j)=p
LA R6,1(R6) k=k+1
LR R1,R6 k
SLA R1,2 ~
LA R4,A-4(R1) r4=@a(k)
LA R5,B-4(R1) r5=@b(k)
IF C,R8,LE,Y if i<=y ----+
ST R8,0(R4) a(k)=i |
L R2,X x |
SR R2,R8 -i |
LA R2,1(R2) +1 |
ST R2,0(R5) b(k)=x-i+1 |
LA R6,1(R6) k=k+1 |
ST R10,4(R4) a(k)=l |
LR R2,R9 j |
SR R2,R10 -l |
ST R2,4(R5) b(k)=j-l |
ELSE , else |
ST R10,4(R4) a(k)=l |
LR R2,R9 j |
SR R2,R10 -l |
ST R2,0(R5) b(k)=j-l |
LA R6,1(R6) k=k+1 |
ST R8,4(R4) a(k)=i |
L R2,X x |
SR R2,R8 -i |
LA R2,1(R2) +1 |
ST R2,4(R5) b(k)=x-i+1 |
ENDIF , end if ----+
ITERATE EQU *
ENDDO , end while =====================
* *** ********* print sorted table
LA R3,PG ibuffer
LA R4,T @t(i)
DO WHILE=(C,R4,LE,=A(TEND)) do i=1 to hbound(t)
L R2,0(R4) t(i)
XDECO R2,XD edit t(i)
MVC 0(4,R3),XD+8 put in buffer
LA R3,4(R3) ibuffer=ibuffer+1
LA R4,4(R4) i=i+1
ENDDO , end do
XPRNT PG,80 print buffer
L R13,4(0,R13) epilog
LM R14,R12,12(R13) "
XR R15,R15 "
BR R14 exit
T DC F'10',F'9',F'9',F'6',F'7',F'16',F'1',F'16',F'17',F'15'
DC F'1',F'9',F'18',F'16',F'8',F'20',F'18',F'2',F'19',F'8'
TEND DS 0F
NN EQU (TEND-T)/4)
A DS (NN)F same size as T
B DS (NN)F same size as T
X DS F
Y DS F
PG DS CL80
XD DS CL12
YREGS
END QUICKSOR</syntaxhighlight>
{{out}}
<pre>
1 1 2 6 7 8 8 9 9 9 10 15 16 16 16 17 18 18 19 20
</pre>
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program quickSort64.s */
/*******************************************/
/* Constantes file */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeConstantesARM64.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessSortOk: .asciz "Table sorted.\n"
szMessSortNok: .asciz "Table not sorted !!!!!.\n"
sMessResult: .asciz "Value : @ \n"
szCarriageReturn: .asciz "\n"
.align 4
TableNumber: .quad 1,3,6,2,5,9,10,8,4,7,11
#TableNumber: .quad 10,9,8,7,6,-5,4,3,2,1
.equ NBELEMENTS, (. - TableNumber) / 8
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: // entry of program
ldr x0,qAdrTableNumber // address number table
mov x1,0 // first element
mov x2,NBELEMENTS // number of élements
bl quickSort
ldr x0,qAdrTableNumber // address number table
bl displayTable
ldr x0,qAdrTableNumber // address number table
mov x1,NBELEMENTS // number of élements
bl isSorted // control sort
cmp x0,1 // sorted ?
beq 1f
ldr x0,qAdrszMessSortNok // no !! error sort
bl affichageMess
b 100f
1: // yes
ldr x0,qAdrszMessSortOk
bl affichageMess
100: // standard end of the program
mov x0,0 // return code
mov x8,EXIT // request to exit program
svc 0 // perform the system call
qAdrsZoneConv: .quad sZoneConv
qAdrszCarriageReturn: .quad szCarriageReturn
qAdrsMessResult: .quad sMessResult
qAdrTableNumber: .quad TableNumber
qAdrszMessSortOk: .quad szMessSortOk
qAdrszMessSortNok: .quad szMessSortNok
/******************************************************************/
/* control sorted table */
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the number of elements > 0 */
/* x0 return 0 if not sorted 1 if sorted */
isSorted:
stp x2,lr,[sp,-16]! // save registers
stp x3,x4,[sp,-16]! // save registers
mov x2,0
ldr x4,[x0,x2,lsl 3]
1:
add x2,x2,1
cmp x2,x1
bge 99f
ldr x3,[x0,x2, lsl 3]
cmp x3,x4
blt 98f
mov x4,x3
b 1b
98:
mov x0,0 // not sorted
b 100f
99:
mov x0,1 // sorted
100:
ldp x3,x4,[sp],16 // restaur 2 registers
ldp x2,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/***************************************************/
/* Appel récursif Tri Rapide quicksort */
/***************************************************/
/* x0 contains the address of table */
/* x1 contains index of first item */
/* x2 contains the number of elements > 0 */
quickSort:
stp x2,lr,[sp,-16]! // save registers
stp x3,x4,[sp,-16]! // save registers
str x5, [sp,-16]! // save registers
sub x2,x2,1 // last item index
cmp x1,x2 // first > last ?
bge 100f // yes -> end
mov x4,x0 // save x0
mov x5,x2 // save x2
bl partition1 // cutting into 2 parts
mov x2,x0 // index partition
mov x0,x4 // table address
bl quickSort // sort lower part
add x1,x2,1 // index begin = index partition + 1
add x2,x5,1 // number of elements
bl quickSort // sort higter part
100: // end function
ldr x5, [sp],16 // restaur 1 register
ldp x3,x4,[sp],16 // restaur 2 registers
ldp x2,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/******************************************************************/
/* Partition table elements */
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains index of first item */
/* x2 contains index of last item */
partition1:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
stp x4,x5,[sp,-16]! // save registers
stp x6,x7,[sp,-16]! // save registers
ldr x3,[x0,x2,lsl 3] // load value last index
mov x4,x1 // init with first index
mov x5,x1 // init with first index
1: // begin loop
ldr x6,[x0,x5,lsl 3] // load value
cmp x6,x3 // compare value
bge 2f
ldr x7,[x0,x4,lsl 3] // if < swap value table
str x6,[x0,x4,lsl 3]
str x7,[x0,x5,lsl 3]
add x4,x4,1 // and increment index 1
2:
add x5,x5,1 // increment index 2
cmp x5,x2 // end ?
blt 1b // no loop
ldr x7,[x0,x4,lsl 3] // swap value
str x3,[x0,x4,lsl 3]
str x7,[x0,x2,lsl 3]
mov x0,x4 // return index partition
100:
ldp x6,x7,[sp],16 // restaur 2 registers
ldp x4,x5,[sp],16 // restaur 2 registers
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/******************************************************************/
/* Display table elements */
/******************************************************************/
/* x0 contains the address of table */
displayTable:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
mov x2,x0 // table address
mov x3,0
1: // loop display table
ldr x0,[x2,x3,lsl 3]
ldr x1,qAdrsZoneConv
bl conversion10S // décimal conversion
ldr x0,qAdrsMessResult
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc // insert result at // character
bl affichageMess // display message
add x3,x3,1
cmp x3,NBELEMENTS - 1
ble 1b
ldr x0,qAdrszCarriageReturn
bl affichageMess
mov x0,x2
100:
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/********************************************************/
/* File Include fonctions */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
<pre>
Value : +1
Value : +2
Value : +3
Value : +4
Value : +5
Value : +6
Value : +7
Value : +8
Value : +9
Value : +10
Value : +11
Table sorted.
</pre>
=={{header|ABAP}}==
This works for ABAP Version 7.40 and above
<syntaxhighlight lang="abap">
report z_quicksort.
data(numbers) = value int4_table( ( 4 ) ( 65 ) ( 2 ) ( -31 ) ( 0 ) ( 99 ) ( 2 ) ( 83 ) ( 782 ) ( 1 ) ).
perform quicksort changing numbers.
write `[`.
loop at numbers assigning field-symbol(<numbers>).
write <numbers>.
endloop.
write `]`.
form quicksort changing numbers type int4_table.
data(less) = value int4_table( ).
data(equal) = value int4_table( ).
data(greater) = value int4_table( ).
if lines( numbers ) > 1.
data(pivot) = numbers[ lines( numbers ) / 2 ].
loop at numbers assigning field-symbol(<number>).
if <number> < pivot.
append <number> to less.
elseif <number> = pivot.
append <number> to equal.
elseif <number> > pivot.
append <number> to greater.
endif.
endloop.
perform quicksort changing less.
perform quicksort changing greater.
clear numbers.
append lines of less to numbers.
append lines of equal to numbers.
append lines of greater to numbers.
endif.
endform.
</syntaxhighlight>
{{out}}
<pre>
[ 31- 0 1 2 2 4 65 83 99 782 ]
</pre>
=={{header|ACL2}}==
<
(if (endp xs)
(mv nil nil)
Line 80 ⟶ 566:
(append (qsort less)
(list (first xs))
(qsort more)))))</
Usage:
<syntaxhighlight lang="text">> (qsort '(8 6 7 5 3 0 9))
(0 3 5 6 7 8 9)</
=={{header|Action!}}==
Action! language does not support recursion. Therefore an iterative approach with a stack has been proposed.
<syntaxhighlight lang="action!">DEFINE MAX_COUNT="100"
INT ARRAY stack(MAX_COUNT)
INT stackSize
PROC PrintArray(INT ARRAY a INT size)
INT i
Put('[)
FOR i=0 TO size-1
DO
IF i>0 THEN Put(' ) FI
PrintI(a(i))
OD
Put(']) PutE()
RETURN
PROC InitStack()
stackSize=0
RETURN
BYTE FUNC IsEmpty()
IF stackSize=0 THEN
RETURN (1)
FI
RETURN (0)
PROC Push(INT low,high)
stack(stackSize)=low stackSize==+1
stack(stackSize)=high stackSize==+1
RETURN
PROC Pop(INT POINTER low,high)
stackSize==-1 high^=stack(stackSize)
stackSize==-1 low^=stack(stackSize)
RETURN
INT FUNC Partition(INT ARRAY a INT low,high)
INT part,v,i,tmp
v=a(high)
part=low-1
FOR i=low TO high-1
DO
IF a(i)<=v THEN
part==+1
tmp=a(part) a(part)=a(i) a(i)=tmp
FI
OD
part==+1
tmp=a(part) a(part)=a(high) a(high)=tmp
RETURN (part)
PROC QuickSort(INT ARRAY a INT size)
INT low,high,part
InitStack()
Push(0,size-1)
WHILE IsEmpty()=0
DO
Pop(@low,@high)
part=Partition(a,low,high)
IF part-1>low THEN
Push(low,part-1)
FI
IF part+1<high THEN
Push(part+1,high)
FI
OD
RETURN
PROC Test(INT ARRAY a INT size)
PrintE("Array before sort:")
PrintArray(a,size)
QuickSort(a,size)
PrintE("Array after sort:")
PrintArray(a,size)
PutE()
RETURN
PROC Main()
INT ARRAY
a(10)=[1 4 65535 0 3 7 4 8 20 65530],
b(21)=[10 9 8 7 6 5 4 3 2 1 0
65535 65534 65533 65532 65531
65530 65529 65528 65527 65526],
c(8)=[101 102 103 104 105 106 107 108],
d(12)=[1 65535 1 65535 1 65535 1
65535 1 65535 1 65535]
Test(a,10)
Test(b,21)
Test(c,8)
Test(d,12)
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Quicksort.png Screenshot from Atari 8-bit computer]
<pre>
Array before sort:
[1 4 -1 0 3 7 4 8 20 -6]
Array after sort:
[-6 -1 0 1 3 4 4 7 8 20]
Array before sort:
[10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10]
Array after sort:
[-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10]
Array before sort:
[101 102 103 104 105 106 107 108]
Array after sort:
[101 102 103 104 105 106 107 108]
Array before sort:
[1 -1 1 -1 1 -1 1 -1 1 -1 1 -1]
Array after sort:
[-1 -1 -1 -1 -1 -1 1 1 1 1 1 1]
</pre>
=={{header|ActionScript}}==
{{works with|ActionScript|3}}<br>
The functional programming way
<
{
if (array.length <= 1)
Line 99 ⟶ 707:
array.filter(function (x:Number, index:int, array:Array):Boolean { return x == pivot; })).concat(
quickSort(array.filter(function (x:Number, index:int, array:Array):Boolean { return x > pivot; })));
}</
The faster way
<
{
if (array.length <= 1)
Line 125 ⟶ 733:
equal).concat(
quickSort(greater));
}</
=={{header|Ada}}==
This example is implemented as a generic procedure.
The procedure specification is:
<syntaxhighlight lang="ada">-----------------------------------------------------------------------
-- Generic Quick_Sort procedure
-----------------------------------------------------------------------
generic
type
type Element_Array is array(
with function "<" (Left, Right :
procedure Quick_Sort(A : in out Element_Array);</syntaxhighlight>
The procedure body deals with any discrete index type, either an integer type or an enumerated type.
<
-- Generic
-----------------------------------------------------------------------
procedure
procedure Swap(Left, Right :
Temp :
begin
A (Left) := A (Right);
A (Right) := Temp;
end Swap;
begin
if
declare
Pivot_Value : Element := A
Left : Index := A'First;
begin
while Left < Right and not (Pivot_Value < A (Left)) loop
end
end
end loop;
if Left
Quick_Sort (A
Quick_Sort (A (Left .. A'Last));
end;
end if;
end
An example of how this procedure may be used is:
<syntaxhighlight lang
with Ada.Text_Io;
with Ada.Float_Text_IO; use Ada.Float_Text_IO;
with Quick_Sort;
procedure Sort_Test is
type Days is (Mon, Tue, Wed, Thu, Fri, Sat, Sun);
type Sales is array (Days range <>) of Float;
procedure Sort_Days is new
procedure Print (Item : Sales) is
begin
for I in Item'range loop
Line 220 ⟶ 826:
Print(Weekly_Sales);
end Sort_Test;</
=={{header|ALGOL 68}}==
<syntaxhighlight lang="algol68">#--- Swap function ---#
(
INT
array[first] := array[second];
array[second]:= temp
);
#--- Quick sort 3 arg function ---#
PROC quick = (REF [] INT array, INT first, INT last) VOID:
(
INT smaller := first + 1,
pivot := array[first];
WHILE smaller <= larger DO
WHILE array[smaller] < pivot AND smaller < last DO
smaller +:= 1
OD;
WHILE array[larger] > pivot AND larger > first DO
larger -:= 1
OD;
IF smaller < larger THEN
swap(array, smaller, larger);
smaller +:= 1;
larger -:= 1
ELSE
smaller +:= 1
FI
OD;
swap(array, first, larger);
IF first < larger-1 THEN
IF last > larger +1 THEN
quick(array, larger+1, last)
);
#--- Quick sort 1 arg function ---#
PROC quicksort
(
IF UPB array > 1 THEN
FI
);
#***************************************************************#
main:
(
[10]INT a;
FOR i FROM 1 TO UPB a DO
a[i] := ROUND(random*1000)
OD;
print(("Before:", a));
quicksort(a);
print((newline, newline));
print(("After: ", a))
)
</syntaxhighlight>
{{out}}
<pre>
Before: +73 +921 +179 +961 +50 +324 +82 +178 +243 +458
After: +50 +73 +82 +178 +179 +243 +324 +458 +921 +961
</pre>
=={{header|ALGOL W}}==
<syntaxhighlight lang="algolw">% Quicksorts in-place the array of integers v, from lb to ub %
procedure quicksort ( integer array v( * )
; integer value lb, ub
) ;
if ub > lb then begin
% more than one element, so must sort %
integer left, right, pivot;
left := lb;
right := ub;
% choosing the middle element of the array as the pivot %
pivot := v( left + ( ( right + 1 ) - left ) div 2 );
while begin
while left <= ub and v( left ) < pivot do left := left + 1;
while right >= lb and v( right ) > pivot do right := right - 1;
left <= right
end do begin
integer swap;
swap := v( left );
v( left ) := v( right );
v( right ) := swap;
left := left + 1;
right := right - 1
end while_left_le_right ;
quicksort( v, lb, right );
quicksort( v, left, ub )
end quicksort ;</syntaxhighlight>
=={{header|APL}}==
{{works with|Dyalog APL}}{{trans|J}}
<syntaxhighlight lang="apl"> qsort ← {1≥⍴⍵:⍵ ⋄ e←⍵[?⍴⍵] ⋄ (∇(⍵<e)/⍵) , ((⍵=e)/⍵) , (∇(⍵>e)/⍵)}
qsort 31 4 1 5 9 2 6 5 3 5 8
1 2 3 4 5 5 5 6 8 9 31</syntaxhighlight>
Of course, in real APL applications, one would use ⍋ (Grade Up) to sort (which will pick a sorting algorithm suited to the argument):
<syntaxhighlight lang="apl"> sort ← {⍵[⍋⍵]}
sort 31 4 1 5 9 2 6 5 3 5 8
1 2 3 4 5 5 5 6 8 9 31</syntaxhighlight>
=={{header|AppleScript}}==
===Functional===
Emphasising clarity and simplicity more than run-time performance. (Practical scripts will often delegate sorting to the OS X shell, or, since OS X Yosemite, to Foundation classes through the ObjC interface).
{{trans|JavaScript}}
(Functional ES5 version)
<syntaxhighlight lang="applescript">-- quickSort :: (Ord a) => [a] -> [a]
on quickSort(xs)
if length of xs > 1 then
set {h, t} to uncons(xs)
-- lessOrEqual :: a -> Bool
script lessOrEqual
on |λ|(x)
x ≤ h
end |λ|
end script
set {less, more} to partition(lessOrEqual, t)
quickSort(less) & h & quickSort(more)
else
xs
end if
end quickSort
-- TEST -----------------------------------------------------------------------
on run
quickSort([11.8, 14.1, 21.3, 8.5, 16.7, 5.7])
--> {5.7, 8.5, 11.8, 14.1, 16.7, 21.3}
end run
-- GENERIC FUNCTIONS ----------------------------------------------------------
-- partition :: predicate -> List -> (Matches, nonMatches)
-- partition :: (a -> Bool) -> [a] -> ([a], [a])
on partition(f, xs)
tell mReturn(f)
set lst to {{}, {}}
repeat with x in xs
set v to contents of x
set end of item ((|λ|(v) as integer) + 1) of lst to v
end repeat
return {item 2 of lst, item 1 of lst}
end tell
end partition
-- uncons :: [a] -> Maybe (a, [a])
on uncons(xs)
if length of xs > 0 then
{item 1 of xs, rest of xs}
else
missing value
end if
end uncons
-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: Handler -> Script
on mReturn(f)
if class of f is script then
f
else
script
property |λ| : f
end script
end if
end mReturn</syntaxhighlight>
{{Out}}
<syntaxhighlight lang="applescript">{5.7, 8.5, 11.8, 14.1, 16.7, 21.3}</syntaxhighlight>
----
===Straightforward===
Emphasising clarity, quick sorting, ''and'' correct AppleScript:
<syntaxhighlight lang="applescript">-- In-place Quicksort (basic algorithm).
-- Algorithm: S.A.R. (Tony) Hoare, 1960.
on quicksort(theList, l, r) -- Sort items l thru r of theList.
set listLength to (count theList)
if (listLength < 2) then return
-- Convert negative and/or transposed range indices.
if (l < 0) then set l to listLength + l + 1
if (r < 0) then set r to listLength + r + 1
if (l > r) then set {l, r} to {r, l}
-- Script object containing the list as a property (to allow faster references to its items)
-- and the recursive subhandler.
script o
property lst : theList
on qsrt(l, r)
set pivot to my lst's item ((l + r) div 2)
set i to l
set j to r
repeat until (i > j)
set lv to my lst's item i
repeat while (pivot > lv)
set i to i + 1
set lv to my lst's item i
end repeat
set rv to my lst's item j
repeat while (rv > pivot)
set j to j - 1
set rv to my lst's item j
end repeat
if (j > i) then
set my lst's item i to rv
set my lst's item j to lv
else if (i > j) then
exit repeat
end if
set i to i + 1
set j to j - 1
end repeat
if (j > l) then qsrt(l, j)
if (i < r) then qsrt(i, r)
end qsrt
end script
tell o to qsrt(l, r)
return -- nothing.
end quicksort
property sort : quicksort
-- Demo:
local aList
set aList to {28, 9, 95, 22, 67, 55, 20, 41, 60, 53, 100, 72, 19, 67, 14, 42, 29, 20, 74, 39}
sort(aList, 1, -1) -- Sort items 1 thru -1 of aList.
return aList</syntaxhighlight>
{{output}}
<syntaxhighlight lang="applescript">{9, 14, 19, 20, 20, 22, 28, 29, 39, 41, 42, 53, 55, 60, 67, 67, 72, 74, 95, 100}</syntaxhighlight>
=={{header|Arc}}==
<syntaxhighlight lang="arc">(def qs (seq)
(if (empty seq) nil
(let pivot (car seq)
(join (qs (keep [< _ pivot] (cdr seq)))
(list pivot)
(qs (keep [>= _ pivot] (cdr seq)))))))</syntaxhighlight>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program quickSort.s */
/* look pseudo code in wikipedia quicksort */
/************************************/
/* Constantes */
/************************************/
.equ STDOUT, 1 @ Linux output console
.equ EXIT, 1 @ Linux syscall
.equ WRITE, 4 @ Linux syscall
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessSortOk: .asciz "Table sorted.\n"
szMessSortNok: .asciz "Table not sorted !!!!!.\n"
sMessResult: .ascii "Value : "
sMessValeur: .fill 11, 1, ' ' @ size => 11
szCarriageReturn: .asciz "\n"
.align 4
iGraine: .int 123456
.equ NBELEMENTS, 10
#TableNumber: .int 9,5,6,1,2,3,10,8,4,7
#TableNumber: .int 1,3,5,2,4,6,10,8,4,7
#TableNumber: .int 1,3,5,2,4,6,10,8,4,7
#TableNumber: .int 1,2,3,4,5,6,10,8,4,7
TableNumber: .int 10,9,8,7,6,5,4,3,2,1
#TableNumber: .int 13,12,11,10,9,8,7,6,5,4,3,2,1
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: @ entry of program
1:
ldr r0,iAdrTableNumber @ address number table
mov r1,#0 @ indice first item
mov r2,#NBELEMENTS @ number of élements
bl triRapide @ call quicksort
ldr r0,iAdrTableNumber @ address number table
bl displayTable
ldr r0,iAdrTableNumber @ address number table
mov r1,#NBELEMENTS @ number of élements
bl isSorted @ control sort
cmp r0,#1 @ sorted ?
beq 2f
ldr r0,iAdrszMessSortNok @ no !! error sort
bl affichageMess
b 100f
2: @ yes
ldr r0,iAdrszMessSortOk
bl affichageMess
100: @ standard end of the program
mov r0, #0 @ return code
mov r7, #EXIT @ request to exit program
svc #0 @ perform the system call
iAdrsMessValeur: .int sMessValeur
iAdrszCarriageReturn: .int szCarriageReturn
iAdrsMessResult: .int sMessResult
iAdrTableNumber: .int TableNumber
iAdrszMessSortOk: .int szMessSortOk
iAdrszMessSortNok: .int szMessSortNok
/******************************************************************/
/* control sorted table */
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the number of elements > 0 */
/* r0 return 0 if not sorted 1 if sorted */
isSorted:
push {r2-r4,lr} @ save registers
mov r2,#0
ldr r4,[r0,r2,lsl #2]
1:
add r2,#1
cmp r2,r1
movge r0,#1
bge 100f
ldr r3,[r0,r2, lsl #2]
cmp r3,r4
movlt r0,#0
blt 100f
mov r4,r3
b 1b
100:
pop {r2-r4,lr}
bx lr @ return
/***************************************************/
/* Appel récursif Tri Rapide quicksort */
/***************************************************/
/* r0 contains the address of table */
/* r1 contains index of first item */
/* r2 contains the number of elements > 0 */
triRapide:
push {r2-r5,lr} @ save registers
sub r2,#1 @ last item index
cmp r1,r2 @ first > last ?
bge 100f @ yes -> end
mov r4,r0 @ save r0
mov r5,r2 @ save r2
bl partition1 @ cutting into 2 parts
mov r2,r0 @ index partition
mov r0,r4 @ table address
bl triRapide @ sort lower part
add r1,r2,#1 @ index begin = index partition + 1
add r2,r5,#1 @ number of elements
bl triRapide @ sort higter part
100: @ end function
pop {r2-r5,lr} @ restaur registers
bx lr @ return
/******************************************************************/
/* Partition table elements */
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains index of first item */
/* r2 contains index of last item */
partition1:
push {r1-r7,lr} @ save registers
ldr r3,[r0,r2,lsl #2] @ load value last index
mov r4,r1 @ init with first index
mov r5,r1 @ init with first index
1: @ begin loop
ldr r6,[r0,r5,lsl #2] @ load value
cmp r6,r3 @ compare value
ldrlt r7,[r0,r4,lsl #2] @ if < swap value table
strlt r6,[r0,r4,lsl #2]
strlt r7,[r0,r5,lsl #2]
addlt r4,#1 @ and increment index 1
add r5,#1 @ increment index 2
cmp r5,r2 @ end ?
blt 1b @ no loop
ldr r7,[r0,r4,lsl #2] @ swap value
str r3,[r0,r4,lsl #2]
str r7,[r0,r2,lsl #2]
mov r0,r4 @ return index partition
100:
pop {r1-r7,lr}
bx lr
/******************************************************************/
/* Display table elements */
/******************************************************************/
/* r0 contains the address of table */
displayTable:
push {r0-r3,lr} @ save registers
mov r2,r0 @ table address
mov r3,#0
1: @ loop display table
ldr r0,[r2,r3,lsl #2]
ldr r1,iAdrsMessValeur @ display value
bl conversion10 @ call function
ldr r0,iAdrsMessResult
bl affichageMess @ display message
add r3,#1
cmp r3,#NBELEMENTS - 1
ble 1b
ldr r0,iAdrszCarriageReturn
bl affichageMess
100:
pop {r0-r3,lr}
bx lr
/******************************************************************/
/* display text with size calculation */
/******************************************************************/
/* r0 contains the address of the message */
affichageMess:
push {r0,r1,r2,r7,lr} @ save registres
mov r2,#0 @ counter length
1: @ loop length calculation
ldrb r1,[r0,r2] @ read octet start position + index
cmp r1,#0 @ if 0 its over
addne r2,r2,#1 @ else add 1 in the length
bne 1b @ and loop
@ so here r2 contains the length of the message
mov r1,r0 @ address message in r1
mov r0,#STDOUT @ code to write to the standard output Linux
mov r7, #WRITE @ code call system "write"
svc #0 @ call systeme
pop {r0,r1,r2,r7,lr} @ restaur des 2 registres */
bx lr @ return
/******************************************************************/
/* Converting a register to a decimal unsigned */
/******************************************************************/
/* r0 contains value and r1 address area */
/* r0 return size of result (no zero final in area) */
/* area size => 11 bytes */
.equ LGZONECAL, 10
conversion10:
push {r1-r4,lr} @ save registers
mov r3,r1
mov r2,#LGZONECAL
1: @ start loop
bl divisionpar10U @ unsigned r0 <- dividende. quotient ->r0 reste -> r1
add r1,#48 @ digit
strb r1,[r3,r2] @ store digit on area
cmp r0,#0 @ stop if quotient = 0
subne r2,#1 @ else previous position
bne 1b @ and loop
@ and move digit from left of area
mov r4,#0
2:
ldrb r1,[r3,r2]
strb r1,[r3,r4]
add r2,#1
add r4,#1
cmp r2,#LGZONECAL
ble 2b
@ and move spaces in end on area
mov r0,r4 @ result length
mov r1,#' ' @ space
3:
strb r1,[r3,r4] @ store space in area
add r4,#1 @ next position
cmp r4,#LGZONECAL
ble 3b @ loop if r4 <= area size
100:
pop {r1-r4,lr} @ restaur registres
bx lr @return
/***************************************************/
/* division par 10 unsigned */
/***************************************************/
/* r0 dividende */
/* r0 quotient */
/* r1 remainder */
divisionpar10U:
push {r2,r3,r4, lr}
mov r4,r0 @ save value
//mov r3,#0xCCCD @ r3 <- magic_number lower raspberry 3
//movt r3,#0xCCCC @ r3 <- magic_number higter raspberry 3
ldr r3,iMagicNumber @ r3 <- magic_number raspberry 1 2
umull r1, r2, r3, r0 @ r1<- Lower32Bits(r1*r0) r2<- Upper32Bits(r1*r0)
mov r0, r2, LSR #3 @ r2 <- r2 >> shift 3
add r2,r0,r0, lsl #2 @ r2 <- r0 * 5
sub r1,r4,r2, lsl #1 @ r1 <- r4 - (r2 * 2) = r4 - (r0 * 10)
pop {r2,r3,r4,lr}
bx lr @ leave function
iMagicNumber: .int 0xCCCCCCCD
</syntaxhighlight>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">quickSort: function [items][
if 2 > size items -> return items
pivot: first items
left: select slice items 1 (size items)-1 'x -> x < pivot
right: select slice items 1 (size items)-1 'x -> x >= pivot
((quickSort left) ++ pivot) ++ quickSort right
]
print quickSort [3 1 2 8 5 7 9 4 6]</syntaxhighlight>
{{out}}
<pre>1 2 3 4 5 6 7 8 9</pre>
=={{header|ATS}}==
=== A quicksort working on non-linear linked lists ===
<syntaxhighlight lang="ats">(*------------------------------------------------------------------*)
(* Quicksort in ATS2, for non-linear lists. *)
(*------------------------------------------------------------------*)
#include "share/atspre_staload.hats"
#define NIL list_nil ()
#define :: list_cons
(*------------------------------------------------------------------*)
(* A simple quicksort working on "garbage-collected" linked lists,
with first element as pivot. This is meant as a demonstration, not
as a superior sort algorithm.
It is based on the "not-in-place" task pseudocode. *)
datatype comparison_result =
| first_is_less_than_second of ()
| first_is_equal_to_second of ()
| first_is_greater_than_second of ()
extern fun {a : t@ype}
list_quicksort$comparison (x : a, y : a) :<> comparison_result
extern fun {a : t@ype}
list_quicksort {n : int}
(lst : list (a, n)) :<> list (a, n)
(* - - - - - - - - - - - - - - - - - - - - - - *)
implement {a}
list_quicksort {n} (lst) =
let
fun
partition {n : nat}
.<n>. (* Proof of termination. *)
(lst : list (a, n),
pivot : a)
:<> [n1, n2, n3 : int | n1 + n2 + n3 == n]
@(list (a, n1), list (a, n2), list (a, n3)) =
(* This implementation is *not* tail recursive. I may get a
scolding for using ATS to risk stack overflow! However, I
need more practice writing non-tail routines. :) Also, a lot
of programmers in other languages would do it this
way--especially if the lists are evaluated lazily. *)
case+ lst of
| NIL => @(NIL, NIL, NIL)
| head :: tail =>
let
val @(lt, eq, gt) = partition (tail, pivot)
prval () = lemma_list_param lt
prval () = lemma_list_param eq
prval () = lemma_list_param gt
in
case+ list_quicksort$comparison<a> (head, pivot) of
| first_is_less_than_second () => @(head :: lt, eq, gt)
| first_is_equal_to_second () => @(lt, head :: eq, gt)
| first_is_greater_than_second () => @(lt, eq, head :: gt)
end
fun
quicksort {n : nat}
.<n>. (* Proof of termination. *)
(lst : list (a, n))
:<> list (a, n) =
case+ lst of
| NIL => lst
| _ :: NIL => lst
| head :: tail =>
let
(* We are careful here to run "partition" on "tail" rather
than "lst", so the termination metric will be provably
decreasing. (Really the compiler *forces* us to take such
care, or else to change :<> to :<!ntm>) *)
val pivot = head
prval () = lemma_list_param tail
val @(lt, eq, gt) = partition {n - 1} (tail, pivot)
prval () = lemma_list_param lt
prval () = lemma_list_param eq
prval () = lemma_list_param gt
val eq = pivot :: eq
and lt = quicksort lt
and gt = quicksort gt
in
lt + (eq + gt)
end
prval () = lemma_list_param lst
in
quicksort {n} lst
end
(*------------------------------------------------------------------*)
val example_strings =
$list ("choose", "any", "element", "of", "the", "array",
"to", "be", "the", "pivot",
"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",
"use", "recursion", "to", "sort", "both", "partitions",
"join", "the", "first", "sorted", "partition", "the",
"pivot", "and", "the", "second", "sorted", "partition")
implement
list_quicksort$comparison<string> (x, y) =
let
val i = strcmp (x, y)
in
if i < 0 then
first_is_less_than_second
else if i = 0 then
first_is_equal_to_second
else
first_is_greater_than_second
end
implement
main0 () =
let
val sorted_strings = list_quicksort<string> example_strings
fun
print_strings {n : nat} .<n>.
(strings : list (string, n),
i : int) : void =
case+ strings of
| NIL => if i <> 1 then println! () else ()
| head :: tail =>
begin
print! head;
if i = 8 then
begin
println! ();
print_strings (tail, 1)
end
else
begin
print! " ";
print_strings (tail, succ i)
end
end
in
println! (length example_strings);
println! (length sorted_strings);
print_strings (sorted_strings, 1)
end
(*------------------------------------------------------------------*)</syntaxhighlight>
{{out}}
<pre>$ patscc -O3 -DATS_MEMALLOC_GCBDW quicksort_task_for_lists.dats -lgc && ./a.out
62
62
all all all and any array be be
be both choose divide element elements elements elements
except first first greater in in into join
less must must of other partition partition partition
partition partitions partitions pivot pivot pivot pivot pivot
recursion second second sort sorted sorted than than
the the the the the the the the
the the to to two use</pre>
=== A quicksort working on linear linked lists ===
This program was derived from the quicksort for non-linear linked lists.
<syntaxhighlight lang="ats">(*------------------------------------------------------------------*)
(* Quicksort in ATS2, for linear lists. *)
(*------------------------------------------------------------------*)
#include "share/atspre_staload.hats"
#define NIL list_vt_nil ()
#define :: list_vt_cons
(*------------------------------------------------------------------*)
(* A simple quicksort working on linear linked lists, with first
element as pivot. This is meant as a demonstration, not as a
superior sort algorithm.
It is based on the "not-in-place" task pseudocode. *)
#define FIRST_IS_LESS_THAN_SECOND 1
#define FIRST_IS_EQUAL_TO_SECOND 2
#define FIRST_IS_GREATER_THAN_SECOND 3
typedef comparison_result =
[i : int | (i == FIRST_IS_LESS_THAN_SECOND ||
i == FIRST_IS_EQUAL_TO_SECOND ||
i == FIRST_IS_GREATER_THAN_SECOND)]
int i
extern fun {a : vt@ype}
list_vt_quicksort$comparison (x : !a, y : !a) :<> comparison_result
extern fun {a : vt@ype}
list_vt_quicksort {n : int}
(lst : list_vt (a, n)) :<!wrt> list_vt (a, n)
(* - - - - - - - - - - - - - - - - - - - - - - *)
implement {a}
list_vt_quicksort {n} (lst) =
let
fun
partition {n : nat}
.<n>. (* Proof of termination. *)
(lst : list_vt (a, n),
pivot : !a)
:<> [n1, n2, n3 : int | n1 + n2 + n3 == n]
@(list_vt (a, n1), list_vt (a, n2), list_vt (a, n3)) =
(* This implementation is *not* tail recursive. I may get a
scolding for using ATS to risk stack overflow! However, I
need more practice writing non-tail routines. :) Also, a lot
of programmers in other languages would do it this
way--especially if the lists are evaluated lazily. *)
case+ lst of
| ~ NIL => @(NIL, NIL, NIL)
| ~ head :: tail =>
let
val @(lt, eq, gt) = partition (tail, pivot)
prval () = lemma_list_vt_param lt
prval () = lemma_list_vt_param eq
prval () = lemma_list_vt_param gt
in
case+ list_vt_quicksort$comparison<a> (head, pivot) of
| FIRST_IS_LESS_THAN_SECOND => @(head :: lt, eq, gt)
| FIRST_IS_EQUAL_TO_SECOND => @(lt, head :: eq, gt)
| FIRST_IS_GREATER_THAN_SECOND => @(lt, eq, head :: gt)
end
fun
quicksort {n : nat}
.<n>. (* Proof of termination. *)
(lst : list_vt (a, n))
:<!wrt> list_vt (a, n) =
case+ lst of
| NIL => lst
| _ :: NIL => lst
| ~ head :: tail =>
let
(* We are careful here to run "partition" on "tail" rather
than "lst", so the termination metric will be provably
decreasing. (Really the compiler *forces* us to take such
care, or else to add !ntm to the effects.) *)
val pivot = head
prval () = lemma_list_vt_param tail
val @(lt, eq, gt) = partition {n - 1} (tail, pivot)
prval () = lemma_list_vt_param lt
prval () = lemma_list_vt_param eq
prval () = lemma_list_vt_param gt
val eq = pivot :: eq
and lt = quicksort lt
and gt = quicksort gt
in
list_vt_append (lt, list_vt_append (eq, gt))
end
prval () = lemma_list_vt_param lst
in
quicksort {n} lst
end
(*------------------------------------------------------------------*)
implement
list_vt_quicksort$comparison<Strptr1> (x, y) =
let
val i = compare (x, y)
in
if i < 0 then
FIRST_IS_LESS_THAN_SECOND
else if i = 0 then
FIRST_IS_EQUAL_TO_SECOND
else
FIRST_IS_GREATER_THAN_SECOND
end
implement
list_vt_map$fopr<string><Strptr1> (s) = string0_copy s
implement
list_vt_freelin$clear<Strptr1> (x) = strptr_free x
implement
main0 () =
let
val example_strings =
$list_vt
("choose", "any", "element", "of", "the", "array",
"to", "be", "the", "pivot",
"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",
"use", "recursion", "to", "sort", "both", "partitions",
"join", "the", "first", "sorted", "partition", "the",
"pivot", "and", "the", "second", "sorted", "partition")
val example_strptrs =
list_vt_map<string><Strptr1> (example_strings)
val sorted_strptrs = list_vt_quicksort<Strptr1> example_strptrs
fun
print_strptrs {n : nat} .<n>.
(strptrs : !list_vt (Strptr1, n),
i : int) : void =
case+ strptrs of
| NIL => if i <> 1 then println! () else ()
| @ head :: tail =>
begin
print! head;
if i = 8 then
begin
println! ();
print_strptrs (tail, 1)
end
else
begin
print! " ";
print_strptrs (tail, succ i)
end;
fold@ strptrs
end
in
println! (length example_strings);
println! (length sorted_strptrs);
print_strptrs (sorted_strptrs, 1);
list_vt_freelin<Strptr1> sorted_strptrs;
list_vt_free<string> example_strings
end
(*------------------------------------------------------------------*)</syntaxhighlight>
{{out}}
<pre>$ patscc -O3 -DATS_MEMALLOC_LIBC quicksort_task_for_list_vt.dats && ./a.out
62
62
all all all and any array be be
be both choose divide element elements elements elements
except first first greater in in into join
less must must of other partition partition partition
partition partitions partitions pivot pivot pivot pivot pivot
recursion second second sort sorted sorted than than
the the the the the the the the
the the to to two use</pre>
=== A quicksort working on arrays of non-linear elements ===
<syntaxhighlight lang="ats">(*------------------------------------------------------------------*)
(* Quicksort in ATS2, for arrays of non-linear values. *)
(*------------------------------------------------------------------*)
#include "share/atspre_staload.hats"
#define NIL list_nil ()
#define :: list_cons
(*------------------------------------------------------------------*)
(* A simple quicksort working on arrays of non-linear values, using
a programmer-selectible pivot.
It is based on the "in-place" task pseudocode. *)
extern fun {a : t@ype} (* A "less-than" predicate. *)
array_quicksort$lt (x : a, y : a) : bool
extern fun {a : t@ype}
array_quicksort$select_pivot {n : int}
{i, j : nat | i < j; j < n}
(arr : &array (a, n) >> _,
first : size_t i,
last : size_t j) : a
extern fun {a : t@ype}
array_quicksort {n : int}
(arr : &array (a, n) >> _,
n : size_t n) : void
(* - - - - - - - - - - - - - - - - - - - - - - *)
fn {a : t@ype}
swap {n : int}
{i, j : nat | i < n; j < n}
(arr : &array(a, n) >> _,
i : size_t i,
j : size_t j) : void =
{
val x = arr[i] and y = arr[j]
val () = (arr[i] := y) and () = (arr[j] := x)
}
implement {a}
array_quicksort {n} (arr, n) =
let
sortdef index = {i : nat | i < n}
typedef index (i : int) = [0 <= i; i < n] size_t i
typedef index = [i : index] index i
macdef lt = array_quicksort$lt<a>
fun
quicksort {i, j : index}
(arr : &array(a, n) >> _,
first : index i,
last : index j) : void =
if first < last then
{
val pivot : a =
array_quicksort$select_pivot<a> (arr, first, last)
fun
search_rightwards (arr : &array (a, n),
left : index) : index =
if arr[left] \lt pivot then
let
val () = assertloc (succ left <> n)
in
search_rightwards (arr, succ left)
end
else
left
fun
search_leftwards (arr : &array (a, n),
left : index,
right : index) : index =
if right < left then
right
else if pivot \lt arr[right] then
let
val () = assertloc (right <> i2sz 0)
in
search_leftwards (arr, left, pred right)
end
else
right
fun
partition (arr : &array (a, n) >> _,
left0 : index,
right0 : index) : @(index, index) =
let
val left = search_rightwards (arr, left0)
val right = search_leftwards (arr, left, right0)
in
if left <= right then
let
val () = assertloc (succ left <> n)
and () = assertloc (right <> i2sz 0)
in
swap (arr, left, right);
partition (arr, succ left, pred right)
end
else
@(left, right)
end
val @(left, right) = partition (arr, first, last)
val () = quicksort (arr, first, right)
and () = quicksort (arr, left, last)
}
in
if i2sz 2 <= n then
quicksort {0, n - 1} (arr, i2sz 0, pred n)
end
(*------------------------------------------------------------------*)
val example_strings =
$list ("choose", "any", "element", "of", "the", "array",
"to", "be", "the", "pivot",
"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",
"use", "recursion", "to", "sort", "both", "partitions",
"join", "the", "first", "sorted", "partition", "the",
"pivot", "and", "the", "second", "sorted", "partition")
implement
array_quicksort$lt<string> (x, y) =
strcmp (x, y) < 0
implement
array_quicksort$select_pivot<string> {n} (arr, first, last) =
(* Median of three, with swapping around of elements during pivot
selection. See https://archive.ph/oYENx *)
let
macdef lt = array_quicksort$lt<string>
val middle = first + ((last - first) / i2sz 2)
val xfirst = arr[first]
and xmiddle = arr[middle]
and xlast = arr[last]
in
if (xmiddle \lt xfirst) xor (xlast \lt xfirst) then
begin
swap (arr, first, middle);
if xlast \lt xmiddle then
swap (arr, first, last);
xfirst
end
else if (xmiddle \lt xfirst) xor (xmiddle \lt xlast) then
begin
if xlast \lt xfirst then
swap (arr, first, last);
xmiddle
end
else
begin
swap (arr, middle, last);
if xmiddle \lt xfirst then
swap (arr, first, last);
xlast
end
end
implement
main0 () =
let
prval () = lemma_list_param example_strings
val n = length example_strings
val @(pf, pfgc | p) = array_ptr_alloc<string> (i2sz n)
macdef arr = !p
val () = array_initize_list (arr, n, example_strings)
val () = array_quicksort<string> (arr, i2sz n)
val sorted_strings = list_vt2t (array2list (arr, i2sz n))
val () = array_ptr_free (pf, pfgc | p)
fun
print_strings {n : nat} .<n>.
(strings : list (string, n),
i : int) : void =
case+ strings of
| NIL => if i <> 1 then println! () else ()
| head :: tail =>
begin
print! head;
if i = 8 then
begin
println! ();
print_strings (tail, 1)
end
else
begin
print! " ";
print_strings (tail, succ i)
end
end
in
println! (length example_strings);
println! (length sorted_strings);
print_strings (sorted_strings, 1)
end
(*------------------------------------------------------------------*)</syntaxhighlight>
{{out}}
<pre>$ patscc -O3 -DATS_MEMALLOC_GCBDW quicksort_task_for_arrays.dats -lgc && ./a.out
62
62
all all all and any array be be
be both choose divide element elements elements elements
except first first greater in in into join
less must must of other partition partition partition
partition partitions partitions pivot pivot pivot pivot pivot
recursion second second sort sorted sorted than than
the the the the the the the the
the the to to two use</pre>
=== A quicksort working on arrays of linear elements ===
The quicksort for arrays of non-linear elements ''makes a copy'' of the pivot value, and compares this copy with array elements ''by value''. Here, however, the array elements are ''linear'' values. They cannot be copied, unless a special "copy" procedure is provided. We do not want to require such a procedure. So we must do something else.
What we do is move the pivot to the last element of the array, by safely swapping it with the original last element. We partition the array to the left of the last element, comparing array elements with the pivot (that is, the last element) ''by reference''.
<syntaxhighlight lang="ats">(*------------------------------------------------------------------*)
(* Quicksort in ATS2, for arrays of (possibly) linear values. *)
(*------------------------------------------------------------------*)
#include "share/atspre_staload.hats"
#define NIL list_vt_nil ()
#define :: list_vt_cons
(*------------------------------------------------------------------*)
(* A simple quicksort working on arrays of non-linear values, using
a programmer-selectible pivot.
It is based on the "in-place" task pseudocode. *)
extern fun {a : vt@ype} (* A "less-than" predicate. *)
array_quicksort$lt {px, py : addr}
(pfx : !(a @ px),
pfy : !(a @ py) |
px : ptr px,
py : ptr py) : bool
extern fun {a : vt@ype}
array_quicksort$select_pivot_index {n : int}
{i, j : nat | i < j; j < n}
(arr : &array (a, n),
first : size_t i,
last : size_t j)
: [k : int | i <= k; k <= j] size_t k
extern fun {a : vt@ype}
array_quicksort {n : int}
(arr : &array (a, n) >> _,
n : size_t n) : void
(* - - - - - - - - - - - - - - - - - - - - - - *)
prfn (* Subdivide an array view into three views. *)
array_v_subdivide3 {a : vt@ype} {p : addr} {n1, n2, n3 : nat}
(pf : @[a][n1 + n2 + n3] @ p)
:<prf> @(@[a][n1] @ p,
@[a][n2] @ (p + n1 * sizeof a),
@[a][n3] @ (p + (n1 + n2) * sizeof a)) =
let
prval (pf1, pf23) =
array_v_split {a} {p} {n1 + n2 + n3} {n1} pf
prval (pf2, pf3) =
array_v_split {a} {p + n1 * sizeof a} {n2 + n3} {n2} pf23
in
@(pf1, pf2, pf3)
end
prfn (* Join three contiguous array views into one view. *)
array_v_join3 {a : vt@ype} {p : addr} {n1, n2, n3 : nat}
(pf1 : @[a][n1] @ p,
pf2 : @[a][n2] @ (p + n1 * sizeof a),
pf3 : @[a][n3] @ (p + (n1 + n2) * sizeof a))
:<prf> @[a][n1 + n2 + n3] @ p =
let
prval pf23 =
array_v_unsplit {a} {p + n1 * sizeof a} {n2, n3} (pf2, pf3)
prval pf = array_v_unsplit {a} {p} {n1, n2 + n3} (pf1, pf23)
in
pf
end
fn {a : vt@ype} (* Safely swap two elements of an array. *)
swap_elems_1 {n : int}
{i, j : nat | i <= j; j < n}
{p : addr}
(pfarr : !array_v(a, p, n) >> _ |
p : ptr p,
i : size_t i,
j : size_t j) : void =
let
fn {a : vt@ype}
swap {n : int}
{i, j : nat | i < j; j < n}
{p : addr}
(pfarr : !array_v(a, p, n) >> _ |
p : ptr p,
i : size_t i,
j : size_t j) : void =
{
(* Safely swapping linear elements requires that views of
those elements be split off from the rest of the
array. Why? Because those elements will temporarily be in
an uninitialized state. (Actually they will be "?!", but
the difference is unimportant here.)
Remember, a linear value is consumed by using it.
The view for the whole array can be reassembled only after
new values have been stored, making the entire array once
again initialized. *)
prval @(pf1, pf2, pf3) =
array_v_subdivide3 {a} {p} {i, j - i, n - j} pfarr
prval @(pfi, pf2_) = array_v_uncons pf2
prval @(pfj, pf3_) = array_v_uncons pf3
val pi = ptr_add<a> (p, i)
and pj = ptr_add<a> (p, j)
val xi = ptr_get<a> (pfi | pi)
and xj = ptr_get<a> (pfj | pj)
val () = ptr_set<a> (pfi | pi, xj)
and () = ptr_set<a> (pfj | pj, xi)
prval pf2 = array_v_cons (pfi, pf2_)
prval pf3 = array_v_cons (pfj, pf3_)
prval () = pfarr := array_v_join3 (pf1, pf2, pf3)
}
in
if i < j then
swap {n} {i, j} {p} (pfarr | p, i, j)
else
() (* i = j must be handled specially, due to linear typing.*)
end
fn {a : vt@ype} (* Safely swap two elements of an array. *)
swap_elems_2 {n : int}
{i, j : nat | i <= j; j < n}
(arr : &array(a, n) >> _,
i : size_t i,
j : size_t j) : void =
swap_elems_1 (view@ arr | addr@ arr, i, j)
overload swap_elems with swap_elems_1
overload swap_elems with swap_elems_2
overload swap with swap_elems
fn {a : vt@ype} (* Safely compare two elements of an array. *)
lt_elems_1 {n : int}
{i, j : nat | i < n; j < n}
{p : addr}
(pfarr : !array_v(a, p, n) |
p : ptr p,
i : size_t i,
j : size_t j) : bool =
let
fn
compare {n : int}
{i, j : nat | i < j; j < n}
{p : addr}
(pfarr : !array_v(a, p, n) |
p : ptr p,
i : size_t i,
j : size_t j,
gt : bool) : bool =
let
prval @(pf1, pf2, pf3) =
array_v_subdivide3 {a} {p} {i, j - i, n - j} pfarr
prval @(pfi, pf2_) = array_v_uncons pf2
prval @(pfj, pf3_) = array_v_uncons pf3
val pi = ptr_add<a> (p, i)
and pj = ptr_add<a> (p, j)
val retval =
if gt then
array_quicksort$lt<a> (pfj, pfi | pj, pi)
else
array_quicksort$lt<a> (pfi, pfj | pi, pj)
prval pf2 = array_v_cons (pfi, pf2_)
prval pf3 = array_v_cons (pfj, pf3_)
prval () = pfarr := array_v_join3 (pf1, pf2, pf3)
in
retval
end
in
if i < j then
compare {n} {i, j} {p} (pfarr | p, i, j, false)
else if j < i then
compare {n} {j, i} {p} (pfarr | p, j, i, true)
else
false
end
fn {a : vt@ype} (* Safely compare two elements of an array. *)
lt_elems_2 {n : int}
{i, j : nat | i < n; j < n}
(arr : &array (a, n),
i : size_t i,
j : size_t j) : bool =
lt_elems_1 (view@ arr | addr@ arr, i, j)
overload lt_elems with lt_elems_1
overload lt_elems with lt_elems_2
implement {a}
array_quicksort {n} (arr, n) =
let
sortdef index = {i : nat | i < n}
typedef index (i : int) = [0 <= i; i < n] size_t i
typedef index = [i : index] index i
macdef lt = array_quicksort$lt<a>
fun
quicksort {i, j : index}
(arr : &array(a, n) >> _,
first : index i,
last : index j) : void =
if first < last then
{
val pivot =
array_quicksort$select_pivot_index<a> (arr, first, last)
(* Swap the pivot with the last element. *)
val () = swap (arr, pivot, last)
val pivot = last
fun
search_rightwards (arr : &array (a, n),
left : index) : index =
if lt_elems<a> (arr, left, pivot) then
let
val () = assertloc (succ left <> n)
in
search_rightwards (arr, succ left)
end
else
left
fun
search_leftwards (arr : &array (a, n),
left : index,
right : index) : index =
if right < left then
right
else if lt_elems<a> (arr, pivot, right) then
let
val () = assertloc (right <> i2sz 0)
in
search_leftwards (arr, left, pred right)
end
else
right
fun
partition (arr : &array (a, n) >> _,
left0 : index,
right0 : index) : @(index, index) =
let
val left = search_rightwards (arr, left0)
val right = search_leftwards (arr, left, right0)
in
if left <= right then
let
val () = assertloc (succ left <> n)
and () = assertloc (right <> i2sz 0)
in
swap (arr, left, right);
partition (arr, succ left, pred right)
end
else
@(left, right)
end
val @(left, right) = partition (arr, first, pred last)
val () = quicksort (arr, first, right)
and () = quicksort (arr, left, last)
}
in
if i2sz 2 <= n then
quicksort {0, n - 1} (arr, i2sz 0, pred n)
end
(*------------------------------------------------------------------*)
implement
array_quicksort$lt<Strptr1> (pfx, pfy | px, py) =
compare (!px, !py) < 0
implement
array_quicksort$select_pivot_index<Strptr1> {n} (arr, first, last) =
(* Median of three. *)
let
val middle = first + ((last - first) / i2sz 2)
in
if lt_elems<Strptr1> (arr, middle, first)
xor lt_elems<Strptr1> (arr, last, first) then
first
else if lt_elems<Strptr1> (arr, middle, first)
xor lt_elems<Strptr1> (arr, middle, last) then
middle
else
last
end
implement
list_vt_map$fopr<string><Strptr1> (s) = string0_copy s
implement
list_vt_freelin$clear<Strptr1> (x) = strptr_free x
implement
main0 () =
let
val example_strings =
$list_vt
("choose", "any", "element", "of", "the", "array",
"to", "be", "the", "pivot",
"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",
"use", "recursion", "to", "sort", "both", "partitions",
"join", "the", "first", "sorted", "partition", "the",
"pivot", "and", "the", "second", "sorted", "partition")
val example_strptrs =
list_vt_map<string><Strptr1> (example_strings)
prval () = lemma_list_vt_param example_strptrs
val n = length example_strptrs
val @(pf, pfgc | p) = array_ptr_alloc<Strptr1> (i2sz n)
macdef arr = !p
val () = array_initize_list_vt<Strptr1> (arr, n, example_strptrs)
val () = array_quicksort<Strptr1> (arr, i2sz n)
val sorted_strptrs = array2list (arr, i2sz n)
fun
print_strptrs {n : nat} .<n>.
(strptrs : !list_vt (Strptr1, n),
i : int) : void =
case+ strptrs of
| NIL => if i <> 1 then println! () else ()
| @ head :: tail =>
begin
print! head;
if i = 8 then
begin
println! ();
print_strptrs (tail, 1)
end
else
begin
print! " ";
print_strptrs (tail, succ i)
end;
fold@ strptrs
end
in
println! (length example_strings);
println! (length sorted_strptrs);
print_strptrs (sorted_strptrs, 1);
list_vt_freelin<Strptr1> sorted_strptrs;
array_ptr_free (pf, pfgc | p);
list_vt_free<string> example_strings
end
(*------------------------------------------------------------------*)</syntaxhighlight>
{{out}}
<pre>$ patscc -O3 -DATS_MEMALLOC_LIBC quicksort_task_for_arrays_2.dats
62
62
all all all and any array be be
be both choose divide element elements elements elements
except first first greater in in into join
less must must of other partition partition partition
partition partitions partitions pivot pivot pivot pivot pivot
recursion second second sort sorted sorted than than
the the the the the the the the
the the to to two use</pre>
=== A ''stable'' quicksort working on linear lists ===
See the code at [[Quickselect_algorithm#Quickselect_working_on_linear_lists|the quickselect task]].
{{out}}
<pre>$ patscc -O3 -DATS_MEMALLOC_LIBC quickselect_task_for_list_vt.dats && ./a.out quicksort
stable sort by first character:
duck, deer, dolphin, elephant, earwig, giraffe, pronghorn, wildebeest, woodlouse, whip-poor-will</pre>
=={{header|AutoHotkey}}==
Translated from the python example:
<syntaxhighlight lang="autohotkey">a := [4, 65, 2, -31, 0, 99, 83, 782, 7]
for k, v in QuickSort(a)
Out .= "," v
MsgBox, % SubStr(Out, 2)
return
QuickSort(a)
{
if (a.MaxIndex() <= 1)
return a
Less := [], Same := [], More := []
Pivot := a[1]
for k, v in a
{
if (v < Pivot)
less.Insert(v)
else if (v > Pivot)
more.Insert(v)
else
same.Insert(v)
}
Less := QuickSort(Less)
Out := QuickSort(More)
if (Same.MaxIndex())
Out.Insert(1, Same*) ; insert all values of same at index 1
if (Less.MaxIndex())
Out.Insert(1, Less*) ; insert all values of less at index 1
return Out
}</syntaxhighlight>
Old implementation for AutoHotkey 1.0:
<syntaxhighlight lang="autohotkey">MsgBox % quicksort("8,4,9,2,1")
quicksort(list)
{
StringSplit, list, list, `,
If (list0 <= 1)
Return list
pivot := list1
Loop, Parse, list, `,
{
If (A_LoopField < pivot)
less = %less%,%A_LoopField%
Else If (A_LoopField > pivot)
more = %more%,%A_LoopField%
Else
pivotlist = %pivotlist%,%A_LoopField%
}
StringTrimLeft, less, less, 1
StringTrimLeft, more, more, 1
StringTrimLeft, pivotList, pivotList, 1
less := quicksort(less)
more := quicksort(more)
Return less . pivotList . more
}</syntaxhighlight>
=={{header|AWK}}==
<
# the following qsort implementation extracted from:
#
Line 395 ⟶ 2,531:
}
}
</syntaxhighlight>
=={{header|
==={{header|ANSI BASIC}}===
{{works with|Decimal BASIC}}
<syntaxhighlight lang="basic">
100 REM Sorting algorithms/Quicksort
110 DECLARE EXTERNAL SUB QuickSort
120 DIM Arr(0 TO 19)
130 LET A = LBOUND(Arr)
140 LET B = UBOUND(Arr)
150 RANDOMIZE
160 FOR I = A TO B
170 LET Arr(I) = ROUND(INT(RND * 99))
180 NEXT I
190 PRINT "Unsorted:"
200 FOR I = A TO B
210 PRINT USING "## ": Arr(I);
220 NEXT I
230 PRINT
240 PRINT "Sorted:"
250 CALL QuickSort(Arr, A, B)
260 FOR I = A TO B
270 PRINT USING "## ": Arr(I);
280 NEXT I
290 PRINT
300 END
310 REM **
320 EXTERNAL SUB QuickSort (Arr(), L, R)
330 LET LIndex = L
340 LET RIndex = R
350 IF R > L THEN
360 LET Pivot = INT((L + R) / 2)
370 DO WHILE (LIndex <= Pivot) AND (RIndex >= Pivot)
380 DO WHILE (Arr(LIndex) < Arr(Pivot)) AND (LIndex <= Pivot)
390 LET LIndex = LIndex + 1
400 LOOP
410 DO WHILE (Arr(RIndex) > Arr(Pivot)) AND (RIndex >= Pivot)
420 LET RIndex = RIndex - 1
430 LOOP
440 LET Temp = Arr(LIndex)
450 LET Arr(LIndex) = Arr(RIndex)
460 LET Arr(RIndex) = Temp
470 LET LIndex = LIndex + 1
480 LET RIndex = RIndex - 1
490 IF (LIndex - 1) = Pivot THEN
500 LET RIndex = RIndex + 1
510 LET Pivot = RIndex
520 ELSEIF (RIndex + 1) = Pivot THEN
530 LET LIndex = LIndex - 1
540 LET Pivot = LIndex
550 END IF
560 LOOP
570 CALL QuickSort (Arr, L, Pivot - 1)
580 CALL QuickSort (Arr, Pivot + 1, R)
590 END IF
600 END SUB
</syntaxhighlight>
{{out}} (example)
<pre>
Unsorted:
17 79 23 91 28 91 29 58 47 59 8 35 93 23 34 28 35 31 7 25
Sorted:
7 8 17 23 23 25 28 28 29 31 34 35 35 47 58 59 79 91 91 93
</pre>
==={{header|BBC BASIC}}===
<syntaxhighlight lang="bbcbasic"> DIM test(9)
test() = 4, 65, 2, -31, 0, 99, 2, 83, 782, 1
PROCquicksort(test(), 0, 10)
FOR i% = 0 TO 9
PRINT test(i%) ;
NEXT
PRINT
DEF PROCquicksort(a(), s%, n%)
IF n% < 2 THEN ENDPROC
l% = s%
r% = t%
p = a((l% + r%) DIV 2)
REPEAT
WHILE a(l%) < p l% += 1 : ENDWHILE
WHILE a(r%) > p r% -= 1 : ENDWHILE
IF l% <= r% THEN
SWAP a(l%), a(r%)
l% += 1
r% -= 1
ENDIF
UNTIL l% > r%
IF s% < r% PROCquicksort(a(), s%, r% - s% + 1)
IF l% < t% PROCquicksort(a(), l%, t% - l% + 1 )
ENDPROC</syntaxhighlight>
{{out}}
<pre>
-31 0 1 2 2 4 65 83 99 782
</pre>
==={{header|
{{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|Craft Basic}}===
<syntaxhighlight lang="basic">define size = 10, point = 0, top = 0
define high = 0, low = 0, pivot = 0
dim list[size]
dim stack[size]
gosub fill
gosub sort
gosub show
end
sub fill
for i = 0 to size - 1
let list[i] = int(rnd * 100)
next i
return
sub sort
let low = 0
let high = size - 1
let top = -1
let top = top + 1
let stack[top] = low
let top = top + 1
let stack[top] = high
do
if top < 0 then
break
endif
let high = stack[top]
let top = top - 1
let low = stack[top]
let top = top - 1
let i = low - 1
for j = low to high - 1
if list[j] <= list[high] then
let i = i + 1
let t = list[i]
let list[i] = list[j]
let list[j] = t
endif
next j
let point = i + 1
let t = list[point]
let list[point] = list[high]
let list[high] = t
let pivot = i + 1
if pivot - 1 > low then
let top = top + 1
let stack[top] = low
let top = top + 1
let stack[top] = pivot - 1
endif
if pivot + 1 < high then
let top = top + 1
let stack[top] = pivot + 1
let top = top + 1
let stack[top] = high
endif
wait
loop top >= 0
return
sub show
for i = 0 to size - 1
print i, ": ", list[i]
next i
return</syntaxhighlight>
==={{header|FreeBASIC}}===
<syntaxhighlight lang="freebasic">' version 23-10-2016
' compile with: fbc -s console
' sort from lower bound to the highter bound
' array's can have subscript range from -2147483648 to +2147483647
Sub quicksort(qs() As Long, l As Long, r As Long)
Dim As ULong size = r - l +1
If size < 2 Then Exit Sub
Dim As Long i = l, j = r
Dim As Long pivot = qs(l + size \ 2)
Do
While qs(i) < pivot
i += 1
Wend
While pivot < qs(j)
j -= 1
Wend
If i <= j Then
Swap qs(i), qs(j)
i += 1
j -= 1
End If
Loop Until i > j
If l < j Then quicksort(qs(), l, j)
If i < r Then quicksort(qs(), i, r)
End Sub
' ------=< MAIN >=------
Dim As Long i, array(-7 To 7)
Dim As Long a = LBound(array), b = UBound(array)
Randomize Timer
For i = a To b : array(i) = i : Next
For i = a To b ' little shuffle
Swap array(i), array(Int(Rnd * (b - a +1)) + a)
Next
Print "unsorted ";
For i = a To b : Print Using "####"; array(i); : Next : Print
quicksort(array(), LBound(array), UBound(array))
Print " sorted ";
For i = a To b : Print Using "####"; array(i); : Next : Print
' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End</syntaxhighlight>
{{out}}
<pre>unsorted -5 -6 -1 0 2 -4 -7 6 -2 -3 4 7 5 1 3
sorted -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7</pre>
==={{header|FutureBasic}}===
<syntaxhighlight lang="futurebasic">
include "NSLog.incl"
local fn Quicksort( qs as CFMutableArrayRef, l as NSInteger, r as NSInteger )
UInt64 size = r - l + 1
if size < 2 then exit fn
NSinteger i = l, j = r
NSinteger pivot = fn NumberIntegerValue( qs[l+size / 2] )
do
while fn NumberIntegerValue( qs[i] ) < pivot
i++
wend
while pivot < fn NumberIntegerValue( qs[j] )
j--
wend
if ( i <= j )
MutableArrayExchangeObjects( qs, i, j )
i++
j--
end if
until i > j
if l < j then fn Quicksort( qs, l, j )
if i < r then fn Quicksort( qs, i, r )
end fn
CFMutableArrayRef qs
CFArrayRef unsorted
NSUInteger i, amount
qs = fn MutableArrayWithCapacity(0)
for i = 0 to 25
if i mod 2 == 0 then amount = 100 else amount = 10000
MutableArrayInsertObjectAtIndex( qs, fn NumberWithInteger( rnd(amount) ), i )
next
unsorted = fn ArrayWithArray( qs )
fn QuickSort( qs, 0, len(qs) - 1 )
NSLog( @"\n-----------------\nUnsorted : Sorted\n-----------------" )
for i = 0 to 25
NSLog( @"%8ld : %-8ld", fn NumberIntegerValue( unsorted[i] ), fn NumberIntegerValue( qs[i] ) )
next
randomize
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
-----------------
Unsorted : Sorted
-----------------
97 : 5
6168 : 30
61 : 34
8847 : 40
55 : 46
2570 : 49
40 : 55
4676 : 61
94 : 62
693 : 67
62 : 79
3419 : 94
30 : 97
936 : 693
5 : 733
9910 : 936
67 : 1395
8460 : 1796
79 : 2570
9352 : 3419
49 : 4676
1395 : 6168
34 : 8460
733 : 8847
46 : 9352
1796 : 9910
</pre>
==={{header|IS-BASIC}}===
<syntaxhighlight lang="is-basic">100 PROGRAM "QuickSrt.bas"
110 RANDOMIZE
120 NUMERIC A(5 TO 19)
130 CALL INIT(A)
140 CALL WRITE(A)
150 CALL QSORT(LBOUND(A),UBOUND(A))
160 CALL WRITE(A)
170 DEF INIT(REF A)
180 FOR I=LBOUND(A) TO UBOUND(A)
190 LET A(I)=RND(98)+1
200 NEXT
210 END DEF
220 DEF WRITE(REF A)
230 FOR I=LBOUND(A) TO UBOUND(A)
240 PRINT A(I);
250 NEXT
260 PRINT
270 END DEF
280 DEF QSORT(AH,FH)
290 NUMERIC E
300 LET E=AH:LET U=FH:LET K=A(E)
310 DO UNTIL E=U
320 DO UNTIL E=U OR A(U)<K
330 LET U=U-1
340 LOOP
350 IF E<U THEN
360 LET A(E)=A(U):LET E=E+1
370 DO UNTIL E=U OR A(E)>K
380 LET E=E+1
390 LOOP
400 IF E<U THEN LET A(U)=A(E):LET U=U-1
410 END IF
420 LOOP
430 LET A(E)=K
440 IF AH<E-1 THEN CALL QSORT(AH,E-1)
450 IF E+1<FH THEN CALL QSORT(E+1,FH)
460 END DEF</syntaxhighlight>
==={{header|PureBasic}}===
<syntaxhighlight lang="purebasic">Procedure qSort(Array a(1), firstIndex, lastIndex)
Protected low, high, pivotValue
low = firstIndex
high = lastIndex
pivotValue = a((firstIndex + lastIndex) / 2)
Repeat
While a(low) < pivotValue
low + 1
Wend
While a(high) > pivotValue
high - 1
Wend
If low <= high
Swap a(low), a(high)
low + 1
high - 1
EndIf
Until low > high
If firstIndex < high
qSort(a(), firstIndex, high)
EndIf
If low < lastIndex
qSort(a(), low, lastIndex)
EndIf
EndProcedure
Procedure quickSort(Array a(1))
qSort(a(),0,ArraySize(a()))
EndProcedure</syntaxhighlight>
==={{header|QB64}}===
<syntaxhighlight lang="qb64">
' Written by Sanmayce, 2021-Oct-29
' The indexes are signed, but the elements are unsigned.
_Define A-Z As _INTEGER64
Sub Quicksort_QB64 (QWORDS~&&())
Left = LBound(QWORDS~&&)
Right = UBound(QWORDS~&&)
LeftMargin = Left
ReDim Stack&&(Left To Right)
StackPtr = 0
StackPtr = StackPtr + 1
Stack&&(StackPtr + LeftMargin) = Left
StackPtr = StackPtr + 1
Stack&&(StackPtr + LeftMargin) = Right
Do 'Until StackPtr = 0
Right = Stack&&(StackPtr + LeftMargin)
StackPtr = StackPtr - 1
Left = Stack&&(StackPtr + LeftMargin)
StackPtr = StackPtr - 1
Do 'Until Left >= Right
Pivot~&& = QWORDS~&&((Left + Right) \ 2)
Indx = Left
Jndx = Right
Do
Do While (QWORDS~&&(Indx) < Pivot~&&)
Indx = Indx + 1
Loop
Do While (QWORDS~&&(Jndx) > Pivot~&&)
Jndx = Jndx - 1
Loop
If Indx <= Jndx Then
If Indx < Jndx Then Swap QWORDS~&&(Indx), QWORDS~&&(Jndx)
Indx = Indx + 1
Jndx = Jndx - 1
End If
Loop While Indx <= Jndx
If Indx < Right Then
StackPtr = StackPtr + 1
Stack&&(StackPtr + LeftMargin) = Indx
StackPtr = StackPtr + 1
Stack&&(StackPtr + LeftMargin) = Right
End If
Right = Jndx
Loop Until Left >= Right
Loop Until StackPtr = 0
End Sub</syntaxhighlight>
==={{header|QuickBASIC}}===
{{works with|FreeBASIC}}
{{works with|PowerBASIC for DOS}}
Line 432 ⟶ 3,058:
This is specifically for <code>INTEGER</code>s, but can be modified for any data type by changing <code>arr()</code>'s type.
<
DIM q(99) AS INTEGER
Line 481 ⟶ 3,107:
quicksort arr(), pivot + 1, rightN
END IF
END SUB</
==={{header|
<syntaxhighlight lang="runbasic">' -------------------------------
' quick sort
' -------------------------------
size = 50
dim s(size) ' array to sort
for i = 1 to size ' fill it with some random numbers
s(i) = rnd(0) * 100
next i
lft = 1
rht = size
[qSort]
pivot
while lft <
while (s(rht) >= pivot)
if lft <> rht then
s(lft)
lft
end
while (s(lft) <= pivot) and (lft
if lft <> rht
end if
wend
s(lft) = pivot
pivot = lft
lft = lftHold
rht = rhtHold
if lft < pivot then
rht = pivot - 1
goto [qSort]
end if
if rht > pivot then
lft = pivot + 1
goto [qSort]
end if
for i = 1 to size
print i;"-->";s(i)
next i</syntaxhighlight>
==={{header|True BASIC}}===
<syntaxhighlight lang="qbasic">SUB quicksort (arr(), l, r)
LET lidx = round(l)
LET ridx = round(r)
IF (r-l) > 0 THEN
LET pivot = round((l+r)/2)
DO WHILE (lidx <= pivot) AND (ridx >= pivot)
DO WHILE (arr(lidx) < arr(pivot)) AND (lidx <= pivot)
LET lidx = lidx+1
LOOP
DO WHILE (arr(ridx) > arr(pivot)) AND (ridx >= pivot)
LET ridx = ridx-1
LOOP
LET temp = arr(lidx)
LET arr(lidx) = arr(ridx)
LET arr(ridx) = temp
LET lidx = lidx+1
LET ridx = ridx-1
IF (lidx-1) = pivot THEN
LET ridx = ridx+1
LET pivot = ridx
ELSEIF (ridx+1) = pivot THEN
LET lidx = lidx-1
LET pivot = lidx
END IF
LOOP
CALL quicksort (arr(), l, pivot-1)
CALL quicksort (arr(), pivot+1, r)
END IF
END SUB
DIM arr(15)
LET a = round(LBOUND(arr))
LET b = round(UBOUND(arr))
RANDOMIZE
FOR n = a TO b
LET arr(n) = round(INT(RND*99))
NEXT n
PRINT "unsort ";
FOR n = a TO b
PRINT arr(n); " ";
NEXT n
PRINT
PRINT " sort ";
CALL quicksort (arr(), a, b)
FOR n = a TO b
PRINT arr(n); " ";
NEXT n
END</syntaxhighlight>
==={{header|uBasic/4tH}}===
<syntaxhighlight lang="text">PRINT "Quick sort:"
n = FUNC (_InitArray)
PROC _ShowArray (n)
PROC _Quicksort (n)
PROC _ShowArray (n)
PRINT
END
_InnerQuick PARAM(2)
LOCAL(4)
IF b@ < 2 THEN RETURN
f@ = a@ + b@ - 1
c@ = a@
e@ = f@
d@ = @((c@ + e@) / 2)
DO
DO WHILE @(c@) < d@
c@ = c@ + 1
LOOP
DO WHILE @(e@) > d@
e@ = e@ - 1
LOOP
IF c@ - 1 < e@ THEN
PROC _Swap (c@, e@)
c@ = c@ + 1
e@ = e@ - 1
ENDIF
UNTIL c@ > e@
LOOP
IF a@ < e@ THEN PROC _InnerQuick (a@, e@ - a@ + 1)
IF c@ < f@ THEN PROC _InnerQuick (c@, f@ - c@ + 1)
RETURN
_Quicksort PARAM(1) ' Quick sort
PROC _InnerQuick (0, a@)
RETURN
_Swap PARAM(2) ' Swap two array elements
PUSH @(a@)
@(a@) = @(b@)
@(b@) = POP()
RETURN
_InitArray ' Init example array
PUSH 4, 65, 2, -31, 0, 99, 2, 83, 782, 1
FOR i = 0 TO 9
@(i) = POP()
NEXT
RETURN (i)
_ShowArray PARAM (1) ' Show array subroutine
FOR i = 0 TO a@-1
PRINT @(i),
NEXT
PRINT
RETURN</syntaxhighlight>
==={{header|VBA}}===
This is the "simple" quicksort, using temporary arrays.
<syntaxhighlight lang="vb">Public Sub Quick(a() As Variant, last As Integer)
' quicksort a Variant array (1-based, numbers or strings)
Dim aLess() As Variant
Dim aEq() As Variant
Dim aGreater() As Variant
Dim pivot As Variant
Dim naLess As Integer
Dim naEq As Integer
Dim naGreater As Integer
If last > 1 Then
'choose pivot in the middle of the array
pivot = a(Int((last + 1) / 2))
'construct arrays
naLess = 0
naEq = 0
naGreater = 0
For Each el In a()
If el > pivot Then
naGreater = naGreater + 1
ReDim Preserve aGreater(1 To naGreater)
aGreater(naGreater) = el
ElseIf el < pivot Then
naLess = naLess + 1
ReDim Preserve aLess(1 To naLess)
aLess(naLess) = el
Else
naEq = naEq + 1
ReDim Preserve aEq(1 To naEq)
aEq(naEq) = el
End If
Next
'sort arrays "less" and "greater"
Quick aLess(), naLess
Quick aGreater(), naGreater
'concatenate
P = 1
For i = 1 To naLess
a(P) = aLess(i): P = P + 1
Next
For i = 1 To naEq
a(P) = aEq(i): P = P + 1
Next
For i = 1 To naGreater
a(P) = aGreater(i): P = P + 1
Next
End If
End Sub
Public Sub QuicksortTest()
Dim a(1 To 26) As Variant
'populate a with numbers in descending order, then sort
For i = 1 To 26: a(i) = 26 - i: Next
Quick a(), 26
For i = 1 To 26: Debug.Print a(i);: Next
Debug.Print
'now populate a with strings in descending order, then sort
For i = 1 To 26: a(i) = Chr$(Asc("z") + 1 - i) & "-stuff": Next
Quick a(), 26
For i = 1 To 26: Debug.Print a(i); " ";: Next
Debug.Print
End Sub</syntaxhighlight>
{{out}}
<pre>quicksorttest
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
a-stuff b-stuff c-stuff d-stuff e-stuff f-stuff g-stuff h-stuff i-stuff j-stuff k-stuff l-stuff m-stuff n-stuff o-stuff p-stuff q-stuff r-stuff s-stuff t-stuff u-stuff v-stuff w-stuff x-stuff y-stuff z-stuff </pre>
Note: the "quicksort in place"
==={{header|VBScript}}===
{{trans|BBC BASIC}}
<syntaxhighlight lang="vb">Function quicksort(arr,s,n)
If n < 2 Then
Exit Function
End If
t = s + n - 1
l = s
r = t
p = arr(Int((l + r)/2))
Do Until l > r
Do While arr(l) < p
l = l + 1
Loop
Do While arr(r) > p
r = r -1
Loop
If l <= r Then
tmp = arr(l)
arr(l) = arr(r)
arr(r) = tmp
l = l + 1
r = r - 1
End If
Loop
If s < r Then
Call quicksort(arr,s,r-s+1)
End If
If l < t Then
Call quicksort(arr,l,t-l+1)
End If
quicksort = arr
End Function
myarray=Array(9,8,7,6,5,5,4,3,2,1,0,-1)
m = quicksort(myarray,0,12)
WScript.Echo Join(m,",")</syntaxhighlight>
{{out}}
<pre>-1,0,1,2,3,4,5,5,6,7,8,9</pre>
==={{header|Visual Basic}}===
{{works with|Visual Basic|5}}
{{works with|Visual Basic|6}}
QuickSort without swapping
<syntaxhighlight lang="vb">Sub QuickSort(arr() As Integer, ByVal f As Integer, ByVal l As Integer)
i = f 'First
j = l 'Last
Key = arr(i) 'Pivot
Do While i < j
Do While i < j And Key < arr(j)
j = j - 1
Loop
If i < j Then arr(i) = arr(j): i = i + 1
Do While i < j And Key > arr(i)
i = i + 1
Loop
If i < j Then arr(j) = arr(i): j = j - 1
Loop
arr(i) = Key
If i - 1 > f Then QuickSort arr(), f, i - 1
If j + 1 < l Then QuickSort arr(), j + 1, l
End Sub</syntaxhighlight>
==={{header|XBasic}}===
{{trans|ANSI BASIC|Added functions for generating pseudorandom numbers.}}
'''Note.''' XBasic has also a standard function <code>XstQuickSort</code> in the ''xst'' library.
{{works with|Windows XBasic}}
<syntaxhighlight lang="basic">
' Sorting algorithms/Quicksort
PROGRAM "quicksort"
VERSION "1.0"
IMPORT "xst"
DECLARE FUNCTION Entry ()
DECLARE FUNCTION QuickSort (@arr%[], l%%, r%%)
' Pseudo-random number generator
' Based on the rand, srand functions from Kernighan & Ritchie's book
' 'The C Programming Language'
DECLARE FUNCTION Rand()
DECLARE FUNCTION SRand(seed%%)
FUNCTION Entry ()
DIM arr%[19]
a%% = 0
b%% = UBOUND(arr%[])
XstGetSystemTime (@msec)
SRand(INT(msec) MOD 32768)
FOR i%% = a%% TO b%%
arr%[i%%] = INT(Rand() / 32768.0 * 99.0)
NEXT i%%
PRINT "Unsorted:"
FOR i%% = a%% TO b%%
PRINT FORMAT$("## ", arr%[i%%]);
NEXT i%%
PRINT
PRINT "Sorted:"
QuickSort(@arr%[], a%%, b%%)
FOR i%% = a%% TO b%%
PRINT FORMAT$("## ", arr%[i%%]);
NEXT i%%
PRINT
END FUNCTION
FUNCTION QuickSort (@arr%[], l%%, r%%)
leftIndex%% = l%%
rightIndex%% = r%%
IF r%% > l%% THEN
pivot%% = (l%% + r%%) \ 2
DO WHILE (leftIndex%% <= pivot%%) AND (rightIndex%% >= pivot%%)
DO WHILE (arr%[leftIndex%%] < arr%[pivot%%]) AND (leftIndex%% <= pivot%%)
INC leftIndex%%
LOOP
DO WHILE (arr%[rightIndex%%] > arr%[pivot%%]) AND (rightIndex%% >= pivot%%)
DEC rightIndex%%
LOOP
SWAP arr%[leftIndex%%], arr%[rightIndex%%]
INC leftIndex%%
DEC rightIndex%%
SELECT CASE TRUE
CASE leftIndex%% - 1 = pivot%%:
INC rightIndex%%
pivot%% = rightIndex%%
CASE rightIndex%% + 1 = pivot%%:
DEC leftIndex%%
pivot%% = leftIndex%%
END SELECT
LOOP
QuickSort (@arr%[], l%%, pivot%% - 1)
QuickSort (@arr%[], pivot%% + 1, r%%)
END IF
END FUNCTION
' Return pseudo-random integer on 0..32767
FUNCTION Rand()
#next&& = #next&& * 1103515245 + 12345
END FUNCTION USHORT(#next&& / 65536) MOD 32768
' Set seed for Rand()
FUNCTION SRand(seed%%)
#next&& = seed%%
END FUNCTION
END PROGRAM
</syntaxhighlight>
{{out}} (example)
<pre>
Unsorted:
18 37 79 14 23 13 64 37 84 37 22 64 25 43 26 13 12 83 21 41
Sorted:
12 13 13 14 18 21 22 23 25 26 37 37 37 41 43 64 64 79 83 84
</pre>
==={{header|Yabasic}}===
Rosetta Code problem: https://rosettacode.org/wiki/Sorting_algorithms/Quicksort
by Jjuanhdez, 03/2023
<syntaxhighlight lang="basic">dim array(15)
a = 0
b = arraysize(array(),1)
for i = a to b
array(i) = ran(1000)
next i
print "unsort ";
for i = a to b
print array(i) using("####");
if i = b then print ""; else print ", "; : fi
next i
quickSort(array(), a, b)
print "\n sort ";
for i = a to b
print array(i) using("####");
if i = b then print ""; else print ", "; : fi
next i
print
end
sub quickSort(array(), l, r)
local asize, i, j, pivot
size = r - l +1
if size < 2 return
i = l
j = r
pivot = array(l + int(size / 2))
repeat
while array(i) < pivot
i = i + 1
wend
while pivot < array(j)
j = j - 1
wend
if i <= j then
temp = array(i)
array(i) = array(j)
array(j) = temp
i = i + 1
j = j - 1
fi
until i > j
if l < j quickSort(array(), l, j)
if i < r quickSort(array(), i, r)
end sub</syntaxhighlight>
{{out}}
<pre>unsort 582, 796, 598, 478, 27, 125, 477, 679, 133, 513, 154, 93, 451, 463, 20
sort 20, 27, 93, 125, 133, 154, 451, 463, 477, 478, 513, 582, 598, 679, 796
</pre>
=={{header|BCPL}}==
<
GET "libhdr.h"
Line 570 ⟶ 3,624:
}
newline()
}</
=={{header|Beads}}==
<syntaxhighlight lang="beads">beads 1 program Quicksort
calc main_init
var arr = [1, 3, 5, 1, 7, 9, 8, 6, 4, 2]
var arr2 = arr
quicksort(arr, 1, tree_count(arr))
var tempStr : str
loop across:arr index:ix
tempStr = tempStr & ' ' & to_str(arr[ix])
log tempStr
calc quicksort(
arr:array of num
startIndex
highIndex
)
if (startIndex < highIndex)
var partitionIndex = partition(arr, startIndex, highIndex)
quicksort(arr, startIndex, partitionIndex - 1)
quicksort(arr, partitionIndex+1, highIndex)
calc partition(
arr:array of num
startIndex
highIndex
):num
var pivot = arr[highIndex]
var i = startIndex - 1
var j = startIndex
loop while:(j <= highIndex - 1)
if arr[j] < pivot
inc i
swap arr[i] <=> arr[j]
inc j
swap arr[i+1] <=> arr[highIndex]
return (i+1)
</syntaxhighlight>
{{out}}
1 1 2 3 4 5 6 7 8 9
=={{header|Bracmat}}==
Instead of comparing elements explicitly, this solution puts the two elements-to-compare in a sum. After evaluating the sum its terms are sorted. Numbers are sorted numerically, strings alphabetically and compound expressions by comparing nodes and leafs in a left-to right order. Now there are three cases: either the terms stayed put, or they were swapped, or they were equal and were combined into one term with a factor <code>2</code> in front. To not let the evaluator add numbers together, each term is constructed as a dotted list.
<syntaxhighlight lang="bracmat">( ( Q
= Less Greater Equal pivot element
. !arg:%(?pivot:?Equal) %?arg
& :?Less:?Greater
& whl
' ( !arg:%?element ?arg
& (.!element)+(.!pivot) { BAD: 1900+90 adds to 1990, GOOD: (.1900)+(.90) is sorted to (.90)+(.1900) }
: ( (.!element)+(.!pivot)
& !element !Less:?Less
| (.!pivot)+(.!element)
& !element !Greater:?Greater
| ?&!element !Equal:?Equal
)
)
& Q$!Less !Equal Q$!Greater
| !arg
)
& out$Q$(1900 optimized variants of 4001/2 Quicksort (quick,sort) are (quick,sober) features of 90 languages)
);</syntaxhighlight>
{{out}}
<pre> 90
1900
4001/2
Quicksort
are
features
languages
of
of
optimized
variants
(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}}==
<syntaxhighlight lang="c">
#include <stdio.h>
void quicksort(int *A, int len);
int n
int
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}
printf("\n");
quicksort(a, n);
for (i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("\n");
return 0;
}
void quicksort(int *A, int len) {
if (len < 2) return;
int pivot = A[len / 2];
int i, j;
for (i = 0, j = len - 1; ; i++, j--) {
while (A[i] < pivot) i++;
while (A[j] > pivot) j--;
if (i >= j) break;
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
quicksort(A, i);
quicksort(A + i, len - i);
}
</syntaxhighlight>
{{out}}
<pre>
4 65 2 -31 0 99 2 83 782 1
-31 0 1 2 2 4 65 83 99 782
</pre>
Randomized sort with separated components.
<syntaxhighlight lang="c">
#include <stdlib.h> // REQ: rand()
void swap(int *a, int *b) {
int c = *a;
*a = *b;
*b = c;
}
int partition(int A[], int p, int q) {
swap(&A[p + (rand() % (q - p + 1))], &A[q]); // PIVOT = A[q]
int i = p - 1;
for(int j = p; j <= q; j++) {
if(A[j] <= A[q]) {
swap(&A[++i], &A[j]);
}
}
return i;
}
void quicksort(int A[], int p, int q) {
if(p < q) {
int pivotIndx = partition(A, p, q);
quicksort(A, p, pivotIndx - 1);
quicksort(A, pivotIndx + 1, q);
}
}
</syntaxhighlight>
=={{header|C sharp|C#}}==
<syntaxhighlight lang="csharp">//
// The Tripartite conditional enables Bentley-McIlroy 3-way Partitioning.
// This performs additional compares to isolate islands of keys equal to
// the pivot value. Use unless key-equivalent classes are of small size.
//
#define Tripartite
namespace RosettaCode {
using System;
using System.Diagnostics;
public class QuickSort<T> where T : IComparable {
#region Constants
public const UInt32 INSERTION_LIMIT_DEFAULT = 12;
private const Int32 SAMPLES_MAX = 19;
#endregion
#region Properties
public UInt32 InsertionLimit { get; }
private T[] Samples { get; }
private Int32 Left { get; set; }
private Int32 Right { get; set; }
private Int32 LeftMedian { get; set; }
private Int32 RightMedian { get; set; }
#endregion
#region Constructors
public QuickSort(UInt32 insertionLimit = INSERTION_LIMIT_DEFAULT) {
this.InsertionLimit = insertionLimit;
this.Samples = new T[SAMPLES_MAX];
}
#endregion
#region Sort Methods
public void Sort(T[] entries) {
Sort(entries, 0, entries.Length - 1);
}
public void Sort(T[] entries, Int32 first, Int32 last) {
var length = last + 1 - first;
while (length > 1) {
if (length < InsertionLimit) {
InsertionSort<T>.Sort(entries, first, last);
return;
}
Left =
Right = last;
var median = pivot(entries);
partition(median, entries);
//[Note]Right < Left
var leftLength = Right + 1 - first;
var rightLength = last + 1 - Left;
//
// First recurse over shorter partition, then loop
// on the longer partition to elide tail recursion.
//
if (leftLength < rightLength) {
Sort(entries, first, Right);
first = Left;
length = rightLength;
}
length = leftLength;
}
}
}
/// <summary>Return an odd sample size proportional to the log of a large interval size.</summary>
private static Int32 sampleSize(Int32 length, Int32 max = SAMPLES_MAX) {
var logLen = (Int32)Math.Log10(length);
var samples = Math.Min(2 * logLen + 1, max);
return Math.Min(samples, length);
}
/// <summary>Estimate the median value of entries[Left:Right]</summary>
/// <remarks>A sample median is used as an estimate the true median.</remarks>
private T pivot(T[] entries) {
var length = Right + 1 - Left;
var samples = sampleSize(length);
// Sample Linearly:
for (var sample = 0; sample < samples; sample++) {
// Guard against Arithmetic Overflow:
var index = (Int64)length * sample / samples + Left;
Samples[sample] = entries[index];
}
InsertionSort<T>.Sort(Samples, 0, samples - 1);
return Samples[samples / 2];
}
private void partition(T median, T[] entries) {
var first = Left;
var last = Right;
#if Tripartite
LeftMedian = first;
RightMedian = last;
#endif
while (true) {
//[Assert]There exists some index >= Left where entries[index] >= median
//[Assert]There exists some index <= Right where entries[index] <= median
// So, there is no need for Left or Right bound checks
while (median.CompareTo(entries[Left]) > 0) Left++;
while (median.CompareTo(entries[Right]) < 0) Right--;
//[Assert]entries[Right] <= median <= entries[Left]
if (Right <= Left) break;
Swap(entries, Left, Right);
swapOut(median, entries);
Left++;
Right--;
//[Assert]entries[first:Left - 1] <= median <= entries[Right + 1:last]
}
if (Left == Right) {
Left++;
Right--;
}
//[Assert]Right < Left
swapIn(entries, first, last);
//[Assert]entries[first:Right] <= median <= entries[Left:last]
//[Assert]entries[Right + 1:Left - 1] == median when non-empty
}
#endregion
#region Swap Methods
[Conditional("Tripartite")]
private void swapOut(T median, T[] entries) {
if (median.CompareTo(entries[Left]) == 0) Swap(entries, LeftMedian++, Left);
if (median.CompareTo(entries[Right]) == 0) Swap(entries, Right, RightMedian--);
}
[Conditional("Tripartite")]
private void swapIn(T[] entries, Int32 first, Int32 last) {
// Restore Median entries
while (first < LeftMedian) Swap(entries, first++, Right--);
while (RightMedian < last) Swap(entries, Left++, last--);
}
/// <summary>Swap entries at the left and right indicies.</summary>
public void Swap(T[] entries, Int32 left, Int32 right) {
Swap(ref entries[left], ref entries[right]);
}
/// <summary>Swap two entities of type T.</summary>
public static void Swap(ref T e1, ref T e2) {
var e = e1;
e1 = e2;
e2 = e;
}
#endregion
}
#region Insertion Sort
static class InsertionSort<T> where T : IComparable {
public static void Sort(T[] entries, Int32 first, Int32 last) {
for (var next = first + 1; next <= last; next++)
insert(entries, first, next);
}
/// <summary>Bubble next entry up to its sorted location, assuming entries[first:next - 1] are already sorted.</summary>
private static void insert(T[] entries, Int32 first, Int32 next) {
var entry = entries[next];
while (next > first && entries[next - 1].CompareTo(entry) > 0)
entries[next] = entries[--next];
entries[next] = entry;
}
}
#endregion
}</syntaxhighlight>
'''Example''':
<syntaxhighlight lang="csharp"> using Sort;
using System;
class Program {
static void Main(String[] args) {
var entries = new Int32[] { 1, 3, 5, 7, 9, 8, 6, 4, 2 };
var sorter = new QuickSort<Int32>();
sorter.Sort(entries);
Console.WriteLine(String.Join(" ", entries));
}
}</syntaxhighlight>
{{out}}
<pre>1 2 3 4 5 6 7 8 9</pre>
A very inefficient way to do qsort in C# to prove C# code can be just as compact and readable as any dynamic code
<syntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.Linq;
namespace QSort
{
class QSorter
{
private static IEnumerable<IComparable> empty = new List<IComparable>();
public static IEnumerable<IComparable> QSort(IEnumerable<IComparable> iEnumerable)
{
if(iEnumerable.Any())
{
var pivot = iEnumerable.First();
return QSort(iEnumerable.Where((anItem) => pivot.CompareTo(anItem) > 0)).
Concat(iEnumerable.Where((anItem) => pivot.CompareTo(anItem) == 0)).
Concat(QSort(iEnumerable.Where((anItem) => pivot.CompareTo(anItem) < 0)));
}
return empty;
}
}
}</syntaxhighlight>
=={{header|CafeOBJ}}==
There is no builtin list type in CafeOBJ, so a user written list module is included.
<syntaxhighlight lang="$CafeOBJ">
mod! SIMPLE-LIST(X :: TRIV){
[NeList < List ]
op [] : -> List
op [_] : Elt -> List
op (_:_) : Elt List -> NeList -- consr
op _++_ : List List -> List {assoc} -- concatenate
var E : Elt
vars L L' : List
eq [ E ] = E : [] .
eq [] ++ L = L .
eq (E : L) ++ L' = E : (L ++ L') .
}
mod! QUICKSORT{
pr(SIMPLE-LIST(NAT))
op qsort_ : List -> List
op smaller__ : List Nat -> List
op larger__ : List Nat -> List
vars x y : Nat
vars xs ys : List
eq qsort [] = [] .
eq qsort (x : xs) = (qsort (smaller xs x)) ++ [ x ] ++ (qsort (larger xs x)) .
eq smaller [] x = [] .
eq smaller (x : xs) y = if x <= y then (x : (smaller xs y)) else (smaller xs y) fi .
eq larger [] x = [] .
eq larger (x : xs) y = if x <= y then (larger xs y) else (x : (larger xs y)) fi .
}
open QUICKSORT .
red qsort(5 : 4 : 3 : 2 : 1 : 0 : []) .
red qsort(5 : 5 : 4 : 3 : 5 : 2 : 1 : 1 : 0 : []) .
eof
</syntaxhighlight>
=={{header|C++}}==
The following implements quicksort with a median-of-three pivot. As idiomatic in C++, the argument <tt>last</tt> is a one-past-end iterator. Note that this code takes advantage of <tt>std::partition</tt>, which is O(n). Also note that it needs a random-access iterator for efficient calculation of the median-of-three pivot (more exactly, for O(1) calculation of the iterator <tt>mid</tt>).
<
#include <algorithm> // for std::partition
#include <functional> // for std::less
Line 676 ⟶ 4,136:
{
quicksort(first, last, std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());
}</
A simpler version of the above that just uses the first element as the pivot and only does one "partition".
<
#include <algorithm> // for std::partition
#include <functional> // for std::less
Line 700 ⟶ 4,160:
{
quicksort(first, last, std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());
}</
=={{header|Clojure}}==
A very Haskell-like solution using list comprehensions and lazy evaluation.
<
(if (empty? L)
'()
Line 779 ⟶ 4,171:
(lazy-cat (qsort (for [y L2 :when (< y pivot)] y))
(list pivot)
(qsort (for [y L2 :when (>= y pivot)] y))))))</
Another short version (using quasiquote):
<
(if pvt
`(~@(qsort (filter #(< % pvt) rs))
~pvt
~@(qsort (filter #(>= % pvt) rs)))))</
Another, more readable version (no macros):
<
(when pivot
(let [smaller #(< % pivot)]
(lazy-cat (qsort (filter smaller xs))
[pivot]
(qsort (remove smaller xs))))))</
A 3-group quicksort (fast when many values are equal):
<
(when pvt
(let [{left -1 mid 0 right 1} (group-by #(compare % pvt) coll)]
(lazy-cat (qsort3 left) mid (qsort3 right)))))</
A lazier version of above (unlike group-by, filter returns (and reads) a lazy sequence)
<
(when pivot
(lazy-cat (qsort (filter #(< % pivot) coll))
(filter #{pivot} coll)
(qsort (filter #(> % pivot) coll)))))</
=={{header|
{{works with|Visual COBOL}}
<syntaxhighlight lang="cobol"> IDENTIFICATION DIVISION.
PROGRAM-ID. quicksort RECURSIVE.
LOCAL-STORAGE SECTION.
01 temp PIC S9(8).
01 pivot PIC S9(8).
01 left-most-idx PIC 9(5).
01 right-most-idx PIC 9(5).
01 left-idx PIC 9(5).
01 right-idx PIC 9(5).
LINKAGE SECTION.
78 Arr-Length VALUE 50.
03 arr PIC S9(8) OCCURS Arr-Length TIMES.
01 left-val PIC 9(5).
01 right-val PIC 9(5).
PROCEDURE DIVISION USING REFERENCE arr-area, OPTIONAL left-val,
OPTIONAL right-val.
IF left-val IS OMITTED OR right-val IS OMITTED
MOVE 1 TO left-most-idx, left-idx
MOVE Arr-Length TO right-most-idx, right-idx
ELSE
MOVE left-val TO left-most-idx, left-idx
MOVE right-val TO right-most-idx, right-idx
GOBACK
END-IF
COMPUTE pivot = arr ((left-most-idx + right-most-idx) / 2)
PERFORM UNTIL left-idx > right-idx
PERFORM VARYING left-idx FROM left-idx BY 1
UNTIL arr (left-idx) >= pivot
END-PERFORM
PERFORM VARYING right-idx FROM right-idx BY -1
UNTIL arr (right-idx) <= pivot
END-PERFORM
IF left-idx <= right-idx
MOVE arr (left-idx) TO temp
MOVE arr (right-idx) TO arr (left-idx)
MOVE temp TO arr (right-idx)
ADD 1 TO left-idx
SUBTRACT 1 FROM right-idx
END-IF
END-PERFORM
CALL "quicksort" USING REFERENCE arr-area,
CONTENT left-most-idx, right-idx
CALL "quicksort" USING REFERENCE arr-area, CONTENT left-idx,
right-most-idx
GOBACK
.</syntaxhighlight>
=={{header|CoffeeScript}}==
<syntaxhighlight lang="coffeescript">
quicksort = ([x, xs...]) ->
return [] unless x?
smallerOrEqual = (a for a in xs when a <= x)
larger = (a for a in xs when a > x)
(quicksort smallerOrEqual).concat(x).concat(quicksort larger)
</syntaxhighlight>
=={{header|Common Lisp}}==
Line 855 ⟶ 4,285:
The functional programming way
<
(if (cdr list)
(nconc (quicksort (remove-if-not #'(lambda (x) (< x pivot)) list))
(remove-if-not #'(lambda (x) (= x pivot)) list)
(quicksort (remove-if-not #'(lambda (x) (> x pivot)) list)))
list))</
With flet
<
(if (cdr list)
(flet ((pivot (test)
(remove (car list) list :test-not test)))
(nconc (qs (pivot #'>)) (pivot #'=) (qs (pivot #'<))))
list))</
In-place non-functional
<
(labels ((swap (a b) (rotatef (elt sequence a) (elt sequence b)))
(sub-sort (left right)
Line 886 ⟶ 4,316:
(sub-sort (1+ index) right)))))
(sub-sort 0 (1- (length sequence)))
sequence))</
Functional with destructuring
<syntaxhighlight lang="lisp">
(defun quicksort (list)
(when list
(destructuring-bind (x . xs) list
(nconc (quicksort (remove-if (lambda (a) (> a x)) xs))
`(,x)
(quicksort (remove-if (lambda (a) (<= a x)) xs))))))</syntaxhighlight>
=={{header|Cowgol}}==
<syntaxhighlight lang="cowgol">include "cowgol.coh";
# Comparator interface, on the model of C, i.e:
# foo < bar => -1, foo == bar => 0, foo > bar => 1
typedef CompRslt is int(-1, 1);
interface Comparator(foo: intptr, bar: intptr): (rslt: CompRslt);
# Quicksort an array of pointer-sized integers given a comparator function
# (This is the closest you can get to polymorphism in Cowgol).
# Because Cowgol does not support recursion, a pointer to free memory
# for a stack must also be given.
sub qsort(A: [intptr], len: intptr, comp: Comparator, stack: [intptr]) is
# The partition function can be taken almost verbatim from Wikipedia
sub partition(lo: intptr, hi: intptr): (p: intptr) is
# This is not quite as bad as it looks: /2 compiles into a single shift
# and "@bytesof intptr" is always power of 2 so compiles into shift(s).
var pivot := [A + (hi/2 + lo/2) * @bytesof intptr];
var i := lo - 1;
var j := hi + 1;
loop
loop
i := i + 1;
if comp([A + i*@bytesof intptr], pivot) != -1 then
break;
end if;
end loop;
loop
j := j - 1;
if comp([A + j*@bytesof intptr], pivot) != 1 then
break;
end if;
end loop;
if i >= j then
p := j;
return;
end if;
var ii := i * @bytesof intptr;
var jj := j * @bytesof intptr;
var t := [A+ii];
[A+ii] := [A+jj];
[A+jj] := t;
end loop;
end sub;
# Cowgol lacks recursion, so we'll have to solve it by implementing
# the stack ourselves.
var sp: intptr := 0; # stack index
sub push(n: intptr) is
sp := sp + 1;
[stack] := n;
stack := @next stack;
end sub;
sub pop(): (n: intptr) is
sp := sp - 1;
stack := @prev stack;
n := [stack];
end sub;
# start by sorting [0..length-1]
push(len-1);
push(0);
while sp != 0 loop
var lo := pop();
var hi := pop();
if lo < hi then
var p := partition(lo, hi);
push(hi); # note the order - we need to push the high pair
push(p+1); # first for it to be done last
push(p);
push(lo);
end if;
end loop;
end sub;
# Test: sort a list of numbers
sub NumComp implements Comparator is
# Compare the inputs as numbers
if foo < bar then rslt := -1;
elseif foo > bar then rslt := 1;
else rslt := 0;
end if;
end sub;
# Numbers
var numbers: intptr[] := {
65,13,4,84,29,5,96,73,5,11,17,76,38,26,44,20,36,12,44,51,79,8,99,7,19,95,26
};
# Room for the stack
var stackbuf: intptr[256];
# Sort the numbers in place
qsort(&numbers as [intptr], @sizeof numbers, NumComp, &stackbuf as [intptr]);
# Print the numbers (hopefully in order)
var i: @indexof numbers := 0;
while i < @sizeof numbers loop
print_i32(numbers[i] as uint32);
print_char(' ');
i := i + 1;
end loop;
print_nl();</syntaxhighlight>
{{out}}
<pre>4 5 5 7 8 11 12 13 17 19 20 26 26 29 36 38 44 44 51 65 73 76 79 84 95 96 99</pre>
=={{header|Crystal}}==
{{trans|Ruby}}
<syntaxhighlight lang="ruby">def quick_sort(a : Array(Int32)) : Array(Int32)
return a if a.size <= 1
p = a[0]
lt, rt = a[1 .. -1].partition { |x| x < p }
return quick_sort(lt) + [p] + quick_sort(rt)
end
a = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]
puts quick_sort(a) # => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</syntaxhighlight>
=={{header|Curry}}==
Copied from [http://www.informatik.uni-kiel.de/~curry/examples/ Curry: Example Programs].
<
qsort :: [Int] -> [Int]
Line 896 ⟶ 4,456:
qsort (x:l) = qsort (filter (<x) l) ++ x : qsort (filter (>=x) l)
goal = qsort [2,3,1,0]</
=={{header|D}}==
A
<
import std.algorithm: filter;
import std.array;
T[] quickSort(T)(T[]
xs[1 .. $].filter!(x => x< xs[0]).array.quickSort ~
xs[0 .. 1] ~
xs[1 .. $].filter!(x => x>=xs[0]).array.quickSort;
void main() =>
[4, 65, 2, -31, 0, 99, 2, 83, 782, 1].quickSort.writeln;
</syntaxhighlight>
{{out}}
<pre>[-31, 0, 1, 2, 2, 4, 65, 83, 99, 782]</pre>
A simple high-level version (same output):
<syntaxhighlight lang="d">import std.stdio, std.array;
T[] quickSort(T)(T[] items) pure nothrow {
if (items.empty)
return items;
T[] less,
foreach (x; items[1 .. $])
(x < items[0] ? less :
return
}
void main() {
}</
Often short functional sieves are not a true implementations of the Sieve of Eratosthenes:
http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
Similarly, one could argue that a true QuickSort is in-place,
as this more efficient version (same output):
<syntaxhighlight lang="d">import std.stdio, std.algorithm;
void quickSort(T)(T[] items) pure nothrow @safe @nogc {
if (items.length >= 2) {
auto parts = partition3(items, items[$ / 2]);
}
}
void main() {
auto items = [4, 65, 2, -31, 0, 99, 2, 83, 782, 1];
}</
=={{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}}==
<
if (a.length <= 1) {
return a;
Line 976 ⟶ 4,727:
print("After sort");
arr.forEach((var i)=>print("$i"));
}</
=={{header|E}}==
<
def swap(container, ixA, ixB) {
Line 1,025 ⟶ 4,777:
quicksortR(array, 0, array.size() - 1)
}
}</
=={{header|EasyLang}}==
<syntaxhighlight lang="text">
proc 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]
#
if mid < (right + left) / 2
qsort left mid - 1 d[]
left = mid + 1
else
qsort mid + 1 right d[]
right = mid - 1
.
.
.
proc sort . d[] .
qsort 1 len d[] d[]
.
d[] = [ 29 4 72 44 55 26 27 77 92 5 ]
sort d[]
print d[]
</syntaxhighlight>
=={{header|EchoLisp}}==
<syntaxhighlight lang="scheme">
(lib 'list) ;; list-partition
(define compare 0) ;; counter
(define (quicksort L compare-predicate: proc aux: (part null))
(if (<= (length L) 1) L
(begin
;; counting the number of comparisons
(set! compare (+ compare (length (rest L))))
;; pivot = first element of list
(set! part (list-partition (rest L) proc (first L)))
(append (quicksort (first part) proc )
(list (first L))
(quicksort (second part) proc)))))
</syntaxhighlight>
{{out}}
<syntaxhighlight lang="scheme">
(shuffle (iota 15))
→ (10 0 14 11 13 9 2 5 4 8 1 7 12 3 6)
(quicksort (shuffle (iota 15)) <)
→ (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14)
;; random list of numbers in [0 .. n[
;; count number of comparisons
(define (qtest (n 10000))
(set! compare 0)
(quicksort (shuffle (iota n)) >)
(writeln 'n n 'compare# compare ))
(qtest 1000)
n 1000 compare# 12764
(qtest 10000)
n 10000 compare# 277868
(qtest 100000)
n 100000 compare# 6198601
</syntaxhighlight>
=={{header|Eero}}==
Translated from Objective-C example on this page.
<syntaxhighlight lang="objc">#import <Foundation/Foundation.h>
void quicksortInPlace(MutableArray array, const long first, const long last)
if first >= last
return
Value pivot = array[(first + last) / 2]
left := first
right := last
while left <= right
while array[left] < pivot
left++
while array[right] > pivot
right--
if left <= right
array.exchangeObjectAtIndex: left++, withObjectAtIndex: right--
quicksortInPlace(array, first, right)
quicksortInPlace(array, left, last)
Array quicksort(Array unsorted)
a := []
a.addObjectsFromArray: unsorted
quicksortInPlace(a, 0, a.count - 1)
return a
int main(int argc, const char * argv[])
autoreleasepool
a := [1, 3, 5, 7, 9, 8, 6, 4, 2]
Log( 'Unsorted: %@', a)
Log( 'Sorted: %@', quicksort(a) )
b := ['Emil', 'Peg', 'Helen', 'Juergen', 'David', 'Rick', 'Barb', 'Mike', 'Tom']
Log( 'Unsorted: %@', b)
Log( 'Sorted: %@', quicksort(b) )
return 0</syntaxhighlight>
Alternative implementation (not necessarily as efficient, but very readable)
<syntaxhighlight lang="objc">#import <Foundation/Foundation.h>
implementation Array (Quicksort)
plus: Array array, return Array =
self.arrayByAddingObjectsFromArray: array
filter: BOOL (^)(id) predicate, return Array
array := []
for id item in self
if predicate(item)
array.addObject: item
return array.copy
quicksort, return Array = self
if self.count > 1
id x = self[self.count / 2]
lesser := self.filter: (id y | return y < x)
greater := self.filter: (id y | return y > x)
return lesser.quicksort + [x] + greater.quicksort
end
int main()
autoreleasepool
a := [1, 3, 5, 7, 9, 8, 6, 4, 2]
Log( 'Unsorted: %@', a)
Log( 'Sorted: %@', a.quicksort )
b := ['Emil', 'Peg', 'Helen', 'Juergen', 'David', 'Rick', 'Barb', 'Mike', 'Tom']
Log( 'Unsorted: %@', b)
Log( 'Sorted: %@', b.quicksort )
return 0</syntaxhighlight>
{{out}}
<pre>
2013-09-04 16:54:31.780 a.out[2201:507] Unsorted: (
1,
3,
5,
7,
9,
8,
6,
4,
2
)
2013-09-04 16:54:31.781 a.out[2201:507] Sorted: (
1,
2,
3,
4,
5,
6,
7,
8,
9
)
2013-09-04 16:54:31.781 a.out[2201:507] Unsorted: (
Emil,
Peg,
Helen,
Juergen,
David,
Rick,
Barb,
Mike,
Tom
)
2013-09-04 16:54:31.782 a.out[2201:507] Sorted: (
Barb,
David,
Emil,
Helen,
Juergen,
Mike,
Peg,
Rick,
Tom
)
</pre>
=={{header|Eiffel}}==
The <syntaxhighlight lang="eiffel">QUICKSORT</syntaxhighlight> class:
<syntaxhighlight lang="eiffel">
class
QUICKSORT [G -> COMPARABLE]
create
make
feature {NONE} --Implementation
is_sorted (list: ARRAY [G]): BOOLEAN
require
not_void: list /= Void
local
i: INTEGER
do
Result := True
from
i := list.lower + 1
invariant
i >= list.lower + 1 and i <= list.upper + 1
until
i > list.upper
loop
Result := Result and list [i - 1] <= list [i]
i := i + 1
variant
list.upper + 1 - i
end
end
concatenate_array (a: ARRAY [G] b: ARRAY [G]): ARRAY [G]
require
not_void: a /= Void and b /= Void
do
create Result.make_from_array (a)
across
b as t
loop
Result.force (t.item, Result.upper + 1)
end
ensure
same_size: a.count + b.count = Result.count
end
quicksort_array (list: ARRAY [G]): ARRAY [G]
require
not_void: list /= Void
local
less_a: ARRAY [G]
equal_a: ARRAY [G]
more_a: ARRAY [G]
pivot: G
do
create less_a.make_empty
create more_a.make_empty
create equal_a.make_empty
create Result.make_empty
if list.count <= 1 then
Result := list
else
pivot := list [list.lower]
across
list as li
invariant
less_a.count + equal_a.count + more_a.count <= list.count
loop
if li.item < pivot then
less_a.force (li.item, less_a.upper + 1)
elseif li.item = pivot then
equal_a.force (li.item, equal_a.upper + 1)
elseif li.item > pivot then
more_a.force (li.item, more_a.upper + 1)
end
end
Result := concatenate_array (Result, quicksort_array (less_a))
Result := concatenate_array (Result, equal_a)
Result := concatenate_array (Result, quicksort_array (more_a))
end
ensure
same_size: list.count = Result.count
sorted: is_sorted (Result)
end
feature -- Initialization
make
do
end
quicksort (a: ARRAY [G]): ARRAY [G]
do
Result := quicksort_array (a)
end
end
</syntaxhighlight>
A test application:
<syntaxhighlight lang="eiffel">
class
APPLICATION
create
make
feature {NONE} -- Initialization
make
-- Run application.
local
test: ARRAY [INTEGER]
sorted: ARRAY [INTEGER]
sorter: QUICKSORT [INTEGER]
do
create sorter.make
test := <<1, 3, 2, 4, 5, 5, 7, -1>>
sorted := sorter.quicksort (test)
across
sorted as s
loop
print (s.item)
print (" ")
end
print ("%N")
end
end
</syntaxhighlight>
=={{header|Elena}}==
ELENA 6.x :
<syntaxhighlight lang="elena">import extensions;
import system'routines;
import system'collections;
extension op
{
quickSort()
{
if (self.isEmpty()) { ^ self };
var pivot := self[0];
auto less := new ArrayList();
auto pivotList := new ArrayList();
auto more := new ArrayList();
self.forEach::(item)
{
if (item < pivot)
{
less.append(item)
}
else if (item > pivot)
{
more.append(item)
}
else
{
pivotList.append(item)
}
};
less := less.quickSort();
more := more.quickSort();
less.appendRange(pivotList);
less.appendRange(more);
^ less
}
}
public program()
{
var list := new int[]{3, 14, 1, 5, 9, 2, 6, 3};
console.printLine("before:", list.asEnumerable());
console.printLine("after :", list.quickSort().asEnumerable());
}</syntaxhighlight>
{{out}}
<pre>
before:3,14,1,5,9,2,6,3
after :1,2,3,3,5,6,9,14
</pre>
=={{header|Elixir}}==
<syntaxhighlight lang="elixir">defmodule Sort do
def qsort([]), do: []
def qsort([h | t]) do
{lesser, greater} = Enum.split_with(t, &(&1 < h))
qsort(lesser) ++ [h] ++ qsort(greater)
end
end</syntaxhighlight>
=={{header|Erlang}}==
like haskell.
Used by [[Measure_relative_performance_of_sorting_algorithms_implementations]]. If changed keep the interface or change [[Measure_relative_performance_of_sorting_algorithms_implementations]]
<syntaxhighlight lang="erlang">
-module( quicksort ).
-export( [qsort/1] ).
qsort([]) -> [];
qsort([X|Xs]) ->
qsort([ Y || Y <- Xs, Y < X]) ++ [X] ++ qsort([ Y || Y <- Xs, Y >= X]).
</syntaxhighlight>
multi-process implementation (number processes = number of processor cores):
<syntaxhighlight lang="erlang">
quick_sort(L) -> qs(L, trunc(math:log2(erlang:system_info(schedulers)))).
qs([],_) -> [];
qs([H|T], N) when N > 0 ->
{Parent, Ref} = {self(), make_ref()},
spawn(fun()-> Parent ! {l1, Ref, qs([E||E<-T, E<H], N-1)} end),
spawn(fun()-> Parent ! {l2, Ref, qs([E||E<-T, H =< E], N-1)} end),
{L1, L2} = receive_results(Ref, undefined, undefined),
L1 ++ [H] ++ L2;
qs([H|T],_) ->
qs([E||E<-T, E<H],0) ++ [H] ++ qs([E||E<-T, H =< E],0).
receive_results(Ref, L1, L2) ->
receive
{l1, Ref, L1R} when L2 == undefined -> receive_results(Ref, L1R, L2);
{l2, Ref, L2R} when L1 == undefined -> receive_results(Ref, L1, L2R);
{l1, Ref, L1R} -> {L1R, L2};
{l2, Ref, L2R} -> {L1, L2R}
after 5000 -> receive_results(Ref, L1, L2)
end.
</syntaxhighlight>
=={{header|Emacs Lisp}}==
'''Unoptimized'''
{{libheader|seq.el}}
<syntaxhighlight lang="lisp">(require 'seq)
(defun quicksort (xs)
(if (null xs)
()
(let* ((head (car xs))
(tail (cdr xs))
(lower-part (quicksort (seq-filter (lambda (x) (<= x head)) tail)))
(higher-part (quicksort (seq-filter (lambda (x) (> x head)) tail))))
(append lower-part (list head) higher-part))))</syntaxhighlight>
=={{header|ERRE}}==
<syntaxhighlight lang="erre">
PROGRAM QUICKSORT_DEMO
DIM ARRAY[21]
!$DYNAMIC
DIM QSTACK[0]
!$INCLUDE="PC.LIB"
PROCEDURE QSORT(ARRAY[],START,NUM)
FIRST=START ! initialize work variables
LAST=START+NUM-1
LOOP
REPEAT
TEMP=ARRAY[(LAST+FIRST) DIV 2] ! seek midpoint
I=FIRST
J=LAST
REPEAT ! reverse both < and > below to sort descending
WHILE ARRAY[I]<TEMP DO
I=I+1
END WHILE
WHILE ARRAY[J]>TEMP DO
J=J-1
END WHILE
EXIT IF I>J
IF I<J THEN SWAP(ARRAY[I],ARRAY[J]) END IF
I=I+1
J=J-1
UNTIL NOT(I<=J)
IF I<LAST THEN ! Done
QSTACK[SP]=I ! Push I
QSTACK[SP+1]=LAST ! Push Last
SP=SP+2
END IF
LAST=J
UNTIL NOT(FIRST<LAST)
EXIT IF SP=0
SP=SP-2
FIRST=QSTACK[SP] ! Pop First
LAST=QSTACK[SP+1] ! Pop Last
END LOOP
END PROCEDURE
BEGIN
RANDOMIZE(TIMER) ! generate a new series each run
! create an array
FOR X=1 TO 21 DO ! fill with random numbers
ARRAY[X]=RND(1)*500 ! between 0 and 500
END FOR
PRIMO=6 ! sort starting here
NUM=10 ! sort this many elements
CLS
PRINT("Before Sorting:";TAB(31);"After sorting:")
PRINT("===============";TAB(31);"==============")
FOR X=1 TO 21 DO ! show them before sorting
IF X>=PRIMO AND X<=PRIMO+NUM-1 THEN
PRINT("==>";)
END IF
PRINT(TAB(5);)
WRITE("###.##";ARRAY[X])
END FOR
! create a stack
!$DIM QSTACK[INT(NUM/5)+10]
QSORT(ARRAY[],PRIMO,NUM)
!$ERASE QSTACK
LOCATE(2,1)
FOR X=1 TO 21 DO ! print them after sorting
LOCATE(2+X,30)
IF X>=PRIMO AND X<=PRIMO+NUM-1 THEN
PRINT("==>";) ! point to sorted items
END IF
LOCATE(2+X,35)
WRITE("###.##";ARRAY[X])
END FOR
END PROGRAM
</syntaxhighlight>
=={{header|F Sharp|F#}}==
<
let rec qsort = function
let less, greater = List.partition ((>=) hd) tl
List.concat [qsort less; [hd]; qsort greater]
| _ -> []
</syntaxhighlight>
=={{header|Factor}}==
<
dup empty? [
unclip [ [ < ] curry partition [ qsort ] bi@ ] keep
prefix append
] unless ;</
=={{header|
<syntaxhighlight lang="clojure">
; utility for list joining
(= join (fn (a b)
(if (is a nil) b (is b nil) a (do
(let res a)
(while (cdr a) (= a (cdr a)))
(setcdr a b)
res))))
(= quicksort (fn (lst)
(if (not (cdr lst)) lst (do
(let less nil)
(let equal nil)
(let greater nil)
; filter list for less than pivot, equal to pivot and greater than pivot
(while lst
(let x (car lst))
(if (< x pivot) (= less (cons x less))
(< pivot x) (= greater (cons x greater))
(= equal (cons x equal)))
(= lst (cdr lst)))
; sort 'less' and 'greater' partitions ('equal' partition is always sorted)
(= less (quicksort less))
(= greater (quicksort greater))
; join partitions to one
(join less (join equal greater))))))
(print '(4 65 0
(print (quicksort '(4 65 0 2 -31 99 2 0 83 782 1)))
</syntaxhighlight>
Outputs:
<syntaxhighlight lang="clojure">
(4 65 0 2 -31 99 2 0 83 782 1)
(-31 0 0 1 2 2 4 65 83 99 782)
</syntaxhighlight>
=={{header|Fexl}}==
<syntaxhighlight lang="fexl"># (sort xs) is the ordered list of all elements in list xs.
# This version preserves duplicates.
\sort==
(\xs
xs [] \x\xs
append (sort; filter (gt x) xs); # all the items less than x
cons x; append (filter (eq x) xs); # all the items equal to x
sort; filter (lt x) xs # all the items greater than x
)
# (unique xs) is the ordered list of unique elements in list xs.
\unique==
(\xs
xs [] \x\xs
append (unique; filter (gt x) xs); # all the items less than x
cons x; # x itself
unique; filter (lt x) xs # all the items greater than x
)
</syntaxhighlight>
=={{header|Forth}}==
<syntaxhighlight lang="forth">: mid ( l r -- mid ) over - 2/ -cell and + ;
: exch ( addr1 addr2 -- ) dup @ >r over @ swap ! r> swap ! ;
Line 1,078 ⟶ 5,388:
2dup mid @ >r ( r: pivot )
2dup begin
swap begin dup @ r@
swap begin r@ over @
2dup <= if 2dup exch >r cell+ r> cell- then
2dup > until r> drop ;
Line 1,091 ⟶ 5,401:
: sort ( array len -- )
dup 2 < if 2drop exit then
1- cells over + qsort ;</
=={{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
logical :: stay
real :: t
real :: x
!
!*Code
!
last = size(a, 1)
if( (last - first)<changesize )then
call insertion_sort(a(first:last))
return
end if
j = shiftr((first + last), 1) + 1
!
x = a(j)
i = first
j = last
stay = .true.
do while ( stay )
do while ( a(i)<x )
i = i + 1
end do
do while ( x<a(j) )
j = j - 1
end do
if( j<i )then
stay = .false.
else
t = a(i) ! Swap the values
a(i) = a(j)
a(j) = t
i = i + 1 ! Adjust the pointers (PIVOT POINTS)
j = j - 1
end if
end do
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
return
end subroutine fsort
</syntaxhighlight>
=={{header|FunL}}==
<syntaxhighlight lang="funl">def
qsort( [] ) = []
qsort( p:xs ) = qsort( xs.filter((< p)) ) + [p] + qsort( xs.filter((>= p)) )</syntaxhighlight>
Here is a more efficient version using the <code>partition</code> function.
<syntaxhighlight lang="funl">def
qsort( [] ) = []
val (ys, zs) = xs.partition( (< x) )
qsort( ys ) + (x : qsort( zs ))
println( qsort([4, 2, 1, 3, 0, 2]) )
println( qsort(["Juan", "Daniel", "Miguel", "William", "Liam", "Ethan", "Jacob"]) )</syntaxhighlight>
{{out}}
<pre>
[0, 1, 2, 2, 3, 4]
[Daniel, Ethan, Jacob, Juan, Liam, Miguel, William]
</pre>
=={{header|Go}}==
Note that Go's <code>sort.Sort</code> function is a Quicksort so in practice it would be just be used.
It's actually a combination of quick sort, heap sort, and insertion sort.
It starts with a quick sort, after a depth of 2*ceil(lg(n+1)) it switches to heap sort, or once a partition becomes small (less than eight items) it switches to insertion sort.
Old school, following [http://comjnl.oxfordjournals.org/cgi/content/short/5/1/10 Hoare's 1962 paper].
Line 1,193 ⟶ 5,503:
Finally, the choice of a recursive closure over passing slices to a recursive function is really just a very small optimization. Slices are cheap because they do not copy the underlying array, but there's still a tiny bit of overhead in constructing the slice object. Passing just the two numbers is in the interest of avoiding that overhead.
<
import "fmt"
Line 1,285 ⟶ 5,595:
}
pex(0, len(a)-1)
}</
{{out}}
<pre>
unsorted: [31 41 59 26 53 58 97 93 23 84]
sorted! [23 26 31 41 53 58 59 84 93 97]
</pre>
More traditional version of quicksort. It work generically with any container that conforms to <code>sort.Interface</code>.
<syntaxhighlight lang="go">package main
import (
"fmt"
"sort"
"math/rand"
)
func partition(a sort.Interface, first int, last int, pivotIndex int) int {
a.Swap(first, pivotIndex) // move it to beginning
left := first+1
right := last
for left <= right {
for left <= last && a.Less(left, first) {
left++
}
for right >= first && a.Less(first, right) {
right--
}
if left <= right {
a.Swap(left, right)
left++
right--
}
}
a.Swap(first, right) // swap into right place
return right
}
func quicksortHelper(a sort.Interface, first int, last int) {
if first >= last {
return
}
pivotIndex := partition(a, first, last, rand.Intn(last - first + 1) + first)
quicksortHelper(a, first, pivotIndex-1)
quicksortHelper(a, pivotIndex+1, last)
}
func quicksort(a sort.Interface) {
quicksortHelper(a, 0, a.Len()-1)
}
func main() {
a := []int{1, 3, 5, 7, 9, 8, 6, 4, 2}
fmt.Printf("Unsorted: %v\n", a)
quicksort(sort.IntSlice(a))
fmt.Printf("Sorted: %v\n", a)
b := []string{"Emil", "Peg", "Helen", "Juergen", "David", "Rick", "Barb", "Mike", "Tom"}
fmt.Printf("Unsorted: %v\n", b)
quicksort(sort.StringSlice(b))
fmt.Printf("Sorted: %v\n", b)
}</syntaxhighlight>
{{out}}
<pre>
Unsorted: [1 3 5 7 9 8 6 4 2]
Sorted: [1 2 3 4 5 6 7 8 9]
Unsorted: [Emil Peg Helen Juergen David Rick Barb Mike Tom]
Sorted: [Barb David Emil Helen Juergen Mike Peg Rick Tom]
</pre>
Line 1,295 ⟶ 5,667:
The famous two-liner, reflecting the underlying algorithm directly:
<syntaxhighlight lang
qsort (x:xs) = qsort [y | y <- xs, y < x] ++ [x] ++ qsort [y | y <- xs, y >= x]</
A more efficient version, doing only one comparison per element:
<
qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort ys ++ [x]
(ys, zs) = partition (< x) xs</syntaxhighlight>
=={{header|Icon}} and {{header|Unicon}}==
<
demosort(quicksort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")
end
Line 1,361 ⟶ 5,723:
suspend lower # 1st return pivot point
suspend X # 2nd return modified X (in case immutable)
end</
Implementation notes:
Line 1,371 ⟶ 5,733:
<br/>Note: This example relies on [[Sorting_algorithms/Bubble_sort#Icon| the supporting procedures 'sortop', and 'demosort' in Bubble Sort]]. The full demosort exercises the named sort of a list with op = "numeric", "string", ">>" (lexically gt, descending),">" (numerically gt, descending), a custom comparator, and also a string.
{{out}} Abbreviated
<pre>Sorting Demo using procedure quicksort
on list : [ 3 14 1 5 9 2 6 3 ]
with op = &null: [ 1 2 3 3 5 6 9 14 ] (0 ms)
Line 1,377 ⟶ 5,740:
on string : "qwerty"
with op = &null: "eqrtwy" (0 ms)</pre>
=={{header|IDL}}==
IDL has a powerful optimized <tt>sort()</tt> built-in. The following is thus merely for demonstration.
<syntaxhighlight lang="idl">function qs, arr
if (count = n_elements(arr)) lt 2 then return,arr
pivot = total(arr) / count ; use the average for want of a better choice
return,[qs(arr[where(arr le pivot)]),qs(arr[where(arr gt pivot)])]
end</syntaxhighlight>
Example:
IDL> print,qs([3,17,-5,12,99])
-5 3 12 17 99
=={{header|Idris}}==
<syntaxhighlight lang="idris">quicksort : Ord elem => List elem -> List elem
quicksort [] = []
quicksort (x :: xs) =
let lesser = filter (< x) xs
greater = filter(>= x) xs in
(quicksort lesser) ++ [x] ++ (quicksort greater)</syntaxhighlight>
Example:
*quicksort> quicksort [1, 3, 7, 2, 5, 4, 9, 6, 8, 0]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] : List Integer
=={{header|Io}}==
<
quickSort := method(
if(size > 1) then(
Line 1,396 ⟶ 5,785:
lst := list(5, -1, -4, 2, 9)
lst quickSort println # ==> list(-4, -1, 2, 5, 9)
lst quickSortInPlace println # ==> list(-4, -1, 2, 5, 9)</
Another more low-level Quicksort implementation can be found in Io's [[http://github.com/stevedekorte/io/blob/master/samples/misc/qsort.io github ]] repository.
=={{header|Isabelle}}==
<syntaxhighlight lang="isabelle">theory Quicksort
imports Main
begin
fun quicksort :: "('a :: linorder) list ⇒ 'a list" where
"quicksort [] = []"
| "quicksort (x#xs) = (quicksort [y←xs. y<x]) @ [x] @ (quicksort [y←xs. y>x])"
lemma "quicksort [4::int, 2, 7, 1] = [1, 2, 4, 7]"
by(code_simp)
lemma set_first_second_partition:
fixes x :: "'a :: linorder"
shows "{y ∈ ys. y < x} ∪ {x} ∪ {y ∈ ys. x < y} =
insert x ys"
by fastforce
lemma set_quicksort: "set (quicksort xs) = set xs"
by(induction xs rule: quicksort.induct)
(simp add: set_first_second_partition[simplified])+
theorem "sorted (quicksort xs)"
proof(induction xs rule: quicksort.induct)
case 1
show "sorted (quicksort [])" by simp
next
case (2 x xs)
assume IH_less: "sorted (quicksort [y←xs. y<x])"
assume IH_greater: "sorted (quicksort [y←xs. y>x])"
have pivot_geq_first_partition:
"∀z∈set (quicksort [y←xs. y<x]). z ≤ x"
by (simp add: set_quicksort less_imp_le)
have pivot_leq_second_partition:
"∀z ∈ (set (quicksort [y←xs. y>x])). (x ≤ z)"
by (simp add: set_quicksort less_imp_le)
have first_partition_leq_second_partition:
"∀p∈set (quicksort [y←xs. y<x]).
∀z ∈ (set (quicksort [y←xs. y>x])). (p ≤ z)"
by (auto simp add: set_quicksort)
from IH_less IH_greater
pivot_geq_first_partition pivot_leq_second_partition
first_partition_leq_second_partition
show "sorted (quicksort (x # xs))" by(simp add: sorted_append)
qed
text‹
The specification on rosettacode says
▪ All elements less than the pivot must be in the first partition.
▪ All elements greater than the pivot must be in the second partition.
Since this specification neither says "less than or equal" nor
"greater or equal", this quicksort implementation removes duplicate elements.
›
lemma "quicksort [1::int, 1, 1, 2, 2, 3] = [1, 2, 3]"
by(code_simp)
text‹If we try the following, we automatically get a counterexample›
lemma "length (quicksort xs) = length xs"
(*
Auto Quickcheck found a counterexample:
xs = [a⇩1, a⇩1]
Evaluated terms:
length (quicksort xs) = 1
length xs = 2
*)
oops
end
</syntaxhighlight>
=={{header|J}}==
{{eff note|J|/:~}}
<
quicksort=: 3 : 0
Line 1,412 ⟶ 5,873:
(quicksort y <sel e),(y =sel e),quicksort y >sel e
end.
)</
See the [[j:Essays/Quicksort|Quicksort essay]] in the J Wiki
Line 1,418 ⟶ 5,879:
=={{header|Java}}==
=== Imperative ===
{{works with|Java|1.5+}}<br>
{{trans|Python}}
<
if (
return arr;
else
E pivot = arr.get(0);
List<E> less = new LinkedList<E>();
List<E> pivotList = new LinkedList<E>();
List<E> more = new LinkedList<E>();
// Partition
for (E i: arr) {
if (i.compareTo(pivot) < 0)
less.add(i);
else if (i.compareTo(pivot) > 0)
more.add(i);
else
pivotList.add(i);
}
// Recursively sort sublists
less = quickSort(less);
more = quickSort(more);
// Concatenate results
less.addAll(pivotList);
less.addAll(more);
return less;
}
}
</syntaxhighlight>
=== Functional ===
{{works with|Java|1.8}}
<syntaxhighlight lang="java5">public static <E extends Comparable<E>> List<E> sort(List<E> col) {
if (col == null || col.isEmpty())
return Collections.emptyList();
else {
E pivot = col.get(0);
Map<Integer, List<E>> grouped = col.stream()
.collect(Collectors.groupingBy(pivot::compareTo));
return Stream.of(sort(grouped.get(1)), grouped.get(0), sort(grouped.get(-1)))
.flatMap(Collection::stream).collect(Collectors.toList());
}
}</syntaxhighlight>
=={{header|JavaScript}}==
===Imperative===
<syntaxhighlight lang="javascript">function sort(array, less) {
function swap(i, j) {
var t = array[i];
array[i] = array[j];
array[j] = t;
}
function quicksort(left, right) {
if (left < right) {
var pivot = array[left + Math.floor((right - left) / 2)],
do {
while (less(array[left_new], pivot)) {
left_new +
}
while (less(pivot, array[right_new
}
swap(left_new, right_new);
left_new += 1;
right_new -= 1;
}
} while (left_new <= right_new);
quicksort(left, right_new);
Line 1,480 ⟶ 5,970:
}
quicksort(0, array.length - 1);
return array;
}</
Example:<syntaxhighlight lang="javascript">var test_array = [10, 3, 11, 15, 19, 1];
var sorted_array = sort(test_array, function(a,b) { return a<b; });</syntaxhighlight>
{{Out}}<syntaxhighlight lang="javascript">[ 1, 3, 10, 11, 15, 19 ]</syntaxhighlight>
===Functional===
====ES6====
Using '''destructuring''' and '''satisfying immutability''' we can propose a single expresion solution (from https://github.com/ddcovery/expressive_sort)
<syntaxhighlight lang="javascript">const qsort = ([pivot, ...others]) =>
pivot === void 0 ? [] : [
...qsort(others.filter(n => n < pivot)),
pivot,
...qsort(others.filter(n => n >= pivot))
];
qsort( [ 11.8, 14.1, 21.3, 8.5, 16.7, 5.7 ] )</syntaxhighlight>
{{Out}}
<pre>[ 5.7, 8.5, 11.8, 14.1, 16.7, 21.3 ]
</pre>
====ES5====
Unlike what happens with ES6, there are no destructuring nor lambdas, but we can '''ensure immutability''' and propose a '''single expression''' solution with standard anonymous functions
<syntaxhighlight lang="javascript">
function qsort( xs ){
return xs.length === 0 ? [] : [].concat(
qsort( xs.slice(1).filter(function(x){ return x< xs[0] })),
xs[0],
qsort( xs.slice(1).filter(function(x){ return x>= xs[0] }))
)
}
qsort( [ 11.8, 14.1, 21.3, 8.5, 16.7, 5.7 ] )
</syntaxhighlight>
{{Out}}
<pre>[5.7, 8.5, 11.8, 14.1, 16.7, 21.3]</pre>
=={{header|Joy}}==
<
DEFINE qsort ==
[small] # termination condition: 0 or 1 element
Line 1,507 ⟶ 6,023:
[enconcat] # insert the pivot after the recursion
binrec. # recursion on the two lists
</syntaxhighlight>
=={{header|jq}}==
jq's built-in <tt>sort</tt> currently (version 1.4) uses the standard C qsort, a quicksort. <tt>sort</tt> can be used on any valid JSON array.
Example:<syntaxhighlight lang="jq">[1, 1.1, [1,2], true, false, null, {"a":1}, null] | sort</syntaxhighlight>{{Out}}<syntaxhighlight lang="jq">[null,null,false,true,1,1.1,[1,2],{"a":1}]</syntaxhighlight>
Here is an implementation in jq of the pseudo-code (and comments :-) given at the head of this article:<syntaxhighlight lang="jq">def quicksort:
if length < 2 then . # it is already sorted
else .[0] as $pivot
| reduce .[] as $x
# state: [less, equal, greater]
( [ [], [], [] ]; # three empty arrays:
if $x < $pivot then .[0] += [$x] # add x to less
elif $x == $pivot then .[1] += [$x] # add x to equal
else .[2] += [$x] # add x to greater
end
)
| (.[0] | quicksort ) + .[1] + (.[2] | quicksort )
end ;
</syntaxhighlight>Fortunately, the example input used above produces the same output,
and so both are omitted here.
=={{header|Julia}}==
Built-in function for in-place sorting via quicksort (the [https://github.com/JuliaLang/julia/blob/2364748377f2a79c0485fdd5155ec2116c9f0d37/base/sort.jl#L259-L296 code from the standard library is quite readable]):
<syntaxhighlight lang="julia">sort!(A, alg=QuickSort)</syntaxhighlight>
A simple polymorphic implementation of an in-place recursive quicksort (based on the pseudocode above):
<syntaxhighlight lang="julia">function quicksort!(A,i=1,j=length(A))
if j > i
pivot = A[rand(i:j)] # random element of A
left, right = i, j
while left <= right
while A[left] < pivot
left += 1
end
while A[right] > pivot
right -= 1
end
if left <= right
A[left], A[right] = A[right], A[left]
left += 1
right -= 1
end
end
quicksort!(A,i,right)
quicksort!(A,left,j)
end
return A
end</syntaxhighlight>
A one-line (but rather inefficient) implementation based on the Haskell version, which operates out-of-place and allocates temporary arrays:
<syntaxhighlight lang="julia">qsort(L) = isempty(L) ? L : vcat(qsort(filter(x -> x < L[1], L[2:end])), L[1:1], qsort(filter(x -> x >= L[1], L[2:end])))</syntaxhighlight>
{{out}}
<pre>julia> A = [84,77,20,60,47,20,18,97,41,49,31,39,73,68,65,52,1,92,15,9]
julia> qsort(A)
[1,9,15,18,20,20,31,39,41,47,49,52,60,65,68,73,77,84,92,97]
julia> quicksort!(copy(A))
[1,9,15,18,20,20,31,39,41,47,49,52,60,65,68,73,77,84,92,97]
julia> qsort(A) == quicksort!(copy(A)) == sort(A) == sort(A, alg=QuickSort)
true</pre>
=={{header|K}}==
<
Example:
<syntaxhighlight lang="k">
quicksort 1 3 5 7 9 8 6 4 2
</syntaxhighlight>
{{out}}
<pre>
1 2 3 4 5 6 7 8 9
</
Explanation:
<syntaxhighlight lang="k">
_f()
</syntaxhighlight>
is the current function called recursively.
<syntaxhighlight lang="k">
:[....]
</syntaxhighlight>
generally means :[condition1;then1;condition2;then2;....;else]. Though
Line 1,542 ⟶ 6,117:
This construct
<syntaxhighlight lang="k">
f:*x@1?#x
</syntaxhighlight>
assigns a random element in x (the argument) to f, as the pivot value.
Line 1,550 ⟶ 6,125:
And here is the full if/then/else clause:
<syntaxhighlight lang="k">
:[
0=#x; / if length of x is zero
Line 1,560 ⟶ 6,135:
_f x@&x>f) / sort (recursively) elements greater than f
]
</syntaxhighlight>
Though - as with APL and J - for larger arrays it's much faster to
Line 1,566 ⟶ 6,141:
list sorted ascending, i.e.
<syntaxhighlight lang="k">
t@<t:1 3 5 7 9 8 6 4 2
</syntaxhighlight>
=={{header|Koka}}==
Haskell-like solution
<syntaxhighlight lang="koka">fun qsort( xs : list<int> ) : div list<int> {
match(xs) {
Cons(x,xx) -> {
val ys = xx.filter fn(el) { el < x }
val zs = xx.filter fn(el) { el >= x }
qsort(ys) ++ [x] ++ qsort(zs)
}
Nil -> Nil
}
}</syntaxhighlight>
or using standard <code>partition</code> function
<syntaxhighlight lang="koka">fun qsort( xs : list<int> ) : div list<int> {
match(xs) {
Cons(x,xx) -> {
val (ys, zs) = xx.partition fn(el) { el < x }
qsort(ys) ++ [x] ++ qsort(zs)
}
Nil -> Nil
}
}</syntaxhighlight>
Example:
<syntaxhighlight lang="koka">fun main() {
val arr = [24,63,77,26,84,64,56,80,85,17]
println(arr.qsort.show)
}</syntaxhighlight>
{{out}}
<pre>[17,24,26,56,63,64,77,80,84,85]</pre>
=={{header|Kotlin}}==
A version that reflects the algorithm directly:
<syntaxhighlight lang="scala">fun <E : Comparable<E>> List<E>.qsort(): List<E> =
if (size < 2) this
else filter { it < first() }.qsort() +
filter { it == first() } +
filter { it > first() }.qsort()
</syntaxhighlight>
A more efficient version that does only one comparison per element:
<syntaxhighlight lang="scala">fun <E : Comparable<E>> List<E>.qsort(): List<E> =
if (size < 2) this
else {
val (less, high) = subList(1, size).partition { it < first() }
less.qsort() + first() + high.qsort()
}
</syntaxhighlight>
=={{header|Lambdatalk}}==
<syntaxhighlight lang="lisp">
We create a binary tree from a random array, then we walk the canopy.
1) three functions for readability:
{def BT.data {lambda {:t} {A.get 0 :t}}} -> BT.data
{def BT.left {lambda {:t} {A.get 1 :t}}} -> BT.left
{def BT.right {lambda {:t} {A.get 2 :t}}} -> BT.right
2) adding a leaf to the tree:
{def BT.add {lambda {:x :t}
{if {A.empty? :t}
then {A.new :x {A.new} {A.new}}
else {if {= :x {BT.data :t}}
then :t
else {if {< :x {BT.data :t}}
then {A.new {BT.data :t}
{BT.add :x {BT.left :t}}
{BT.right :t}}
else {A.new {BT.data :t}
{BT.left :t}
{BT.add :x {BT.right :t}} }}}}}}
-> BT.add
3) creating the tree from an array of numbers:
{def BT.create
{def BT.create.rec
{lambda {:l :t}
{if {A.empty? :l}
then :t
else {BT.create.rec {A.rest :l}
{BT.add {A.first :l} :t}} }}}
{lambda {:l}
{BT.create.rec :l {A.new}} }}
-> BT.create
4) walking the canopy -> sorting in increasing order:
{def BT.sort
{lambda {:t}
{if {A.empty? :t}
then else {BT.sort {BT.left :t}}
{BT.data :t}
{BT.sort {BT.right :t}} }}}
-> BT.sort
Testing
1) generating random numbers:
{def L {A.new
{S.map {lambda {:n} {floor {* {random} 100000}}} {S.serie 1 100}}}}
-> L = [1850,7963,50540,92667,72892,47361,19018,40640,10126,80235,48407,51623,63597,71675,27814,63478,18985,88032,46585,85209,
74053,95005,27592,9575,22162,35904,70467,38527,89715,36594,54309,39950,89345,72224,7772,65756,68766,43942,52422,85144,
66010,38961,21647,53194,72166,33545,49037,23218,27969,83566,19382,53120,55291,77374,27502,66648,99637,37322,9815,432,90565,
37831,26503,99232,87024,65625,75155,55382,30120,58117,70031,13011,81375,10490,39786,1926,71311,4213,55183,2583,22075,90411,
92928,61120,94259,433,93332,88423,64119,40850,94318,27816,84818,90632,5094,36696,94705,50602,45818,61365]
2) creating the tree is the main work:
{def T {BT.create {L}}}
-> T = [1850,[432,],[433,],]]],[7963,[7772,[1926,],[4213,[2583,],]],[5094,],]]]],]],[50540,[47361,[19018,[10126,[9575,],
[9815,],]]],[18985,[13011,[10490,],]],]],]]],[40640,[27814,[27592,[22162,[21647,[19382,],]],[22075,],]]],[23218,],
[27502,[26503,],]],]]]],]],[35904,[33545,[27969,[27816,],]],[30120,],]]],]],[38527,[36594,],[37322,[36696,],]],[37831,],]]]],
[39950,[38961,],[39786,],]]],]]]]],[46585,[43942,[40850,],]],[45818,],]]],]]]],[48407,],[49037,],]]]],[92667,[72892,
[51623,[50602,],]],[63597,[63478,[54309,[52422,],[53194,[53120,],]],]]],[55291,[55183,],]],[55382,],[58117,],[61120,],[61365,],]]]]]]],]],[71675,[70467,[65756,[65625,[64119,],]],]],[68766,[66010,],[66648,],]]],[70031,],]]]],[71311,],]]],
[72224,[72166,],]],]]]]],[80235,[74053,],[77374,[75155,],]],]]],[88032,[85209,[85144,[83566,[81375,],]],[84818,],]]],]],
[87024,],]]],[89715,[89345,[88423,],]],]],[90565,[90411,],]],[90632,],]]]]]]],[95005,[92928,],[94259,[93332,],]],[94318,],
[94705,],]]]]],[99637,[99232,],]],]]]]]]]
3) walking the canopy is fast:
{BT.sort {T}}
-> 432 433 1850 1926 2583 4213 5094 7772 7963 9575 9815 10126 10490 13011 18985 19018 19382 21647 22075 22162 23218 26503
27502 27592 27814 27816 27969 30120 33545 35904 36594 36696 37322 37831 38527 38961 39786 39950 40640 40850 43942 45818
46585 47361 48407 49037 50540 50602 51623 52422 53120 53194 54309 55183 55291 55382 58117 61120 61365 63478 63597 64119
65625 65756 66010 66648 68766 70031 70467 71311 71675 72166 72224 72892 74053 75155 77374 80235 81375 83566 84818 85144
85209 87024 88032 88423 89345 89715 90411 90565 90632 92667 92928 93332 94259 94318 94705 95005 99232 99637
4) walking with new leaves is fast:
{BT.sort {BT.add -1 {T}}}
-> -1 432 433 1850 1926 2583 4213 5094 7772 7963 9575 9815 10126 10490 13011 18985 19018 19382 21647 22075 22162 23218 26503
27502 27592 27814 27816 27969 30120 33545 35904 36594 36696 37322 37831 38527 38961 39786 39950 40640 40850 43942 45818 46585
47361 48407 49037 50540 50602 51623 52422 53120 53194 54309 55183 55291 55382 58117 61120 61365 63478 63597 64119 65625 65756
66010 66648 68766 70031 70467 71311 71675 72166 72224 72892 74053 75155 77374 80235 81375 83566 84818 85144 85209 87024 88032
88423 89345 89715 90411 90565 90632 92667 92928 93332 94259 94318 94705 95005 99232 99637
{BT.sort {BT.add 50000 {T}}}
-> 432 433 1850 1926 2583 4213 5094 7772 7963 9575 9815 10126 10490 13011 18985 19018 19382 21647 22075 22162 23218 26503
27502 27592 27814 27816 27969 30120 33545 35904 36594 36696 37322 37831 38527 38961 39786 39950 40640 40850 43942 45818 46585
47361 48407 49037 50000 50540 50602 51623 52422 53120 53194 54309 55183 55291 55382 58117 61120 61365 63478 63597 64119 65625
65756 66010 66648 68766 70031 70467 71311 71675 72166 72224 72892 74053 75155 77374 80235 81375 83566 84818 85144 85209 87024
88032 88423 89345 89715 90411 90565 90632 92667 92928 93332 94259 94318 94705 95005 99232 99637
{BT.sort {BT.add 100000 {T}}}
-> 432 433 1850 1926 2583 4213 5094 7772 7963 9575 9815 10126 10490 13011 18985 19018 19382 21647 22075 22162 23218 26503
27502 27592 27814 27816 27969 30120 33545 35904 36594 36696 37322 37831 38527 38961 39786 39950 40640 40850 43942 45818 46585
47361 48407 49037 50540 50602 51623 52422 53120 53194 54309 55183 55291 55382 58117 61120 61365 63478 63597 64119 65625 65756
66010 66648 68766 70031 70467 71311 71675 72166 72224 72892 74053 75155 77374 80235 81375 83566 84818 85144 85209 87024 88032
88423 89345 89715 90411 90565 90632 92667 92928 93332 94259 94318 94705 95005 99232 99637 100000
</syntaxhighlight>
=={{header|Lobster}}==
<syntaxhighlight lang="lobster">include "std.lobster"
def quicksort(xs, lt):
if xs.length <= 1:
xs
else:
pivot := xs[0]
tail := xs.slice(1, -1)
f1 := filter tail: lt(_, pivot)
f2 := filter tail: !lt(_, pivot)
append(append(quicksort(f1, lt), [ pivot ]),
quicksort(f2, lt))
sorted := [ 3, 9, 5, 4, 1, 3, 9, 5, 4, 1 ].quicksort(): _a < _b
print sorted</syntaxhighlight>
=={{header|Logo}}==
<
to small? :list
Line 1,586 ⟶ 6,342:
end
show quicksort [1 3 5 7 9 8 6 4 2]</
<
to incr :name
Line 1,620 ⟶ 6,376:
make "test {1 3 5 7 9 8 6 4 2}
sort :test
show :test</
=={{header|Logtalk}}==
<
quicksort(List, [], Sorted).
Line 1,639 ⟶ 6,395:
; Bigs = [X| Rest],
partition(Xs, Pivot, Smalls, Rest)
).</
=={{header|Lua}}==
NOTE: If you want to use quicksort in a Lua script, you don't need to implement it yourself. Just do: <pre>table.sort(tableName)</pre>
===in-place===
<syntaxhighlight lang="lua">--in-place quicksort
function quicksort(t, start, endi)
start, endi = start or 1, endi or #t
--partition w.r.t. first element
if(endi - start <
local pivot = start
for i = start + 1, endi do
if t[i] <= t[pivot] then
t[pivot
else
t[pivot],t[pivot+1],t[i] = t[i],t[pivot],t[pivot+1]
end
pivot = pivot + 1
Line 1,666 ⟶ 6,421:
--example
print(unpack(quicksort{5, 2, 7, 3, 4, 7, 1}))</
===non in-place===
<syntaxhighlight lang="lua">function quicksort(t)
if #t<2 then return t end
local pivot=t[1]
local a,b,c={},{},{}
for _,v in ipairs(t) do
if v<pivot then a[#a+1]=v
elseif v>pivot then c[#c+1]=v
else b[#b+1]=v
end
end
a=quicksort(a)
c=quicksort(c)
for _,v in ipairs(b) do a[#a+1]=v end
for _,v in ipairs(c) do a[#a+1]=v end
return a
end</syntaxhighlight>
=={{header|Lucid}}==
[http://i.csc.uvic.ca/home/hei/lup/06.html]
<
where
p = first a < a;
Line 1,679 ⟶ 6,452:
xdone = iseod x fby xdone or iseod x;
end;
end</
=={{header|M2000 Interpreter}}==
===Recursive calling Functions===
<syntaxhighlight lang="m2000 interpreter">
Module Checkit1 {
Group Quick {
Private:
Function partition {
Read &A(), p, r
x = A(r)
i = p-1
For j=p to r-1 {
If .LE(A(j), x) Then {
i++
Swap A(i),A(j)
}
}
Swap A(i+1),A(r)
= i+1
}
Public:
LE=Lambda->Number<=Number
Function quicksort {
Read &A(), p, r
If p < r Then {
q = .partition(&A(), p, r)
Call .quicksort(&A(), p, q - 1)
Call .quicksort(&A(), q + 1, r)
}
}
}
Dim A(10)<<Random(50, 100)
Print A()
Call Quick.quicksort(&A(), 0, Len(A())-1)
Print A()
}
Checkit1
</syntaxhighlight>
===Recursive calling Subs===
Variables p, r, q removed from quicksort function. we use stack for values. Also Partition push to stack now. Works for string arrays too.
<syntaxhighlight lang="m2000 interpreter">
Module Checkit2 {
Class Quick {
Private:
partition=lambda-> {
Read &A(), p, r : i = p-1 : x=A(r)
For j=p to r-1 {If .LE(A(j), x) Then i++:Swap A(i),A(j)
} : Swap A(i+1), A(r) : Push i+1
}
Public:
LE=Lambda->Number<=Number
Module ForStrings {
.partition<=lambda-> {
Read &A$(), p, r : i = p-1 : x$=A$(r)
For j=p to r-1 {If A$(j)<= x$ Then i++:Swap A$(i),A$(j)
} : Swap A$(i+1), A$(r) : Push i+1
}
}
Function quicksort (ref$) {
myQuick()
sub myQuick()
If Stackitem() >= stackitem(2) Then drop 2 : Exit Sub
Over 2, 2 : Call .partition(ref$) : Over : Shiftback 3, 2
myQuick(number, number - 1)
myQuick( number + 1, number)
End Sub
}
}
Quick=Quick()
Dim A(10)
A(0):=57, 83, 74, 98, 51, 73, 85, 76, 65, 92
Print A()
Call Quick.quicksort(&A(), 0, Len(A())-1)
Print A()
Quick=Quick()
Quick.ForStrings
Dim A$()
A$()=("one","two", "three","four", "five")
Print A$()
Call Quick.quicksort(&A$(), 0, Len(A$())-1)
Print A$()
}
Checkit2
</syntaxhighlight>
===Non Recursive===
Partition function return two values (where we want q, and use it as q-1 an q+1 now Partition() return final q-1 and q+1_
Example include numeric array, array of arrays (we provide a lambda for comparison) and string array.
<syntaxhighlight lang="m2000 interpreter">
Module Checkit3 {
Class Quick {
Private:
partition=lambda-> {
Read &A(), p, r : i = p-1 : x=A(r)
For j=p to r-1 {If .LE(A(j), x) Then i++:Swap A(i),A(j)
} : Swap A(i+1), A(r) : Push i+2, i
}
Public:
LE=Lambda->Number<=Number
Module ForStrings {
.partition<=lambda-> {
Read &A$(), p, r : i = p-1 : x$=A$(r)
For j=p to r-1 {If A$(j)<= x$ Then i++:Swap A$(i),A$(j)
} : Swap A$(i+1), A$(r) : Push i+2, i
}
}
Function quicksort {
Read ref$
{
loop : If Stackitem() >= Stackitem(2) Then Drop 2 : if empty then {Break} else continue
over 2,2 : call .partition(ref$) :shift 3
}
}
}
Quick=Quick()
Dim A(10)<<Random(50, 100)
Print A()
Call Quick.quicksort(&A(), 0, Len(A())-1)
Print A()
Quick=Quick()
Function join$(a$()) {
n=each(a$(), 1, -2)
k$=""
while n {
overwrite k$, ".", n^:=array$(n)
}
=k$
}
Stack New {
Data "1.3.6.1.4.1.11.2.17.19.3.4.0.4" , "1.3.6.1.4.1.11.2.17.19.3.4.0.1", "1.3.6.1.4.1.11150.3.4.0.1"
Data "1.3.6.1.4.1.11.2.17.19.3.4.0.10", "1.3.6.1.4.1.11.2.17.5.2.0.79", "1.3.6.1.4.1.11150.3.4.0"
Dim Base 0, arr(Stack.Size)
Link arr() to arr$()
i=0 : While not Empty {arr$(i)=piece$(letter$+".", ".") : i++ }
}
\\ change comparison function
Quick.LE=lambda (a, b)->{
Link a, b to a$(), b$()
def i=-1
do {
i++
} until a$(i)="" or b$(i)="" or a$(i)<>b$(i)
if b$(i)="" then =a$(i)="":exit
if a$(i)="" then =true:exit
=val(a$(i))<=val(b$(i))
}
Call Quick.quicksort(&arr(), 0, Len(arr())-1)
For i=0 to len(arr())-1 {
Print join$(arr(i))
}
\\ Fresh load
Quick=Quick()
Quick.ForStrings
Dim A$()
A$()=("one","two", "three","four", "five")
Print A$()
Call Quick.quicksort(&A$(), 0, Len(A$())-1)
Print A$()
}
Checkit3
</syntaxhighlight>
=={{header|M4}}==
<
define(`arg1', `$1')dnl
dnl
Line 1,709 ⟶ 6,643:
`sep(arg1$1,(shift$1),`()',`()')')')dnl
dnl
quicksort((3,1,4,1,5,9))</
{{out}}
<pre>
(1,1,3,4,5,9)
</pre>
=={{header|
<syntaxhighlight lang="lisp">
;; While not strictly required, it simplifies the
;; implementation considerably to use filter. MACLisp
;; Doesn't have one out of the box, so we bring our own
(DEFUN FILTER (F LIST)
(COND
((EQ LIST NIL) NIL)
((FUNCALL F (CAR LIST))
(CONS (CAR LIST) (FILTER F (CDR LIST))))
(T
(FILTER F (CDR LIST)))))
;; And then, quicksort.
(DEFUN QUICKSORT (LIST)
(COND
((OR (EQ LIST ())
(EQ (CDR LIST) ()))
LIST)
(T
(LET
((PIVOT (CAR LIST))
(REST (CDR LIST)))
(APPEND
(QUICKSORT (FILTER #'(LAMBDA (X) (<= X PIVOT)) REST))
(LIST PIVOT)
(QUICKSORT (FILTER #'(LAMBDA (X) (> X PIVOT)) REST)))))))
</syntaxhighlight>
=={{header|Maple}}==
<syntaxhighlight lang="maple">swap := proc(arr, a, b)
local temp := arr[a]:
arr[a] := arr[b]:
arr[b] := temp:
end proc:
quicksort := proc(arr, low, high)
local pi:
if (low < high) then
pi := qpart(arr,low,high):
quicksort(arr, low, pi-1):
quicksort(arr, pi+1, high):
end if:
end proc:
qpart := proc(arr, low, high)
local i,j,pivot;
pivot := arr[high]:
i := low-1:
for j from low to high-1 by 1 do
if (arr[j] <= pivot) then
i++:
swap(arr, i, j):
end if;
end do;
swap(arr, i+1, high):
return (i+1):
end proc:
a:=Array([12,4,2,1,0]);
quicksort(a,1,5);
a;</syntaxhighlight>
{{Out|Output}}
<pre>[0, 1, 2, 4, 12]</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">QuickSort[x_List] := Module[{pivot},
If[Length@x <= 1, Return[x]];
pivot = RandomChoice@x;
Flatten@{QuickSort[Cases[x, j_ /; j < pivot]], Cases[x, j_ /; j == pivot], QuickSort[Cases[x, j_ /; j > pivot]]}
]</
<syntaxhighlight lang="mathematica">qsort[{}] = {};
qsort[{x_, xs___}] := Join[qsort@Select[{xs}, # <= x &], {x}, qsort@Select[{xs}, # > x &]];</syntaxhighlight>
<syntaxhighlight lang="mathematica">QuickSort[{}] := {}
QuickSort[list: {__}] := With[{pivot=RandomChoice[list]},
Join[ <|1->{}, -1->{}|>, GroupBy[list,Order[#,pivot]&] ] // Catenate[ {QuickSort@#[1], #[0], QuickSort@#[-1]} ]&
]</syntaxhighlight>
=={{header|MATLAB}}==
Line 1,732 ⟶ 6,730:
This should be placed in a file named ''quickSort.m''.
<
if numel(array) <= 1 %If the array has 1 element then it can't be sorted
Line 1,752 ⟶ 6,750:
sortedArray = [quickSort(less) pivot quickSort(greater)];
end</
A slightly more vectorized version of the above code that removes the need for the ''less'' and ''greater'' arrays:
<
if numel(array) <= 1 %If the array has 1 element then it can't be sorted
Line 1,767 ⟶ 6,765:
sortedArray = [quickSort( array(array <= pivot) ) pivot quickSort( array(array > pivot) )];
end</
Sample usage:
<
ans =
-2 1 3 4 7 9</
=={{header|MAXScript}}==
<
(
less = #()
Line 1,804 ⟶ 6,802:
)
a = #(4, 89, -3, 42, 5, 0, 2, 889)
a = quickSort a</
=={{header|Mercury}}==
=== A quicksort that works on linked lists ===
{{works with|Mercury|22.01.1}}
<syntaxhighlight lang="mercury">%%%-------------------------------------------------------------------
:- module quicksort_task_for_lists.
:- interface.
:- import_module io.
:- pred main(io, io).
:- mode main(di, uo) is det.
:- implementation.
:- import_module int.
:- import_module list.
%%%-------------------------------------------------------------------
%%%
%%% Partitioning a list into three:
%%%
%%% Left elements less than the pivot
%%% Middle elements equal to the pivot
%%% Right elements greater than the pivot
%%%
%%% The implementation is tail-recursive.
%%%
:- pred partition(comparison_func(T), T, list(T),
list(T), list(T), list(T)).
:- mode partition(in, in, in, out, out, out) is det.
partition(Compare, Pivot, Lst, Left, Middle, Right) :-
partition(Compare, Pivot, Lst, [], Left, [], Middle, [], Right).
:- pred partition(comparison_func(T), T, list(T),
list(T), list(T),
list(T), list(T),
list(T), list(T)).
:- mode partition(in, in, in,
in, out,
in, out,
in, out) is det.
partition(_, _, [], Left0, Left, Middle0, Middle, Right0, Right) :-
Left = Left0,
Middle = Middle0,
Right = Right0.
partition(Compare, Pivot, [Head | Tail], Left0, Left,
Middle0, Middle, Right0, Right) :-
Compare(Head, Pivot) = Cmp,
(if (Cmp = (<))
then partition(Compare, Pivot, Tail,
[Head | Left0], Left,
Middle0, Middle,
Right0, Right)
else if (Cmp = (=))
then partition(Compare, Pivot, Tail,
Left0, Left,
[Head | Middle0], Middle,
Right0, Right)
else partition(Compare, Pivot, Tail,
Left0, Left,
Middle0, Middle,
[Head | Right0], Right)).
%%%-------------------------------------------------------------------
%%%
%%% Quicksort using the first element as pivot.
%%%
%%% This is not the world's best choice of pivot, but it is the
%%% easiest one to get from a linked list.
%%%
%%% This implementation is *not* tail-recursive--as most quicksort
%%% implementations also are not. (However, do an online search on
%%% "quicksort fortran 77" and you will find some "tail-recursive"
%%% implementations, with the tail recursions expressed as gotos.)
%%%
:- func quicksort(comparison_func(T), list(T)) = list(T).
quicksort(_, []) = [].
quicksort(Compare, [Pivot | Tail]) = Sorted_Lst :-
partition(Compare, Pivot, Tail, Left, Middle, Right),
quicksort(Compare, Left) = Sorted_Left,
quicksort(Compare, Right) = Sorted_Right,
Sorted_Left ++ [Pivot | Middle] ++ Sorted_Right = Sorted_Lst.
%%%-------------------------------------------------------------------
:- func example_numbers = list(int).
example_numbers = [1, 3, 9, 5, 8, 6, 5, 1, 7, 9, 8, 6, 4, 2].
:- func int_compare(int, int) = comparison_result.
int_compare(I, J) = Cmp :-
if (I < J) then (Cmp = (<))
else if (I = J) then (Cmp = (=))
else (Cmp = (>)).
main(!IO) :-
quicksort(int_compare, example_numbers) = Sorted_Numbers,
print("unsorted: ", !IO),
print_line(example_numbers, !IO),
print("sorted: ", !IO),
print_line(Sorted_Numbers, !IO).
%%%-------------------------------------------------------------------
%%% local variables:
%%% mode: mercury
%%% prolog-indent-width: 2
%%% end:</syntaxhighlight>
{{out}}
<pre>$ mmc quicksort_task_for_lists.m && ./quicksort_task_for_lists
unsorted: [1, 3, 9, 5, 8, 6, 5, 1, 7, 9, 8, 6, 4, 2]
sorted: [1, 1, 2, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9]</pre>
=== A quicksort that works on arrays ===
{{works with|Mercury|22.01.1}}
The in-place partitioning algorithm here is similar to but not quite the same as that of the task pseudocode. I wrote it by referring to some Fortran code I wrote several months ago for a quickselect. (That quickselect had a random pivot, however.)
<syntaxhighlight lang="mercury">%%%-------------------------------------------------------------------
:- module quicksort_task_for_arrays.
:- interface.
:- import_module io.
:- pred main(io, io).
:- mode main(di, uo) is det.
:- implementation.
:- import_module array.
:- import_module int.
:- import_module list.
%%%-------------------------------------------------------------------
%%%
%%% Partitioning a subarray into two halves: one with elements less
%%% than or equal to a pivot, the other with elements greater than or
%%% equal to a pivot.
%%%
%%% The implementation is tail-recursive.
%%%
:- pred partition(pred(T, T), T, int, int, array(T), array(T), int).
:- mode partition(pred(in, in) is semidet, in, in, in,
array_di, array_uo, out).
partition(Less_than, Pivot, I_first, I_last, Arr0, Arr, I_pivot) :-
I = I_first - 1,
J = I_last + 1,
partition_loop(Less_than, Pivot, I, J, Arr0, Arr, I_pivot).
:- pred partition_loop(pred(T, T), T, int, int,
array(T), array(T), int).
:- mode partition_loop(pred(in, in) is semidet, in, in, in,
array_di, array_uo, out).
partition_loop(Less_than, Pivot, I, J, Arr0, Arr, Pivot_index) :-
if (I = J) then (Arr = Arr0,
Pivot_index = I)
else (I1 = I + 1,
I2 = search_right(Less_than, Pivot, I1, J, Arr0),
(if (I2 = J) then (Arr = Arr0,
Pivot_index = J)
else (J1 = J - 1,
J2 = search_left(Less_than, Pivot, I2, J1, Arr0),
swap(I2, J2, Arr0, Arr1),
partition_loop(Less_than, Pivot, I2, J2, Arr1, Arr,
Pivot_index)))).
:- func search_right(pred(T, T), T, int, int, array(T)) = int.
:- mode search_right(pred(in, in) is semidet,
in, in, in, in) = out is det.
search_right(Less_than, Pivot, I, J, Arr0) = K :-
if (I = J) then (I = K)
else if Less_than(Pivot, Arr0^elem(I)) then (I = K)
else (search_right(Less_than, Pivot, I + 1, J, Arr0) = K).
:- func search_left(pred(T, T), T, int, int, array(T)) = int.
:- mode search_left(pred(in, in) is semidet,
in, in, in, in) = out is det.
search_left(Less_than, Pivot, I, J, Arr0) = K :-
if (I = J) then (J = K)
else if Less_than(Arr0^elem(J), Pivot) then (J = K)
else (search_left(Less_than, Pivot, I, J - 1, Arr0) = K).
%%%-------------------------------------------------------------------
%%%
%%% Quicksort with median of three as pivot.
%%%
%%% Like most quicksort implementations, this one is *not*
%%% tail-recursive.
%%%
%% quicksort/3 sorts an entire array.
:- pred quicksort(pred(T, T), array(T), array(T)).
:- mode quicksort(pred(in, in) is semidet, array_di, array_uo) is det.
quicksort(Less_than, Arr0, Arr) :-
bounds(Arr0, I_first, I_last),
quicksort(Less_than, I_first, I_last, Arr0, Arr).
%% quicksort/5 sorts a subarray.
:- pred quicksort(pred(T, T), int, int, array(T), array(T)).
:- mode quicksort(pred(in, in) is semidet, in, in,
array_di, array_uo) is det.
quicksort(Less_than, I_first, I_last, Arr0, Arr) :-
if (I_last - I_first >= 2)
then (median_of_three(Less_than, I_first, I_last,
Arr0, Arr1, Pivot),
%% Partition only from I_first to I_last - 1.
partition(Less_than, Pivot, I_first, I_last - 1,
Arr1, Arr2, K),
%% Now everything that is less than the pivot is to the
%% left of K.
%% Put the pivot at K, moving the element that had been there
%% to the end. If K = I_last, then this element is actually
%% garbage and will be overwritten with the pivot, which turns
%% out to be the greatest element. Otherwise, the moved
%% element is not less than the pivot and so the partitioning
%% is preserved.
Arr2^elem(K) = Elem_to_move,
(Arr2^elem(I_last) := Elem_to_move) = Arr3,
(Arr3^elem(K) := Pivot) = Arr4,
%% Sort the subarray on either side of the pivot.
quicksort(Less_than, I_first, K - 1, Arr4, Arr5),
quicksort(Less_than, K + 1, I_last, Arr5, Arr))
else if (I_last - I_first = 1) % Two elements.
then (Elem_first = Arr0^elem(I_first),
Elem_last = Arr0^elem(I_last),
(if Less_than(Elem_first, Elem_last)
then (Arr = Arr0)
else ((Arr0^elem(I_first) := Elem_last) = Arr1,
(Arr1^elem(I_last) := Elem_first) = Arr)))
else (Arr = Arr0). % Zero or one element.
%% median_of_three/6 both chooses a pivot and rearranges the array
%% elements so one may partition them from I_first to I_last - 1,
%% leaving the pivot element out of the array.
:- pred median_of_three(pred(T, T), int, int, array(T), array(T), T).
:- mode median_of_three(pred(in, in) is semidet, in, in,
array_di, array_uo, out) is det.
median_of_three(Less_than, I_first, I_last, Arr0, Arr, Pivot) :-
I_middle = I_first + ((I_last - I_first) // 2),
Elem_first = Arr0^elem(I_first),
Elem_middle = Arr0^elem(I_middle),
Elem_last = Arr0^elem(I_last),
(if pred_xor(Less_than, Less_than,
Elem_middle, Elem_first,
Elem_last, Elem_first)
then (Pivot = Elem_first,
(if Less_than(Elem_middle, Elem_last)
then (Arr1 = (Arr0^elem(I_first) := Elem_middle),
Arr = (Arr1^elem(I_middle) := Elem_last))
else (Arr = (Arr0^elem(I_first) := Elem_last))))
else if pred_xor(Less_than, Less_than,
Elem_middle, Elem_first,
Elem_middle, Elem_last)
then (Pivot = Elem_middle,
(if Less_than(Elem_first, Elem_last)
then (Arr = (Arr0^elem(I_middle) := Elem_last))
else (Arr1 = (Arr0^elem(I_first) := Elem_last),
Arr = (Arr1^elem(I_middle) := Elem_first))))
else (Pivot = Elem_last,
(if Less_than(Elem_first, Elem_middle)
then (Arr = Arr0)
else (Arr1 = (Arr0^elem(I_first) := Elem_middle),
Arr = (Arr1^elem(I_middle) := Elem_first))))).
:- pred pred_xor(pred(T, T), pred(T, T), T, T, T, T).
:- mode pred_xor(pred(in, in) is semidet,
pred(in, in) is semidet,
in, in, in, in) is semidet.
pred_xor(P, Q, W, X, Y, Z) :-
if P(W, X) then (not Q(Y, Z)) else Q(Y, Z).
%%%-------------------------------------------------------------------
:- func example_numbers = list(int).
example_numbers = [1, 3, 9, 5, 8, 6, 5, 0, 1, 7, 9, 8, 6, 4, 2, -28,
30, 31, 1, 3, 9, 5, 8, 6, 5, 1, 6, 4, 2, -28, 30,
-50, 500, -1234, 1234, 12].
main(!IO) :-
(array.from_list(example_numbers, Arr0)),
print_line("", !IO),
print_line(Arr0, !IO),
print_line("", !IO),
print_line(" |", !IO),
print_line(" V", !IO),
print_line("", !IO),
quicksort(<, Arr0, Arr1),
print_line(Arr1, !IO),
print_line("", !IO).
%%%-------------------------------------------------------------------
%%% local variables:
%%% mode: mercury
%%% prolog-indent-width: 2
%%% end:</syntaxhighlight>
{{out}}
<pre>$ mmc quicksort_task_for_arrays.m && ./quicksort_task_for_arrays
array([1, 3, 9, 5, 8, 6, 5, 0, 1, 7, 9, 8, 6, 4, 2, -28, 30, 31, 1, 3, 9, 5, 8, 6, 5, 1, 6, 4, 2, -28, 30, -50, 500, -1234, 1234, 12])
|
V
array([-1234, -50, -28, -28, 0, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 8, 8, 8, 9, 9, 9, 12, 30, 30, 31, 500, 1234])
</pre>
=={{header|MiniScript}}==
Quick implementation for Miniscript, simply goes through the list reference and swaps the positions
<syntaxhighlight lang="miniscript">Partition = function(a, low, high)
pivot = a[low]
leftwall = low
for i in range(low + 1, high)
if a[i] < pivot then
leftwall = leftwall + 1
temp = a[leftwall]
a[leftwall] = a[i]
a[i] = temp
end if
end for
temp = a[leftwall]
a[leftwall] = pivot
a[low] = temp
return leftwall
end function
QuickSort = function(a, low=null, high=null)
if not low then low = 0
if not high then high = a.len - 1
if low < high then
pivot_location = Partition(a, low, high)
QuickSort a, low, pivot_location - 1
QuickSort a, pivot_location + 1, high
end if
return a
end function
print QuickSort([3, 5, 2, 4, 1])
</syntaxhighlight>
{{out}}
<pre>[1, 2, 3, 4, 5]</pre>
=={{header|Miranda}}==
<syntaxhighlight lang="miranda">main :: [sys_message]
main = [Stdout ("Before: " ++ show testlist ++ "\n"),
Stdout ("After: " ++ show (quicksort testlist) ++ "\n")]
where testlist = [4,65,2,-31,0,99,2,83,782,1]
quicksort [] = []
quicksort [x] = [x]
quicksort xs = (quicksort less) ++ equal ++ (quicksort more)
where pivot = hd xs
less = [x | x<-xs; x<pivot]
equal = [x | x<-xs; x=pivot]
more = [x | x<-xs; x>pivot]</syntaxhighlight>
{{out}}
<pre>Before: [4,65,2,-31,0,99,2,83,782,1]
After: [-31,0,1,2,2,4,65,83,99,782]</pre>
=={{header|Modula-2}}==
Line 1,816 ⟶ 7,188:
The ISO standard for the "Generic Modula-2" language extension provides genericity without the chink, but most compilers have not implemented this extension.
<
DEFINITION MODULE QSORT;
(*#####################*)
Line 1,827 ⟶ 7,199:
Compare:CmpFuncPtrs);
END QSORT.
</
The implementation module is not visible to clients, so it may be changed without worry so long as it still implements the definition.
Line 1,833 ⟶ 7,205:
Sedgewick suggests that faster sorting will be achieved if you drop back to an insertion sort once the partitions get small.
<
IMPLEMENTATION MODULE QSORT;
(*##########################*)
Line 1,960 ⟶ 7,332:
END QSORT.
</syntaxhighlight>
=={{header|Modula-3}}==
This code is taken from libm3, which is basically Modula-3's "standard library". Note that this code uses Insertion sort when the array is less than 9 elements long.
<
PROCEDURE Sort(VAR a: ARRAY OF Elem.T; cmp := Elem.Compare);
END ArraySort.</
<
PROCEDURE Sort (VAR a: ARRAY OF Elem.T; cmp := Elem.Compare) =
Line 2,057 ⟶ 7,429:
BEGIN
END ArraySort.</
To use this generic code to sort an array of text, we create two files called TextSort.i3 and TextSort.m3, respectively.
<
<
Then, as an example:
<
IMPORT IO, TextSort;
Line 2,077 ⟶ 7,449:
IO.Put(arr[i] & "\n");
END;
END Main.</
=={{header|Mond}}==
Implements the simple quicksort algorithm.
<syntaxhighlight lang="mond">fun quicksort( arr, cmp )
{
if( arr.length() < 2 )
return arr;
if( !cmp )
cmp = ( a, b ) -> a - b;
var a = [ ], b = [ ];
var pivot = arr[0];
var len = arr.length();
for( var i = 1; i < len; ++i )
{
var item = arr[i];
if( cmp( item, pivot ) < cmp( pivot, item ) )
a.add( item );
else
b.add( item );
}
a = quicksort( a, cmp );
b = quicksort( b, cmp );
a.add( pivot );
foreach( var item in b )
a.add( item );
return a;
}</syntaxhighlight>
;Usage
<syntaxhighlight lang="mond">var array = [ 532, 16, 153, 3, 63.60, 925, 0.214 ];
var sorted = quicksort( array );
printLn( sorted );</syntaxhighlight>
{{out}}
<pre>[
0.214,
3,
16,
63.6,
153,
532,
925
]</pre>
=={{header|MUMPS}}==
Shows quicksort on a 16-element array.
<syntaxhighlight lang="mumps">
main
new collection,size
set size=16
set collection=size for i=0:1:size-1 set collection(i)=$random(size)
write "Collection to sort:",!!
zwrite collection ; This will only work on Intersystem's flavor of MUMPS
do quicksort(.collection,0,collection-1)
write:$$isSorted(.collection) !,"Collection is sorted:",!!
zwrite collection ; This will only work on Intersystem's flavor of MUMPS
q
quicksort(array,low,high)
if low<high do
. set pivot=$$partition(.array,low,high)
. do quicksort(.array,low,pivot-1)
. do quicksort(.array,pivot+1,high)
q
partition(A,p,r)
set pivot=A(r)
set i=p-1
for j=p:1:r-1 do
. i A(j)<=pivot do
. . set i=i+1
. . set helper=A(j)
. . set A(j)=A(i)
. . set A(i)=helper
set helper=A(r)
set A(r)=A(i+1)
set A(i+1)=helper
quit i+1
isSorted(array)
set sorted=1
for i=0:1:array-2 do quit:sorted=0
. for j=i+1:1:array-1 do quit:sorted=0
. . set:array(i)>array(j) sorted=0
quit sorted
</syntaxhighlight>
;Usage
<syntaxhighlight lang="mumps"> do main()</syntaxhighlight>
{{out}}
<pre>
Collection to sort:
collection=16
collection(0)=4
collection(1)=0
collection(2)=6
collection(3)=14
collection(4)=4
collection(5)=0
collection(6)=10
collection(7)=5
collection(8)=11
collection(9)=4
collection(10)=12
collection(11)=9
collection(12)=13
collection(13)=4
collection(14)=14
collection(15)=0
Collection is sorted:
collection=16
collection(0)=0
collection(1)=0
collection(2)=0
collection(3)=4
collection(4)=4
collection(5)=4
collection(6)=4
collection(7)=5
collection(8)=6
collection(9)=9
collection(10)=10
collection(11)=11
collection(12)=12
collection(13)=13
collection(14)=14
collection(15)=14
</pre>
=={{header|Nanoquery}}==
{{trans|Python}}
<syntaxhighlight lang="nanoquery">def quickSort(arr)
less = {}
pivotList = {}
more = {}
if len(arr) <= 1
return arr
else
pivot = arr[0]
for i in arr
if i < pivot
less.append(i)
else if i > pivot
more.append(i)
else
pivotList.append(i)
end
end
less = quickSort(less)
more = quickSort(more)
return less + pivotList + more
end
end</syntaxhighlight>
=={{header|Nemerle}}==
{{trans|Haskell}}
A little less clean and concise than Haskell, but essentially the same.
<
using System.Console;
using Nemerle.Collections.NList;
Line 2,104 ⟶ 7,648:
WriteLine(Qsort(several));
}
}</
=={{header|NetRexx}}==
This sample implements both the '''simple''' and '''in place''' algorithms as described in the task's description:
<
options replace format comments java crossref savelog symbols binary
Line 2,208 ⟶ 7,752:
return ixStore
</syntaxhighlight>
{{out}}
<pre>
UK London
Line 2,241 ⟶ 7,785:
=={{header|Nial}}==
<
pass,
link [
Line 2,248 ⟶ 7,792:
quicksort sublist [ > [pass,first], pass ]
]
]</
Using it.
<
=3 4 5 7 8</
=={{header|
==={{header|Procedural (in place) algorithm }} ===
<syntaxhighlight lang="nim">proc quickSortImpl[T](a: var openarray[T], start, stop: int) =
if stop - start > 0:
let pivot = a[start]
var left = start
var right = stop
while left <= right:
while cmp(a[left], pivot) < 0:
inc(left)
while cmp(a[right], pivot) > 0:
dec(right)
if left <= right:
swap(a[left], a[right])
inc(left)
dec(right)
quickSortImpl(a, start, right)
quickSortImpl(a, left, stop)
proc quickSort[T](a: var openarray[T]) =
quickSortImpl(a, 0, a.len - 1)
var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]
a.quickSort()
echo a</syntaxhighlight>
==={{header|Functional (inmmutability) algorithm }} ===
<syntaxhighlight lang="nim">import sequtils,sugar
func sorted[T](xs:seq[T]): seq[T] =
if xs.len==0: @[] else: concat(
xs[1..^1].filter(x=>x<xs[0]).sorted,
@[xs[0]],
xs[1..^1].filter(x=>x>=xs[0]).sorted
)
@[4, 65, 2, -31, 0, 99, 2, 83, 782].sorted.echo</syntaxhighlight>
{{out}}
<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>
=={{header|Nix}}==
<syntaxhighlight lang="nix">
let
qs = l:
if l == [] then []
else
with builtins;
let x = head l;
xs = tail l;
low = filter (a: a < x) xs;
high = filter (a: a >= x) xs;
in qs low ++ [x] ++ qs high;
in
qs [4 65 2 (-31) 0 99 83 782]
</syntaxhighlight>
{{out}}
<pre>[ -31 0 2 4 65 83 99 782 ]</pre>
=={{header|Oberon-2}}==
{{trans|Pascal}}
<syntaxhighlight lang="oberon2">MODULE QS;
IMPORT Out;
TYPE
TItem = INTEGER;
CONST
N = 10;
VAR
I:LONGINT;
A:ARRAY N OF INTEGER;
PROCEDURE Init(VAR A:ARRAY OF TItem);
BEGIN
A[0] := 4; A[1] := 65; A[2] := 2; A[3] := -31; A[4] := 0;
A[5] := 99; A[6] := 2; A[7] := 83; A[8] := 782; A[9] := 1;
END Init;
PROCEDURE QuickSort(VAR A:ARRAY OF TItem; Left,Right:LONGINT);
VAR
I,J:LONGINT;
Pivot,Temp:TItem;
BEGIN
I := Left;
J := Right;
Pivot := A[(Left + Right) DIV 2];
REPEAT
WHILE Pivot > A[I] DO INC(I) END;
WHILE Pivot < A[J] DO DEC(J) END;
IF I <= J THEN
Temp := A[I];
A[I] := A[J];
A[J] := Temp;
INC(I);
DEC(J);
END;
UNTIL I > J;
IF Left < J THEN QuickSort(A, Left, J) END;
IF I < Right THEN QuickSort(A, I, Right) END;
END QuickSort;
BEGIN
Init(A);
FOR I := 0 TO LEN(A)-1 DO
Out.Int(A[I], 0); Out.Char(' ');
END;
Out.Ln;
QuickSort(A, 0, LEN(A)-1);
FOR I := 0 TO LEN(A)-1 DO
Out.Int(A[I], 0); Out.Char(' ');
END;
Out.Ln;
END QS.
</syntaxhighlight>
=={{header|Objeck}}==
<
class QuickSort {
function : Main(args : String[]) ~ Nil {
Line 2,327 ⟶ 7,966:
}
}
</syntaxhighlight>
=={{header|Objective
The [http://weblog.bignerdranch.com/398-objective-c-literals-part-1/ latest XCode compiler] is assumed with [http://en.wikipedia.org/wiki/Automatic_Reference_Counting ARC] enabled.
<
if (first >= last) return;
while (left <= right) {
while (
left++;
while (
right--;
if (left <= right)
[array exchangeObjectAtIndex:left++ withObjectAtIndex:right--];
}
quicksortInPlace(array, first, right, comparator);
quicksortInPlace(array, left, last, comparator);
}
NSArray* quicksort(NSArray *unsorted, NSComparator comparator) {
NSMutableArray *a = [NSMutableArray arrayWithArray:unsorted];
quicksortInPlace(a, 0, a.count - 1, comparator);
return a;
}
Line 2,358 ⟶ 7,997:
NSArray *a = @[ @1, @3, @5, @7, @9, @8, @6, @4, @2 ];
NSLog(@"Unsorted: %@", a);
NSLog(@"Sorted: %@", quicksort(a, ^(id x, id y) { return [x compare:y]; }));
NSArray *b = @[ @"Emil", @"Peg", @"Helen", @"Juergen", @"David", @"Rick", @"Barb", @"Mike", @"Tom" ];
NSLog(@"Unsorted: %@", b);
NSLog(@"Sorted: %@", quicksort(b, ^(id x, id y) { return [x compare:y]; }));
}
return 0;
}</
{{out}}
<pre>Unsorted: (
Line 2,412 ⟶ 8,051:
=={{header|OCaml}}==
===Declarative and purely functional===
<syntaxhighlight lang="ocaml">let rec quicksort gt = function
| [] -> []
| x::xs ->
Line 2,419 ⟶ 8,061:
let _ =
quicksort (>) [4; 65; 2; -31; 0; 99; 83; 782; 1]</
The list based implementation is elegant and perspicuous, but inefficient in time (because <code>partition</code> and <code>@</code> are linear) and in space (since it creates numerous new lists along the way).
===Imperative and in place===
Using aliased array slices from the [https://c-cube.github.io/ocaml-containers/2.6/containers/CCArray_slice/index.html Containers library].
<syntaxhighlight lang="ocaml"> module Slice = CCArray_slice
let quicksort : int Array.t -> unit = fun arr ->
let rec quicksort' : int Slice.t -> unit = fun slice ->
let len = Slice.length slice in
if len > 1 then begin
let pivot = Slice.get slice (len / 2)
and i = ref 0
and j = ref (len - 1)
in
while !i < !j do
while Slice.get slice !i < pivot do incr i done;
while Slice.get slice !j > pivot do decr j done;
if !i < !j then begin
let i_val = Slice.get slice !i in
Slice.set slice !i (Slice.get slice !j);
Slice.set slice !j i_val;
incr i;
decr j;
end
done;
quicksort' (Slice.sub slice 0 !i);
quicksort' (Slice.sub slice !i (len - !i));
end
in
(* Take the array into an aliased array slice *)
Slice.full arr |> quicksort'
</syntaxhighlight>
=={{header|Octave}}==
{{trans|MATLAB}} (The MATLAB version works as is in Octave, provided that the code is put in a file named <tt>quicksort.m</tt>, and everything below the <tt>return</tt> must be typed in the prompt of course)
<
f = v; n=length(v);
if(n > 1)
Line 2,435 ⟶ 8,116:
N=30; v=rand(N,1); tic,u=quicksort(v); toc
u</
=={{header|Oforth}}==
Oforth built-in sort uses quick sort algorithm (see lang/collect/ListBuffer.of for implementation) :
<syntaxhighlight lang="oforth">[ 5, 8, 2, 3, 4, 1 ] sort</syntaxhighlight>
=={{header|Ol}}==
<syntaxhighlight lang="scheme">
(define (quicksort l ??)
(if (null? l)
'()
(append (quicksort (filter (lambda (x) (?? (car l) x)) (cdr l)) ??)
(list (car l))
(quicksort (filter (lambda (x) (not (?? (car l) x))) (cdr l)) ??))))
(print
(quicksort (list 1 3 5 9 8 6 4 3 2) >))
(print
(quicksort (iota 100) >))
(print
(quicksort (iota 100) <))
</syntaxhighlight>
{{Out}}
<pre>
(1 2 3 3 4 5 6 8 9)
(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99)
(99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0)
</pre>
=={{header|ooRexx}}==
{{trans|Python}}
<syntaxhighlight lang="oorexx"> a = .array~Of(4, 65, 2, -31, 0, 99, 83, 782, 1)
say 'before:' a~toString( ,', ')
a = quickSort(a)
say ' after:' a~toString( ,', ')
exit
Line 2,465 ⟶ 8,175:
more = quickSort(more)
return less~~appendAll(pivotList)~~appendAll(more)
end</
{{out}}
<pre>before: 4, 65, 2, -31, 0, 99, 83, 782, 1
after: -31, 0, 1, 2, 4, 65, 83, 99, 782 </pre>
=={{header|Oz}}==
<
fun {QuickSort Xs}
case Xs of nil then nil
Line 2,480 ⟶ 8,193:
end
in
{Show {QuickSort [3 1 4 1 5 9 2 6 5]}}</
=={{header|PARI/GP}}==
<
if(#v<2, return(v));
my(less=List(),more=List(),same=List(),pivot);
Line 2,497 ⟶ 8,210:
median(v)={
vecsort(v)[#v>>1]
};</
=={{header|Pascal}}==
{{works with|FPC}}
<syntaxhighlight lang="pascal">
program QSortDemo;
{$mode objfpc}{$h+}{$b-}
procedure QuickSort(var A: array of Integer);
procedure QSort(L, R: Integer);
var
I, J, Tmp, Pivot: Integer;
{$push}{$q-}{$r-}Pivot := A[(L + R) shr 1];{$pop}
A[J] := Tmp;
Inc(I); Dec(J);
end;
until I > J;
QSort(L, J);
QSort(I, R);
end;
begin
QSort(0, High(A));
end;
procedure PrintArray(const A: array of Integer);
var
I: Integer;
begin
Write('[');
for I := 0 to High(A) - 1 do
Write(A[I], ', ');
WriteLn(A[High(A)], ']');
end;
var
a: array[-7..6] of Integer = (-34, -20, 30, 13, 36, -10, 5, -25, 9, 19, 35, -50, 29, 11);
begin
QuickSort(a);
PrintArray(a);
end.
</syntaxhighlight>
{{out}}
<pre>
[-50, -34, -25, -20, -10, 5, 9, 11, 13, 19, 29, 30, 35, 36]
</pre>
=={{header|Perl}}==
<
sub quick_sort {
quick_sort(grep $_ < $p, @_), $p, quick_sort(grep $_ >= $p, @_);
}
Line 2,538 ⟶ 8,277:
@a = quick_sort @a;
print "@a\n";
</syntaxhighlight>
=={{header|
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">quick_sort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">--
-- put x into ascending order using recursive quick sort
--</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">x</span> <span style="color: #000080;font-style:italic;">-- already sorted (trivial case)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">mid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">((</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">last</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">midval</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mid</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mid</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">xi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">xi</span><span style="color: #0000FF;"><</span><span style="color: #000000;">midval</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">last</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">last</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">last</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">xi</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">quick_sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">..</span><span style="color: #000000;">last</span><span style="color: #0000FF;">])</span> <span style="color: #0000FF;">&</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">midval</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">quick_sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">last</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">n</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">quick_sort</span><span style="color: #0000FF;">({</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"oranges"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"and"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"apples"</span><span style="color: #0000FF;">})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
{3,5,"and","apples","oranges"}
</pre>
=={{header|PHP}}==
<
$
if(count($arr) < 2){
return $arr;
Line 2,565 ⟶ 8,325:
foreach($arr as $val){
if($val <= $pivot){
$
}
$gt[] = $val;
}
}
return array_merge(quicksort($
}
$arr = array(1, 3, 5, 7, 9, 8, 6, 4, 2);
$arr = quicksort($arr);
echo implode(',',$arr);</
<pre>1,2,3,4,5,6,7,8,9</pre>
<syntaxhighlight lang="php">
function quickSort(array $array) {
// base case
if (empty($array)) {
return $array;
}
$head = array_shift($array);
$tail = $array;
$lesser = array_filter($tail, function ($item) use ($head) {
return $item <= $head;
});
$bigger = array_filter($tail, function ($item) use ($head) {
return $item > $head;
});
return array_merge(quickSort($lesser), [$head], quickSort($bigger));
}
$testCase = [1, 4, 8, 2, 8, 0, 2, 8];
$result = quickSort($testCase);
echo sprintf("[%s] ==> [%s]\n", implode(', ', $testCase), implode(', ', $result));
</syntaxhighlight>
<pre>[1, 4, 8, 2, 8, 0, 2, 8] ==> [0, 1, 2, 2, 4, 8, 8, 8]</pre>
=={{header|Picat}}==
===Function===
<syntaxhighlight lang="picat">qsort([]) = [].
qsort([H|T]) = qsort([E : E in T, E =< H])
++ [H] ++
qsort([E : E in T, E > H]).</syntaxhighlight>
===Recursion===
{{trans|Prolog}}
<syntaxhighlight lang="picat">qsort( [], [] ).
qsort( [H|U], S ) :-
splitBy(H, U, L, R),
qsort(L, SL),
qsort(R, SR),
append(SL, [H|SR], S).
% splitBy( H, U, LS, RS )
% True if LS = { L in U | L <= H }; RS = { R in U | R > H }
splitBy( _, [], [], []).
splitBy( H, [U|T], [U|LS], RS ) :- U =< H, splitBy(H, T, LS, RS).
splitBy( H, [U|T], LS, [U|RS] ) :- U > H, splitBy(H, T, LS, RS).</syntaxhighlight>
=={{header|PicoLisp}}==
<
(if (cdr L)
(let Pivot (car L)
Line 2,585 ⟶ 8,389:
(filter '((A) (= A Pivot)) L )
(quicksort (filter '((A) (> A Pivot)) (cdr L)))) )
L) )</
=={{header|PL/I}}==
<
QUICKSORT: PROCEDURE (A,AMIN,AMAX,N) RECURSIVE ;
Line 2,636 ⟶ 8,440:
END MINMAX;
CALL MINMAX(A,AMIN,AMAX,N);
CALL QUICKSORT(A,AMIN,AMAX,N);</
=={{header|PowerShell}}==
===First solution===
<syntaxhighlight lang="powershell">Function SortThree( [Array] $data )
{
if( $data[ 0 ] -gt $data[ 1 ] )
Line 2,690 ⟶ 8,496:
QuickSort 'e','c','a','b','d'
QuickSort 0.5,0.3,0.1,0.2,0.4
$l = 100; QuickSort ( 1..$l | ForEach-Object { $Rand = New-Object Random }{ $Rand.Next( 0, $l - 1 ) } )</
===Another solution===
<syntaxhighlight lang="powershell">
function quicksort($array) {
$less, $equal, $greater = @(), @(), @()
if( $array.Count -gt 1 ) {
$pivot = $array[0]
foreach( $x in $array) {
if($x -lt $pivot) { $less += @($x) }
elseif ($x -eq $pivot) { $equal += @($x)}
else { $greater += @($x) }
}
$array = (@(quicksort $less) + @($equal) + @(quicksort $greater))
}
$array
}
$array = @(60, 21, 19, 36, 63, 8, 100, 80, 3, 87, 11)
"$(quicksort $array)"
</syntaxhighlight>
<pre>The output is: 3 8 11 19 21 36 60 63 80 87 100</pre>
===Yet another solution===
<syntaxhighlight lang="powershell">
function quicksort($in) {
$n = $in.count
switch ($n) {
0 {}
1 { $in[0] }
2 { if ($in[0] -lt $in[1]) {$in[0], $in[1]} else {$in[1], $in[0]} }
default {
$pivot = $in | get-random
$lt = $in | ? {$_ -lt $pivot}
$eq = $in | ? {$_ -eq $pivot}
$gt = $in | ? {$_ -gt $pivot}
@(quicksort $lt) + @($eq) + @(quicksort $gt)
}
}
}
</syntaxhighlight>
=={{header|Prolog}}==
<
qsort( [H|U], S ) :- splitBy(H, U, L, R), qsort(L, SL), qsort(R, SR), append(SL, [H|SR], S).
Line 2,701 ⟶ 8,548:
splitBy( H, [U|T], [U|LS], RS ) :- U =< H, splitBy(H, T, LS, RS).
splitBy( H, [U|T], LS, [U|RS] ) :- U > H, splitBy(H, T, LS, RS).
</syntaxhighlight>
=={{header|
<syntaxhighlight lang="python">def quick_sort(sequence):
lesser = []
equal = []
if len(sequence) <= 1:
return sequence
pivot = sequence[0]
for element in sequence:
if element < pivot:
lesser.append(element)
greater.append(element)
else:
equal.append(element)
lesser = quick_sort(lesser)
greater = quick_sort(greater)
return lesser + equal + greater
a = [4, 65, 2, -31, 0, 99, 83, 782, 1]
a =
</syntaxhighlight>
In a Haskell fashion --
<
return (qsort([y for y in L[1:] if y < L[0]]) +
[L[
qsort([y for y in L[1:] if y >= L[0]])) if len(L) > 1 else L</
More readable, but still using list comprehensions:
<
if not list:
return []
else:
pivot = list[0]
less = [x for x in list
more = [x for x in list[1:] if x >= pivot]
return qsort(less) + [pivot] + qsort(more)</
More correctly in some tests:
<syntaxhighlight lang="python">from random import *
def qSort(a):
if len(a) <= 1:
return a
else:
q = choice(a)
return qSort([elem for elem in a if elem < q]) + [q] * a.count(q) + qSort([elem for elem in a if elem > q])</syntaxhighlight>
<syntaxhighlight lang="python">def quickSort(a):
if len(a) <= 1:
return a
else:
less = []
more = []
pivot = choice(a)
for i in a:
if i < pivot:
less.append(i)
if i > pivot:
more.append(i)
less = quickSort(less)
more = quickSort(more)
return less + [pivot] * a.count(pivot) + more</syntaxhighlight>
Returning a new list:
<syntaxhighlight lang="python">def qsort(array):
if len(array) < 2:
return array
head, *tail = array
less = qsort([i for i in tail if i < head])
more = qsort([i for i in tail if i >= head])
return less + [head] + more</syntaxhighlight>
Sorting a list in place:
<syntaxhighlight lang="python">def quicksort(array):
_quicksort(array, 0, len(array) - 1)
def _quicksort(array, start, stop):
if stop - start > 0:
pivot, left, right = array[start], start, stop
while left <= right:
while array[left] < pivot:
left += 1
while array[right] > pivot:
right -= 1
if left <= right:
array[left], array[right] = array[right], array[left]
left += 1
right -= 1
_quicksort(array, start, right)
_quicksort(array, left, stop)</syntaxhighlight>
Functional Style (no for or while loops, constants only):
<syntaxhighlight lang="python">
def quicksort(unsorted_list):
if len(unsorted_list) == 0:
return ()
pivot = unsorted_list[0]
less = filter(lambda x: x < pivot, unsorted_list)
same = filter(lambda x: x == pivot, unsorted_list)
more = filter(lambda x: x > pivot, unsorted_list)
return quicksort(less) + same + quicksort(more)
</syntaxhighlight>
=={{header|Qi}}==
<
_ [] -> []
Pred [A|Rest] -> [A | (keep Pred Rest)] where (Pred A)
Line 2,794 ⟶ 8,674:
(quicksort [6 8 5 9 3 2 2 1 4 7])
</syntaxhighlight>
=={{header|Quackery}}==
Sort a nest of numbers.
<syntaxhighlight lang="quackery">[ stack ] is less ( --> s )
[ stack ] is same ( --> s )
[ stack ] is more ( --> s )
[ - -1 1 clamp 1+ ] is <=> ( n n --> n )
[ tuck take join swap put ] is append ( x s --> )
[ dup size 2 < if done
[] less put
[] same put
[] more put
behead swap witheach
[ 2dup swap <=>
[ table less same more ]
append ]
same append
less take recurse
same take join
more take recurse join ] is quicksort ( [ --> [ )
[] 10 times [ i^ join ] 3 of
dup echo cr
quicksort echo cr</syntaxhighlight>
'''Output:'''
<pre>[ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 ]
[ 0 0 0 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 ]</pre>
=={{header|R}}==
{{trans|Octave}}
<
if ( length(v) > 1 )
{
Line 2,809 ⟶ 8,725:
vs <- runif(N)
system.time(u <- qsort(vs))
print(u)</
=={{header|Racket}}==
<
(define (quicksort
(match
['() '(
(let-values ([(xs-gte xs-lt) (partition (curry < x) xs)])
(append (quicksort
(list x)
Examples
<
;returns '(2 3 4 5 6 7 8)
(quicksort string<? '("
;returns '("Bubblesort" "Mergesort" "Quicksort")</
=={{header|
<syntaxhighlight lang="raku" line>
#| 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})
}
</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(\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}}==
<syntaxhighlight lang="red">
Red []
;;-------------------------------
;; we have to use function not func here, otherwise we'd have to define all "vars" as local...
qsort: function [list][
;;-------------------------------
if 1 >= length? list [ return list ]
left: copy []
right: copy []
eq: copy [] ;; "equal"
pivot: list/2 ;; simply choose second element as pivot element
foreach ele list [
case [
ele < pivot [ append left ele ]
ele > pivot [ append right ele ]
true [append eq ele ]
]
]
;; this is the last expression of the function, so coding "return" here is not necessary
reduce [qsort left eq qsort right]
]
;; lets test the function with an array of 100k integers, range 1..1000
list: []
loop 100000 [append list random 1000]
t0: now/time/precise ;; start timestamp
qsort list ;; the return value (block) contains the sorted list, original list has not changed
print ["time1: " now/time/precise - t0] ;; about 1.1 sec on my machine
t0: now/time/precise
sort list ;; just for fun time the builtin function also ( also implementation of quicksort )
print ["time2: " now/time/precise - t0]
</syntaxhighlight>
=={{header|REXX}}==
===version 1===
This REXX version doesn't use or modify the program stack.
It is over '''400%''' times faster then the 2<sup>nd</sup> REXX version (using the exact same random numbers).
<syntaxhighlight lang="rexx">/*REXX program sorts a stemmed array using the quicksort algorithm. */
call gen@ /*generate the elements for the array. */
call show@ 'before sort' /*show the before array elements. */
call qSort # /*invoke the quicksort subroutine. */
call show@ ' after sort' /*show the after array elements. */
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
inOrder: parse arg n; do j=1 for n-1; k= j+1; if @.j>@.k then return 0; end; return 1
/*──────────────────────────────────────────────────────────────────────────────────────*/
qSort: procedure expose @.; a.1=1; parse arg b.1; $= 1 /*access @.; get @. size; pivot.*/
if inOrder(b.1) then return /*Array already in order? Return*/
do while $\==0; L= a.$; t= b.$; $= $ - 1; if t<2 then iterate
H= L + t - 1; ?= L + t % 2
if @.H<@.L then if @.?<@.H then do; p= @.H; @.H= @.L; end
else if @.?>@.L then p= @.L
else do; p= @.?; @.?= @.L; end
else if @.?<@.L then p=@.L
else if @.?>@.H then do; p= @.H; @.H= @.L; end
else do; p= @.?; @.?= @.L; end
j= L+1; k= h
do forever
do j=j while j<=k & @.j<=p; end /*a teeny─tiny loop.*/
do k=k by -1 while j< k & @.k>=p; end /*another " " */
if j>=k then leave /*segment finished? */
_= @.j; @.j= @.k; @.k= _ /*swap J&K elements.*/
end /*forever*/
$= $ + 1
k= j - 1; @.L= @.k; @.k= p
if j<=? then do; a.$= j; b.$= H-j+1; $= $+1; a.$= L; b.$= k-L; end
else do; a.$= L; b.$= k-L; $= $+1; a.$= j; b.$= H-j+1; end
end /*while $¬==0*/
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
show@: w= length(#); do j=1 for #; say 'element' right(j,w) arg(1)":" @.j; end
say copies('▒', maxL + w + 22) /*display a separator (between outputs)*/
return
/*──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────*/
gen@: @.=; maxL=0 /*assign a default value for the array.*/
@.1 = " Rivers that form part of a (USA) state's border " /*this value is adjusted later to include a prefix & suffix.*/
@.2 = '=' /*this value is expanded later. */
@.3 = "Perdido River Alabama, Florida"
@.4 = "Chattahoochee River Alabama, Georgia"
@.5 = "Tennessee River Alabama, Kentucky, Mississippi, Tennessee"
@.6 = "Colorado River Arizona, California, Nevada, Baja California (Mexico)"
@.7 = "Mississippi River Arkansas, Illinois, Iowa, Kentucky, Minnesota, Mississippi, Missouri, Tennessee, Louisiana, Wisconsin"
@.8 = "St. Francis River Arkansas, Missouri"
@.9 = "Poteau River Arkansas, Oklahoma"
@.10 = "Arkansas River Arkansas, Oklahoma"
@.11 = "Red River (Mississippi watershed) Arkansas, Oklahoma, Texas"
@.12 = "Byram River Connecticut, New York"
@.13 = "Pawcatuck River Connecticut, Rhode Island and Providence Plantations"
@.14 = "Delaware River Delaware, New Jersey, New York, Pennsylvania"
@.15 = "Potomac River District of Columbia, Maryland, Virginia, West Virginia"
@.16 = "St. Marys River Florida, Georgia"
@.17 = "Chattooga River Georgia, South Carolina"
@.18 = "Tugaloo River Georgia, South Carolina"
@.19 = "Savannah River Georgia, South Carolina"
@.20 = "Snake River Idaho, Oregon, Washington"
@.21 = "Wabash River Illinois, Indiana"
@.22 = "Ohio River Illinois, Indiana, Kentucky, Ohio, West Virginia"
@.23 = "Great Miami River (mouth only) Indiana, Ohio"
@.24 = "Des Moines River Iowa, Missouri"
@.25 = "Big Sioux River Iowa, South Dakota"
@.26 = "Missouri River Kansas, Iowa, Missouri, Nebraska, South Dakota"
@.27 = "Tug Fork River Kentucky, Virginia, West Virginia"
@.28 = "Big Sandy River Kentucky, West Virginia"
@.29 = "Pearl River Louisiana, Mississippi"
@.30 = "Sabine River Louisiana, Texas"
@.31 = "Monument Creek Maine, New Brunswick (Canada)"
@.32 = "St. Croix River Maine, New Brunswick (Canada)"
@.33 = "Piscataqua River Maine, New Hampshire"
@.34 = "St. Francis River Maine, Quebec (Canada)"
@.35 = "St. John River Maine, Quebec (Canada)"
@.36 = "Pocomoke River Maryland, Virginia"
@.37 = "Palmer River Massachusetts, Rhode Island and Providence Plantations"
@.38 = "Runnins River Massachusetts, Rhode Island and Providence Plantations"
@.39 = "Montreal River Michigan (upper peninsula), Wisconsin"
@.40 = "Detroit River Michigan, Ontario (Canada)"
@.41 = "St. Clair River Michigan, Ontario (Canada)"
@.42 = "St. Marys River Michigan, Ontario (Canada)"
@.43 = "Brule River Michigan, Wisconsin"
@.44 = "Menominee River Michigan, Wisconsin"
@.45 = "Red River of the North Minnesota, North Dakota"
@.46 = "Bois de Sioux River Minnesota, North Dakota, South Dakota"
@.47 = "Pigeon River Minnesota, Ontario (Canada)"
@.48 = "Rainy River Minnesota, Ontario (Canada)"
@.49 = "St. Croix River Minnesota, Wisconsin"
@.50 = "St. Louis River Minnesota, Wisconsin"
@.51 = "Halls Stream New Hampshire, Canada"
@.52 = "Salmon Falls River New Hampshire, Maine"
@.53 = "Connecticut River New Hampshire, Vermont"
@.54 = "Arthur Kill New Jersey, New York (tidal strait)"
@.55 = "Kill Van Kull New Jersey, New York (tidal strait)"
@.56 = "Hudson River (lower part only) New Jersey, New York"
@.57 = "Rio Grande New Mexico, Texas, Tamaulipas (Mexico), Nuevo Leon (Mexico), Coahuila de Zaragoza (Mexico), Chihuahua (Mexico)"
@.58 = "Niagara River New York, Ontario (Canada)"
@.59 = "St. Lawrence River New York, Ontario (Canada)"
@.60 = "Poultney River New York, Vermont"
@.61 = "Catawba River North Carolina, South Carolina"
@.62 = "Blackwater River North Carolina, Virginia"
@.63 = "Columbia River Oregon, Washington"
do #=1 until @.#=='' /*find how many entries in array, and */
maxL=max(maxL, length(@.#)) /* also find the maximum width entry.*/
end /*#*/; #= #-1 /*adjust the highest element number. */
@.1= center(@.1, maxL, '-') /* " " header information. */
@.2= copies(@.2, maxL) /* " " " separator. */
return</syntaxhighlight>
{{out|output|text= when using the internal default input:}}
<pre style="height:60ex">
element 1 before sort: ------------------------------------------------ Rivers that form part of a (USA) state's border -------------------------------------------------
element 2 before sort: ==================================================================================================================================================
element 3 before sort:
element 4 before sort:
element 5 before sort:
element 6 before sort:
element 7 before sort:
element 8 before sort:
element 9 before sort:
element 10 before sort:
element 11 before sort:
element 12 before sort:
element 13 before sort:
element 14 before sort:
element 15 before sort:
element 16 before sort:
element 17 before sort:
element 18 before sort:
element 19 before sort:
element 20 before sort:
element 21 before sort:
element 22 before sort:
element 23 before sort:
element 24 before sort:
element 25 before sort:
element 26 before sort:
element 27 before sort:
element 28 before sort:
element 29 before sort:
element 30 before sort:
element 31 before sort:
element 32 before sort:
element 33 before sort:
element 34 before sort:
element 35 before sort: St.
element 36 before sort:
element 37 before sort:
element 38 before sort:
element 39 before sort:
element 40 before sort:
element 41 before sort:
element 42 before sort:
element 43 before sort:
element 44 before sort:
element 45 before sort:
element 46 before sort:
element 47 before sort:
element 48 before sort:
element 49 before sort:
element 50 before sort:
element 51 before sort:
element 52 before sort:
element 53 before sort:
element 54 before sort:
element 55 before sort:
element 56 before sort:
element 57 before sort:
element 58 before sort:
element 59 before sort:
element 60 before sort:
element 61 before sort:
element 62 before sort: Blackwater River
element 63 before sort: Columbia River
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
element 1 after sort: ------------------------------------------------ Rivers that form part of a
element 2 after sort: ==================================================================================================================================================
element 3 after sort: Arkansas River
element 4 after sort: Arthur Kill
element 5 after sort: Big Sandy River
element 6 after sort: Big Sioux River
element 7 after sort: Blackwater River
element 8 after sort: Bois de Sioux River
element 9 after sort: Brule River
element 10 after sort: Byram River
element 11 after sort: Catawba River
element 12 after sort: Chattahoochee River
element 13 after sort: Chattooga River
element 14 after sort: Colorado River
element 15 after sort: Columbia River
element 16 after sort: Connecticut River
element 17 after sort: Delaware River
element 18 after sort: Des Moines River
element 19 after sort: Detroit River
element 20 after sort: Great Miami River (mouth only)
element 21 after sort: Halls Stream
element 22 after sort: Hudson River (lower part only)
element 23 after sort: Kill Van Kull
element 24 after sort: Menominee River
element 25 after sort: Mississippi River
element 26 after sort: Missouri River
element 27 after sort: Montreal River
element 28 after sort: Monument Creek
element 29 after sort: Niagara River
element 30 after sort: Ohio River
element 31 after sort: Palmer River
element 32 after sort: Pawcatuck River
element 33 after sort: Pearl River
element 34 after sort: Perdido River
element 35 after sort: Pigeon River
element 36 after sort: Piscataqua River
element 37 after sort: Pocomoke River
element 38 after sort: Poteau River
element 39 after sort: Potomac River
element 40 after sort: Poultney River
element 41 after sort: Rainy River
element 42 after sort: Red River (Mississippi watershed)
element 43 after sort: Red River of the North
element 44 after sort: Rio Grande
element 45 after sort: Runnins River
element 46 after sort: Sabine River
element 47 after sort: Salmon Falls River
element 48 after sort: Savannah River
element 49 after sort: Snake River
element 50 after sort: St. Clair River
element 51 after sort: St. Croix River
element 52 after sort: St. Croix River
element 53 after sort: St. Francis River
element 54 after sort: St. Francis River
element 55 after sort: St. John River
element 56 after sort: St. Lawrence River
element 57 after sort: St. Louis River
element 58 after sort: St. Marys River
element 59 after sort: St. Marys River
element 60 after sort: Tennessee River
element 61 after sort: Tug Fork River
element 62 after sort: Tugaloo River
element 63 after sort: Wabash River
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
</pre>
Line 3,085 ⟶ 9,174:
{{trans|Python}}The Python code translates very well to [[ooRexx]] but here is a way to implement it in classic REXX as well.
This REXX version doesn't handle numbers with leading/trailing/embedded blanks, or textual values that have blanks (or whitespace) in them.
<syntaxhighlight lang="rexx">
/*REXX*/
a = '4 65 2 -31 0 99 83 782 1'
do i = 1 to words(a)
queue word(a, i)
Line 3,170 ⟶ 9,262:
queue more.i
end
return</
=={{header|
<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">
# Project : Sorting algorithms/Quicksort
test = [4, 65, 2, -31, 0, 99, 2, 83, 782, 1]
see "before sort:" + nl
showarray(test)
quicksort(test, 1, 10)
see "after sort:" + nl
showarray(test)
func quicksort(a, s, n)
if n < 2
return
ok
t = s + n - 1
l = s
r = t
p = a[floor((l + r) / 2)]
while l <= r
while a[l] < p
l = l + 1
end
while a[r] > p
r = r - 1
end
if l <= r
temp = a[l]
a[l] = a[r]
a[r] = temp
l = l + 1
r = r - 1
ok
end
if s < r
quicksort(a, s, r - s + 1)
ok
if l < t
quicksort(a, l, t - l + 1 )
ok
func showarray(vect)
svect = ""
for n = 1 to len(vect)
svect = svect + vect[n] + " "
next
svect = left(svect, len(svect) - 1)
see svect + nl
</syntaxhighlight>
Output:
<pre>
before sort:
4 65 2 -31 0 99 2 83 782 1
after sort:
-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}}==
<syntaxhighlight lang="ruby">class Array
def quick_sort
return self if length <= 1
pivot = self[
less.quick_sort + [pivot] + greatereq.quick_sort
end
end</
or
<
def quick_sort
return self if length <= 1
pivot =
group[-1].quick_sort + group[0] + group[1].quick_sort
end
end</
or functionally
<syntaxhighlight lang="ruby">class Array
def quick_sort
h, *t = self
h ? t.partition { |e| e < h }.inject { |l, r| l.quick_sort + [h] + r.quick_sort } : []
end
end</syntaxhighlight>
=={{header|Rust}}==
<syntaxhighlight lang="rust">fn main() {
println!("Sort numbers in descending order");
let mut numbers = [4, 65, 2, -31, 0, 99, 2, 83, 782, 1];
println!("Before: {:?}", numbers);
quick_sort(&mut numbers, &|x,y| x > y);
println!("After: {:?}\n", numbers);
println!("Sort strings alphabetically");
let mut strings = ["beach", "hotel", "airplane", "car", "house", "art"];
println!("Before: {:?}", strings);
quick_sort(&mut strings, &|x,y| x < y);
println!("After: {:?}\n", strings);
println!("Sort strings by length");
println!("Before: {:?}", strings);
quick_sort(&mut strings, &|x,y| x.len() < y.len());
println!("After: {:?}", strings);
}
fn quick_sort<T,F>(v: &mut [T], f: &F)
where F: Fn(&T,&T) -> bool
{
let len = v.len();
if len >= 2 {
let pivot_index = partition(v, f);
quick_sort(&mut v[0..pivot_index], f);
quick_sort(&mut v[pivot_index + 1..len], f);
}
}
fn partition<T,F>(v: &mut [T], f: &F) -> usize
where F: Fn(&T,&T) -> bool
{
let len = v.len();
let pivot_index = len / 2;
let last_index = len - 1;
v.swap(pivot_index, last_index);
let mut store_index = 0;
for i in 0..last_index {
if f(&v[i], &v[last_index]) {
v.swap(i, store_index);
store_index += 1;
}
}
v.swap(store_index, len - 1);
store_index
}</syntaxhighlight>
{{out}}
<pre>Sort numbers in descending order
Before: [4, 65, 2, -31, 0, 99, 2, 83, 782, 1]
After: [782, 99, 83, 65, 4, 2, 2, 1, 0, -31]
Sort strings alphabetically
Before: ["beach", "hotel", "airplane", "car", "house", "art"]
After: ["airplane", "art", "beach", "car", "hotel", "house"]
Sort strings by length
Before: ["airplane", "art", "beach", "car", "hotel", "house"]
After: ["car", "art", "house", "hotel", "beach", "airplane"]</pre>
Or, using functional style (slower than the imperative style but faster than functional style in other languages):
<syntaxhighlight lang="rust">fn main() {
let numbers = [4, 65, 2, -31, 0, 99, 2, 83, 782, 1];
println!("{:?}\n", quick_sort(numbers.iter()));
}
fn quick_sort<T, E>(mut v: T) -> Vec<E>
where
T: Iterator<Item = E>,
E: PartialOrd,
{
match v.next() {
None => Vec::new(),
Some(pivot) => {
let (lower, higher): (Vec<_>, Vec<_>) = v.partition(|it| it < &pivot);
let lower = quick_sort(lower.into_iter());
let higher = quick_sort(higher.into_iter());
lower.into_iter()
.chain(core::iter::once(pivot))
.chain(higher.into_iter())
.collect()
}
}
}
</syntaxhighlight>
By the way this implementation needs only O(n) memory because the partition(...) call already "consumes" v. This means that the memory of v will be freed here, before the recursive calls to quick_sort(...). If we tried to use v later, we would get a compilation error.
=={{header|SASL}}==
Copied from SASL manual, Appendix II, solution (2)(b)
<syntaxhighlight lang="sasl">DEF || this rather nice solution is due to Silvio Meira
sort () = ()
sort (a : x) = sort {b <- x; b <= a } ++ a : sort { b <- x; b>a}
?</syntaxhighlight>
=={{header|Sather}}==
<
private afilter(a:ARRAY{T}, cmp:ROUT{T,T}:BOOL, p:T):ARRAY{T} is
Line 3,267 ⟶ 9,524:
a := res;
end;
end;</
<
main is
a:ARRAY{INT} := |10, 9, 8, 7, 6, -10, 5, 4, 656, -11|;
Line 3,276 ⟶ 9,533:
#OUT + a + "\n" + b.sort + "\n";
end;
end;</
The ARRAY class has a builtin sorting method, which is quicksort (but under certain condition an insertion sort is used instead), exactly <code>quicksort_range</code>; this implementation is original.
=={{header|Scala}}==
First, a quick sort of a list of integers:
<
case Nil => Nil
case head :: tail =>
val (less, notLess) = tail.partition(_ < head) // Arbitrarily partition list in two
sort(less) ++ (head :: sort(notLess)) // Sort each half
}</syntaxhighlight>
Next, a quick sort of a list of some type T, given a lessThan function:
<
case Nil => Nil
val (lo, hi) = xx.partition(lessThan(_, x))
}</syntaxhighlight>
To take advantage of known orderings, a quick sort of a list of some type T,
for which exists an implicit (or explicit)
<
case Nil => Nil
val (lo, hi) = xx.partition(ord.lt(_, x))
sort[T](lo) ++ (x :: sort[T](hi))
}</syntaxhighlight>
That last one could have worked with Ordering, but Ordering is Java, and doesn't have
the less than operator. Ordered is Scala-specific, and provides it.
<syntaxhighlight lang="scala"> def sort[T <: Ordered[T]](xs: List[T]): List[T] = xs match {
case Nil => Nil
case x :: xx =>
val (lo, hi) = xx.partition(_ < x)
sort(lo) ++ (x :: sort(hi))
}</syntaxhighlight>
What hasn't changed in all these examples is ordering a list. It is possible
to write a generic quicksort in Scala, which will order any kind of collection. To do
so, however, requires that the type of the collection, itself, be made a parameter to
the function. Let's see it below, and then remark upon it:
<syntaxhighlight lang="scala"> def sort[T, C[T] <: scala.collection.TraversableLike[T, C[T]]]
(xs: C[T])
(implicit ord: scala.math.Ordering[T],
// Some collection types can't pattern match
if (
} else {
val (
val b = cbf()
b.sizeHint(xs.size)
b ++= sort(lo)
b += xs.head
b ++= sort(hi)
b.result()
}
}</syntaxhighlight>
by providing
of
and TraversableLike is a trait which contains the implementation of most Traversable
methods.
We need another parameter, though, which is a factory capable of building a
That is being passed implicitly, so callers to this method do not need to provide them, as
the collection they are using should already provide one as such
which provides it cannot be used in conjunction with implicit parameters.
The body of the function is
collection types don't support pattern matching, "+:" or "::".
=={{header|Scheme}}==
=== List quicksort ===
<syntaxhighlight lang="scheme">(define (split-by l p k)
(let loop ((low '())
(high '())
Line 3,382 ⟶ 9,643:
(quicksort high gt?))))))
(quicksort '(1 3 5 7 9 8 6 4 2) >)</
With srfi-1:
<
(if (null? l)
'()
Line 3,393 ⟶ 9,654:
(quicksort '(1 3 5 7 9 8 6 4 2) >)
</syntaxhighlight>
=== Vector quicksort (in place) ===
{{works with|Chibi Scheme}}
{{works with|Gauche Scheme}}
{{works with|CHICKEN Scheme|5.3.0}}
For CHICKEN:{{libheader|r7rs}}
<syntaxhighlight lang="scheme">;;;-------------------------------------------------------------------
;;;
;;; Quicksort in R7RS Scheme, working in-place on vectors (that is,
;;; arrays). I closely follow the "better quicksort algorithm"
;;; pseudocode, and thus the code is more "procedural" than
;;; "functional".
;;;
;;; I use a random pivot. If you can generate a random number quickly,
;;; this is a good method, but for this demonstration I have taken a
;;; fast linear congruential generator and made it brutally slow. It's
;;; just a demonstration. :)
;;;
(import (scheme base))
(import (scheme case-lambda))
(import (scheme write))
;;;-------------------------------------------------------------------
;;;
;;; Add "while" loops to the language.
;;;
(define-syntax while
(syntax-rules ()
((_ pred? body ...)
(let loop ()
(when pred?
(begin body ...)
(loop))))))
;;;-------------------------------------------------------------------
;;;
;;; In-place quicksort.
;;;
(define vector-quicksort!
(case-lambda
;; Use a default pivot selector.
((<? vec)
;; Random pivot.
(vector-quicksort! (lambda (vec i-first i-last)
(vector-ref vec (randint i-first i-last)))
<? vec))
;; Specify a pivot selector.
((pivot-select <? vec)
;;
;; The recursion:
;;
(let quicksort! ((i-first 0)
(i-last (- (vector-length vec) 1)))
(let ((n (- i-last i-first -1)))
(when (> n 1)
(let* ((pivot (pivot-select vec i-first i-last)))
(let ((left i-first)
(right i-last))
(while (<= left right)
(while (< (vector-ref vec left) pivot)
(set! left (+ left 1)))
(while (> (vector-ref vec right) pivot)
(set! right (- right 1)))
(when (<= left right)
(let ((lft (vector-ref vec left))
(rgt (vector-ref vec right)))
(vector-set! vec left rgt)
(vector-set! vec right lft)
(set! left (+ left 1))
(set! right (- right 1)))))
(quicksort! i-first right)
(quicksort! left i-last)))))))))
;;;-------------------------------------------------------------------
;;;
;;; A simple linear congruential generator, attributed by
;;; https://en.wikipedia.org/w/index.php?title=Linear_congruential_generator&oldid=1083800601
;;; to glibc and GCC. No attempt has been made to optimize this code.
;;;
(define seed 1)
(define two**31 (expt 2 31))
(define (random-integer)
(let* ((s0 seed)
(s1 (truncate-remainder (+ (* 1103515245 s0) 12345)
two**31)))
(set! seed s1)
s0))
(define randint
(case-lambda
((n) (truncate-remainder (random-integer) n))
((i-first i-last) (+ i-first (randint (- i-last i-first -1))))))
;;;-------------------------------------------------------------------
;;;
;;; A demonstration of in-place vector quicksort.
;;;
(define vec1 (vector-copy #(60 53 100 72 19 67 14
31 4 1 5 9 2 6 5 3 5 8
28 9 95 22 67 55 20 41
42 29 20 74 39)))
(vector-quicksort! < vec1)
(write vec1)
(newline)
;;;-------------------------------------------------------------------</syntaxhighlight>
{{out}}
<pre>$ gosh vector-quicksort.scm
#(1 2 3 4 5 5 5 6 8 9 9 14 19 20 20 22 28 29 31 39 41 42 53 55 60 67 67 72 74 95 100)</pre>
=={{header|Seed7}}==
<
local
var elemType: compare_elem is elemType.value;
Line 3,430 ⟶ 9,810:
begin
quickSort(arr, 1, length(arr));
end func;</
Original source: [http://seed7.sourceforge.net/algorith/sorting.htm#quickSort]
=={{header|SETL}}==
In-place sort (looks much the same as the C version)
<
qsort(a);
print(a);
Line 3,456 ⟶ 9,836:
proc swap(rw x, rw y);
[y,x] := [x,y];
end proc;</
Copying sort using comprehensions:
<
print(qsort(a));
Line 3,471 ⟶ 9,851:
end if;
return a;
end proc;</
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">func quicksort (a) {
a.len < 2 && return(a);
var p = a.pop_rand; # to avoid the worst cases
__FUNC__(a.grep{ .< p}) + [p] + __FUNC__(a.grep{ .>= p});
}</syntaxhighlight>
=={{header|Simula}}==
<syntaxhighlight lang="simula">PROCEDURE QUICKSORT(A); REAL ARRAY A;
BEGIN
PROCEDURE QS(A, FIRST, LAST); REAL ARRAY A; INTEGER FIRST, LAST;
BEGIN
INTEGER LEFT, RIGHT;
LEFT := FIRST; RIGHT := LAST;
IF RIGHT - LEFT + 1 > 1 THEN
BEGIN
REAL PIVOT;
PIVOT := A((LEFT + RIGHT) // 2);
WHILE LEFT <= RIGHT DO
BEGIN
WHILE A(LEFT) < PIVOT DO LEFT := LEFT + 1;
WHILE A(RIGHT) > PIVOT DO RIGHT := RIGHT - 1;
IF LEFT <= RIGHT THEN
BEGIN
REAL SWAP;
SWAP := A(LEFT); A(LEFT) := A(RIGHT); A(RIGHT) := SWAP;
LEFT := LEFT + 1; RIGHT := RIGHT - 1;
END;
END;
QS(A, FIRST, RIGHT);
QS(A, LEFT, LAST);
END;
END QS;
QS(A, LOWERBOUND(A, 1), UPPERBOUND(A, 1));
END QUICKSORT;
</syntaxhighlight>
=={{header|Standard ML}}==
<
| quicksort (x::xs) =
let
Line 3,480 ⟶ 9,900:
in
quicksort left @ [x] @ quicksort right
end
</syntaxhighlight>
------------------------------------------------------------
Solution 2:
Without using List.partition
<syntaxhighlight lang="sml">
fun par_helper([], x, l, r) = (l, r)
| par_helper(h::t, x, l, r) =
if h <= x then
par_helper(t, x, l @ [h], r)
else
par_helper(t, x, l, r @ [h]);
fun par(l, x) = par_helper(l, x, [], []);
fun quicksort [] = []
| quicksort (h::t) =
let
val (left, right) = par(t, h)
in
quicksort left @ [h] @ quicksort right
end;</syntaxhighlight>
=={{header|Swift}}==
<syntaxhighlight lang="swift">func quicksort<T where T : Comparable>(inout elements: [T], range: Range<Int>) {
if (range.endIndex - range.startIndex > 1) {
let pivotIndex = partition(&elements, range)
quicksort(&elements, range.startIndex ..< pivotIndex)
quicksort(&elements, pivotIndex+1 ..< range.endIndex)
}
}
func quicksort<T where T : Comparable>(inout elements: [T]) {
quicksort(&elements, indices(elements))
}</syntaxhighlight>
=={{header|Symsyn}}==
<syntaxhighlight lang="symsyn">
x : 23 : 15 : 99 : 146 : 3 : 66 : 71 : 5 : 23 : 73 : 19
quicksort param l r
l i
r j
((l+r) shr 1) k
x.k pivot
repeat
if pivot > x.i
+ cmp
+ i
goif
endif
if pivot < x.j
+ cmp
- j
goif
endif
if i <= j
swap x.i x.j
- j
+ i
endif
if i <= j
go repeat
endif
if l < j
save l r i j
call quicksort l j
restore l r i j
endif
if i < r
save l r i j
call quicksort i r
restore l r i j
endif
return
start
' original values : ' $r
call showvalues
call quicksort 0 10
' sorted values : ' $r
call showvalues
stop
showvalues
$s
i
if i <= 10
"$s ' ' x.i ' '" $s
+ i
goif
endif
" $r $s " []
return
</syntaxhighlight>
=={{header|Tailspin}}==
Simple recursive quicksort:
<syntaxhighlight lang="tailspin">
templates quicksort
@: [];
$ -> #
when <[](2..)> do
def pivot: $(1);
[ [ $(2..last)... -> \(
when <..$pivot> do
$ !
otherwise
..|@quicksort: $;
\)] -> quicksort..., $pivot, $@ -> quicksort... ] !
otherwise
$ !
end quicksort
[4,5,3,8,1,2,6,7,9,8,5] -> quicksort -> !OUT::write
</syntaxhighlight>
In place:
<syntaxhighlight lang="tailspin">
templates quicksort
templates partial
def first: $(1);
def last: $(2);
def pivot: $@quicksort($first);
@: $(1) + 1;
$(2) -> #
when <..~$@> do
def limit: $;
@quicksort($first): $@quicksort($limit);
@quicksort($limit): $pivot;
[ $first, $limit - 1 ] !
[ $limit + 1, $last ] !
when <?($@quicksort($) <$pivot~..>)> do
$ - 1 -> #
when <?($@quicksort($@) <..$pivot>)> do
@: $@ + 1; $ -> #
otherwise
def temp: $@quicksort($@);
@quicksort($@): $@quicksort($);
@quicksort($): $temp;
@: $@ + 1; $ - 1 -> #
end partial
@: $;
[1, $@::length] -> #
$@ !
when <?($(1) <..~$(2)>)> do
$ -> partial -> #
end quicksort
[4,5,3,8,1,2,6,7,9,8,5] -> quicksort -> !OUT::write
</syntaxhighlight>
=={{header|Tcl}}==
<
proc quicksort {m} {
Line 3,497 ⟶ 10,091:
}
puts [quicksort {8 6 4 2 1 3 5 7 9}] ;# => 1 2 3 4 5 6 7 8 9</
=={{header|TypeScript}}==
<syntaxhighlight lang="text">
/**
Generic quicksort function using typescript generics.
Follows quicksort as done in CLRS.
*/
export type Comparator<T> = (o1: T, o2: T) => number;
export function quickSort<T>(array: T[], compare: Comparator<T>) {
if (array.length <= 1 || array == null) {
return;
}
sort(array, compare, 0, array.length - 1);
}
function sort<T>(
array: T[], compare: Comparator<T>, low: number, high: number) {
if (low < high) {
const partIndex = partition(array, compare, low, high);
sort(array, compare, low, partIndex - 1);
sort(array, compare, partIndex + 1, high);
}
}
function partition<T>(
array: T[], compare: Comparator<T>, low: number, high: number): number {
const pivot: T = array[high];
let i: number = low - 1;
for (let j = low; j <= high - 1; j++) {
if (compare(array[j], pivot) == -1) {
i = i + 1;
swap(array, i, j)
}
}
if (compare(array[high], array[i + 1]) == -1) {
swap(array, i + 1, high);
}
return i + 1;
}
function swap<T>(array: T[], i: number, j: number) {
const newJ: T = array[i];
array[i] = array[j];
array[j] = newJ;
}
export function testQuickSort(): void {
function numberComparator(o1: number, o2: number): number {
if (o1 < o2) {
return -1;
} else if (o1 == o2) {
return 0;
}
return 1;
}
let tests: number[][] = [
[], [1], [2, 1], [-1, 2, -3], [3, 16, 8, -5, 6, 4], [1, 2, 3, 4, 5, 6],
[1, 2, 3, 4, 5]
];
for (let testArray of tests) {
quickSort(testArray, numberComparator);
console.log(testArray);
}
}
</syntaxhighlight>
=={{header|UnixPipes}}==
{{works with|Zsh}}
<
(while read n ; do
test $1 -gt $n && echo $n > $2 || echo $n > $3
Line 3,517 ⟶ 10,179:
}
cat to.sort | qsort</
=={{header|Ursala}}==
Line 3,529 ⟶ 10,191:
natural numbers.
<
quicksort "p" = ~&itB^?a\~&a ^|WrlT/~& "p"*|^\~& "p"?hthPX/~&th ~&h
Line 3,535 ⟶ 10,197:
#cast %nL
example = quicksort(nleq) <694,1377,367,506,3712,381,1704,1580,475,1872></
{{out}}
<pre>
<367,381,475,506,694,1377,1580,1704,1872,3712>
Line 3,543 ⟶ 10,205:
=={{header|V}}==
<
[joinparts [p [*l1] [*l2] : [*l1 p *l2]] view].
[split_on_first uncons [>] split].
Line 3,549 ⟶ 10,211:
[]
[split_on_first [l1 l2 : [l1 qsort l2 qsort joinparts]] view i]
ifte].</
The way of joy (using binrec)
<
[small?] []
[uncons [>] split]
[[p [*l] [*g] : [*l p *g]] view]
binrec].</
{{omit from|GUISS}}
=={{header|
<syntaxhighlight lang="v (vlang)">fn partition(mut arr []int, low int, high int) int {
pivot := arr[high]
mut i := (low - 1)
for j in low .. high {
if arr[j] < pivot {
i++
temp := arr[i]
arr[i] = arr[j]
arr[j] = temp
}
}
temp := arr[i + 1]
arr[i + 1] = arr[high]
arr[high] = temp
return i + 1
}
fn quick_sort(mut arr []int, low int, high int) {
if low < high {
pi := partition(mut arr, low, high)
quick_sort(mut arr, low, pi - 1)
quick_sort(mut arr, pi + 1, high)
}
}
fn main() {
mut arr := [4, 65, 2, -31, 0, 99, 2, 83, 782, 1]
n := arr.len - 1
println('Input: ' + arr.str())
quick_sort(mut arr, 0, n)
println('Output: ' + arr.str())
}</syntaxhighlight>
{{out}}
<pre>Input: [4, 65, 2, -31, 0, 99, 2, 83, 782, 1]
Output: [-31, 0, 1, 2, 2, 4, 65, 83, 99, 782]</pre>
=={{header|Wart}}==
<syntaxhighlight lang="python">def (qsort (pivot ... ns))
(+ (qsort+keep (fn(_) (_ < pivot)) ns)
list.pivot
(qsort+keep (fn(_) (_ > pivot)) ns))
def (qsort x) :case x=nil
nil</syntaxhighlight>
=={{header|Wren}}==
{{libheader|Wren-sort}}
<syntaxhighlight lang="wren">import "./sort" for Sort
var array = [
[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 array) {
System.print("Before: %(a)")
Sort.quick(a)
System.print("After : %(a)")
System.print()
}</syntaxhighlight>
{{out}}
<pre>
Before: [4, 65, 2, -31, 0, 99, 2, 83, 782, 1]
After : [-31, 0, 1, 2, 2, 4, 65, 83, 99, 782]
Before: [7, 5, 2, 6, 1, 4, 2, 6, 3]
After : [1, 2, 2, 3, 4, 5, 6, 6, 7]
Before: [echo, lima, charlie, whiskey, golf, papa, alfa, india, foxtrot, kilo]
After : [alfa, charlie, echo, foxtrot, golf, india, kilo, lima, papa, whiskey]
</pre>
=={{header|XPL0}}==
<
string 0; \use zero-terminated strings
Line 3,673 ⟶ 10,330:
QSort(Str, StrLen(Str), 1);
Text(0, Str); CrLf(0);
]</
{{out}}
Line 3,679 ⟶ 10,336:
.Pabcdeefghiiijklmnoooqrstuuvwxyz
</pre>
=={{header|Z80 Assembly}}==
sjasmplus syntax
<syntaxhighlight lang="z80">;--------------------------------------------------------------------------------------------------------------------
; Quicksort, inputs (__sdcccall(1) calling convention):
; HL = uint16_t* A (pointer to beginning of array)
; DE = uint16_t len (number of word elements in array)
; modifies: AF, A'F', BC, DE, HL
; WARNING: array can't be aligned to start/end of 64ki address space, like HL == 0x0000, or having last value at 0xFFFE
; WARNING: stack space required is on average about 6*log(len) (depending on the data, in extreme case it may be more)
quicksort_a:
; convert arguments to HL=A.begin(), DE=A.end() and continue with quicksort_a_impl
ex de,hl
add hl,hl
add hl,de
ex de,hl
; |
; fallthrough into implementation
; |
; v
;--------------------------------------------------------------------------------------------------------------------
; Quicksort implementation, inputs:
; HL = uint16_t* A.begin() (pointer to beginning of array)
; DE = uint16_t* A.end() (pointer beyond array)
; modifies: AF, A'F', BC, HL (DE is preserved)
quicksort_a_impl:
; array must be located within 0x0002..0xFFFD
ld c,l
ld b,h ; BC = A.begin()
; if (len < 2) return; -> if (end <= begin+2) return;
inc hl
inc hl
or a
sbc hl,de ; HL = -(2*len-2), len = (2-HL)/2
ret nc ; case: begin+2 >= end <=> (len < 2)
push de ; preserve A.end() for recursion
push bc ; preserve A.begin() for recursion
; uint16_t pivot = A[len / 2];
rr h
rr l
dec hl
res 0,l
add hl,de
ld a,(hl)
inc hl
ld l,(hl)
ld h,b
ld b,l
ld l,c
ld c,a ; HL = A.begin(), DE = A.end(), BC = pivot
; flip HL/DE meaning, it makes simpler the recursive tail and (A[j] > pivot) test
ex de,hl ; DE = A.begin(), HL = A.end(), BC = pivot
dec de ; but keep "from" address (related to A[i]) at -1 as "default" state
; for (i = 0, j = len - 1; ; i++, j--) { ; DE = (A+i-1).hi, HL = A+j+1
.find_next_swap:
; while (A[j] > pivot) j--;
.find_j:
dec hl
ld a,b
sub (hl)
dec hl ; HL = A+j (finally)
jr c,.find_j ; if cf=1, A[j].hi > pivot.hi
jr nz,.j_found ; if zf=0, A[j].hi < pivot.hi
ld a,c ; if (A[j].hi == pivot.hi) then A[j].lo vs pivot.lo is checked
sub (hl)
jr c,.find_j
.j_found:
; while (A[i] < pivot) i++;
.find_i:
inc de
ld a,(de)
inc de ; DE = (A+i).hi (ahead +0.5 for swap)
sub c
ld a,(de)
sbc a,b
jr c,.find_i ; cf=1 -> A[i] < pivot
; if (i >= j) break; // DE = (A+i).hi, HL = A+j, BC=pivot
sbc hl,de ; cf=0 since `jr c,.find_i`
jr c,.swaps_done
add hl,de ; DE = (A+i).hi, HL = A+j
; swap(A[i], A[j]);
inc hl
ld a,(de)
ldd
ex af,af
ld a,(de)
ldi
ex af,af
ld (hl),a ; Swap(A[i].hi, A[j].hi) done
dec hl
ex af,af
ld (hl),a ; Swap(A[i].lo, A[j].lo) done
inc bc
inc bc ; pivot value restored (was -=2 by ldd+ldi)
; --j; HL = A+j is A+j+1 for next loop (ready)
; ++i; DE = (A+i).hi is (A+i-1).hi for next loop (ready)
jp .find_next_swap
.swaps_done:
; i >= j, all elements were already swapped WRT pivot, call recursively for the two sub-parts
dec de ; DE = A+i
; quicksort_c(A, i);
pop hl ; HL = A
call quicksort_a_impl
; quicksort_c(A + i, len - i);
ex de,hl ; HL = A+i
pop de ; DE = end() (and return it preserved)
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}}==
These are the Wikipedia algorithms.
Quick sort immutable sequence using crappy pivot choice:
<syntaxhighlight lang="zkl">fcn qtSort(list,cmp=Op("<")){ // sort immutable lists
fcn(list,cmp,N){ // spendy to keep recreating cmp
reg pivot=list[0], rest=list[1,*];
left,right:=rest.filter22(cmp,pivot);
N+=1;
T.extend(self.fcn(left,cmp,N),T(pivot),self.fcn(right,cmp,N));
}(list,cmp,0);
}</syntaxhighlight>
In place quick sort:
<syntaxhighlight lang="zkl">fcn qiSort(list,cmp='<){ // in place quick sort
fcn(list,left,right,cmp){
if (left<right){
// partition list
pivotIndex:=(left+right)/2; // or median of first,middle,last
pivot:=list[pivotIndex];
list.swap(pivotIndex,right); // move pivot to end
pivotIndex:=left;
i:=left; do(right-left){ // foreach i in ([left..right-1])
if(cmp(list[i],pivot)){ // not cheap
list.swap(i,pivotIndex);
pivotIndex+=1;
}
i+=1;
}
list.swap(pivotIndex,right); // move pivot to final place
// sort the partitions
self.fcn(list,left,pivotIndex-1,cmp);
return(self.fcn(list,pivotIndex+1,right,cmp));
}
}(list,0,list.len()-1,cmp);
list;
}</syntaxhighlight>
| |||