Sorting algorithms/Quicksort: Difference between revisions
→{{header|Python}}
(87 intermediate revisions by 34 users not shown) | |||
Line 82:
{{trans|Python}}
<
I stop - start > 0
V pivot = array[start]
Line 104:
V arr = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]
quicksort(&arr)
print(arr)</
{{out}}
Line 114:
{{trans|REXX}}
Structured version with ASM & ASSIST macros.
<
QUICKSOR CSECT
USING QUICKSOR,R13 base register
Line 285:
XD DS CL12
YREGS
END QUICKSOR</
{{out}}
<pre>
Line 293:
=={{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 */
Line 483:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
<pre>
Value : +1
Line 501:
=={{header|ABAP}}==
This works for ABAP Version 7.40 and above
<syntaxhighlight lang="abap">
report z_quicksort.
Line 540:
endif.
endform.
</syntaxhighlight>
{{out}}
Line 550:
=={{header|ACL2}}==
<
(if (endp xs)
(mv nil nil)
Line 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.
<
INT ARRAY stack(MAX_COUNT)
INT stackSize
Line 669:
Test(c,8)
Test(d,12)
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Quicksort.png Screenshot from Atari 8-bit computer]
Line 697:
{{works with|ActionScript|3}}<br>
The functional programming way
<
{
if (array.length <= 1)
Line 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 733:
equal).concat(
quickSort(greater));
}</
=={{header|Ada}}==
Line 739:
The procedure specification is:
<
-- Generic Quick_Sort procedure
-----------------------------------------------------------------------
Line 747:
type Element_Array is array(Index range <>) of Element;
with function "<" (Left, Right : Element) return Boolean is <>;
procedure Quick_Sort(A : in out Element_Array);</
The procedure body deals with any discrete index type, either an integer type or an enumerated type.
<
-- Generic Quick_Sort procedure
-----------------------------------------------------------------------
Line 792:
end;
end if;
end Quick_Sort;</
An example of how this procedure may be used is:
<
with Ada.Text_Io;
with Ada.Float_Text_IO; use Ada.Float_Text_IO;
Line 826:
Print(Weekly_Sales);
end Sort_Test;</
=={{header|ALGOL 68}}==
<
PROC swap = (REF []INT array, INT first, INT second) VOID:
(
Line 891:
print(("After: ", a))
)
</syntaxhighlight>
{{out}}
<pre>
Line 900:
=={{header|ALGOL W}}==
<
procedure quicksort ( integer array v( * )
; integer value lb, ub
Line 925:
quicksort( v, lb, right );
quicksort( v, left, ub )
end quicksort ;</
=={{header|APL}}==
{{works with|Dyalog APL}}{{trans|J}}
<
qsort 31 4 1 5 9 2 6 5 3 5 8
1 2 3 4 5 5 5 6 8 9 31</
Of course, in real APL applications, one would use ⍋ (Grade Up) to sort (which will pick a sorting algorithm suited to the argument):
<
sort 31 4 1 5 9 2 6 5 3 5 8
1 2 3 4 5 5 5 6 8 9 31</
=={{header|AppleScript}}==
Line 946:
(Functional ES5 version)
<
on quickSort(xs)
if length of xs > 1 then
Line 1,011:
end script
end if
end mReturn</
{{Out}}
<
----
Line 1,020:
Emphasising clarity, quick sorting, ''and'' correct AppleScript:
<
-- Algorithm: S.A.R. (Tony) Hoare, 1960.
on quicksort(theList, l, r) -- Sort items l thru r of theList.
Line 1,078:
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</
{{output}}
<
=={{header|Arc}}==
<
(if (empty seq) nil
(let pivot (car seq)
(join (qs (keep [< _ pivot] (cdr seq)))
(list pivot)
(qs (keep [>= _ pivot] (cdr seq)))))))</
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program quickSort.s */
Line 1,348:
iMagicNumber: .int 0xCCCCCCCD
</syntaxhighlight>
=={{header|Arturo}}==
<
if 2 > size items -> return items
Line 1,362:
]
print quickSort [3 1 2 8 5 7 9 4 6]</
{{out}}
Line 1,374:
<
(* Quicksort in ATS2, for non-linear lists. *)
(*------------------------------------------------------------------*)
Line 1,526:
end
(*------------------------------------------------------------------*)</
{{out}}
Line 1,546:
This program was derived from the quicksort for non-linear linked lists.
<
(* Quicksort in ATS2, for linear lists. *)
(*------------------------------------------------------------------*)
Line 1,715:
end
(*------------------------------------------------------------------*)</
{{out}}
Line 1,733:
<
(* Quicksort in ATS2, for arrays of non-linear values. *)
(*------------------------------------------------------------------*)
Line 1,948:
end
(*------------------------------------------------------------------*)</
{{out}}
Line 1,970:
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''.
<
(* Quicksort in ATS2, for arrays of (possibly) linear values. *)
(*------------------------------------------------------------------*)
Line 2,333:
end
(*------------------------------------------------------------------*)</
{{out}}
Line 2,348:
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:
<
for k, v in QuickSort(a)
Out .= "," v
Line 2,379 ⟶ 2,388:
Out.Insert(1, Less*) ; insert all values of less at index 1
return Out
}</
Old implementation for AutoHotkey 1.0:
<
quicksort(list)
Line 2,405 ⟶ 2,414:
more := quicksort(more)
Return less . pivotList . more
}</
=={{header|AWK}}==
<
# the following qsort implementation extracted from:
#
Line 2,522 ⟶ 2,531:
}
}
</syntaxhighlight>
=={{header|BASIC}}==
==={{header|ANSI BASIC}}===
{{works with|
<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)
270 PRINT USING "## ":
280 NEXT I
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
420
430 LOOP
440 LET
450 LET Arr(LIndex) =
460 LET Arr(RIndex) = Temp
470 LET
480 LET RIndex = RIndex -
490 IF (LIndex - 1) =
500 LET
510 LET
520
530 LET
540 LET
550 END IF
560 LOOP
570 CALL QuickSort (Arr, L, Pivot - 1)
580 CALL QuickSort (Arr, Pivot + 1,
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}}===
<
test() = 4, 65, 2, -31, 0, 99, 2, 83, 782, 1
PROCquicksort(test(), 0, 10)
Line 2,611 ⟶ 2,625:
IF s% < r% PROCquicksort(a(), s%, r% - s% + 1)
IF l% < t% PROCquicksort(a(), l%, t% - l% + 1 )
ENDPROC</
{{out}}
<pre>
-31 0 1 2 2 4 65 83 99 782
</pre>
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
{{trans|Yabasic}}
<syntaxhighlight lang="qbasic">100 dim array(15)
110 a = 0
120 b = ubound(array)
130 randomize timer
140 for i = a to b
150 array(i) = rnd(1)*1000
160 next i
170 print "unsort ";
180 for i = a to b
190 print using "####";array(i);
200 if i = b then print ""; else print ", ";
210 next i
220 quicksort(array(),a,b)
230 print : print " sort ";
240 for i = a to b
250 print using "####";array(i);
260 if i = b then print ""; else print ", ";
270 next i
280 print
290 end
300 sub quicksort(array(),l,r)
310 size = r-l+1
320 if size < 2 then return
330 i = l
340 j = r
350 pivot = array(l+int(size/2))
360 rem repeat
370 while array(i) < pivot
380 i = i+1
390 wend
400 while pivot < array(j)
410 j = j-1
420 wend
430 if i <= j then temp = array(i) : array(i) = array(j) : array(j) = temp : i = i+1 : j = j-1
440 if i <= j then goto 360
450 if l < j then quicksort(array(),l,j)
460 if i < r then quicksort(array(),i,r)
470 end sub</syntaxhighlight>
==={{header|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}}===
<
110 RANDOMIZE
120 NUMERIC A(5 TO 19)
Line 2,654 ⟶ 2,961:
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</
==={{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.
Line 2,702 ⟶ 3,048:
Loop Until Left >= Right
Loop Until StackPtr = 0
End Sub</
==={{header|QuickBASIC}}===
{{works with|FreeBASIC}}
{{works with|PowerBASIC for DOS}}
{{works with|QB64}}
{{works with|QBasic}}
This is specifically for <code>INTEGER</code>s, but can be modified for any data type by changing <code>arr()</code>'s type.
<syntaxhighlight lang="qbasic">DECLARE SUB quicksort (arr() AS INTEGER, leftN AS INTEGER, rightN AS INTEGER)
DIM q(99) AS INTEGER
DIM n AS INTEGER
RANDOMIZE TIMER
FOR n = 0 TO 99
q(n) = INT(RND * 9999)
NEXT
OPEN "output.txt" FOR OUTPUT AS 1
FOR n = 0 TO 99
PRINT #1, q(n),
NEXT
PRINT #1,
quicksort q(), 0, 99
FOR n = 0 TO 99
PRINT #1, q(n),
NEXT
CLOSE
SUB quicksort (arr() AS INTEGER, leftN AS INTEGER, rightN AS INTEGER)
DIM pivot AS INTEGER, leftNIdx AS INTEGER, rightNIdx AS INTEGER
leftNIdx = leftN
rightNIdx = rightN
IF (rightN - leftN) > 0 THEN
pivot = (leftN + rightN) / 2
WHILE (leftNIdx <= pivot) AND (rightNIdx >= pivot)
WHILE (arr(leftNIdx) < arr(pivot)) AND (leftNIdx <= pivot)
leftNIdx = leftNIdx + 1
WEND
WHILE (arr(rightNIdx) > arr(pivot)) AND (rightNIdx >= pivot)
rightNIdx = rightNIdx - 1
WEND
SWAP arr(leftNIdx), arr(rightNIdx)
leftNIdx = leftNIdx + 1
rightNIdx = rightNIdx - 1
IF (leftNIdx - 1) = pivot THEN
rightNIdx = rightNIdx + 1
pivot = rightNIdx
ELSEIF (rightNIdx + 1) = pivot THEN
leftNIdx = leftNIdx - 1
pivot = leftNIdx
END IF
WEND
quicksort arr(), leftN, pivot - 1
quicksort arr(), pivot + 1, rightN
END IF
END SUB</syntaxhighlight>
==={{header|Run BASIC}}===
<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]
lftHold = lft
rhtHold = rht
pivot = s(lft)
while lft < rht
while (s(rht) >= pivot) and (lft < rht) : rht = rht - 1 :wend
if lft <> rht then
s(lft) = s(rht)
lft = lft + 1
end if
while (s(lft) <= pivot) and (lft < rht) : lft = lft + 1 :wend
if lft <> rht then
s(rht) = s(lft)
rht = rht - 1
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 2,757 ⟶ 3,624:
}
newline()
}</
=={{header|Beads}}==
<
calc main_init
Line 2,796 ⟶ 3,663:
swap arr[i+1] <=> arr[highIndex]
return (i+1)
</syntaxhighlight>
{{out}}
Line 2,803 ⟶ 3,670:
=={{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.
<
= Less Greater Equal pivot element
. !arg:%(?pivot:?Equal) %?arg
Line 2,821 ⟶ 3,688:
)
& out$Q$(1900 optimized variants of 4001/2 Quicksort (quick,sort) are (quick,sober) features of 90 languages)
);</
{{out}}
<pre> 90
Line 2,836 ⟶ 3,703:
(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>
Line 2,883 ⟶ 3,765:
quicksort(A + i, len - i);
}
</syntaxhighlight>
{{out}}
Line 2,893 ⟶ 3,775:
Randomized sort with separated components.
<syntaxhighlight lang="c">
#include <stdlib.h> // REQ: rand()
Line 2,923 ⟶ 3,805:
}
}
</syntaxhighlight>
=={{header|C sharp|C#}}==
<
// The Tripartite conditional enables Bentley-McIlroy 3-way Partitioning.
// This performs additional compares to isolate islands of keys equal to
Line 3,101 ⟶ 3,983:
}
#endregion
}</
'''Example''':
<
using System;
Line 3,113 ⟶ 3,995:
Console.WriteLine(String.Join(" ", entries));
}
}</
{{out}}
<pre>1 2 3 4 5 6 7 8 9</pre>
Line 3,119 ⟶ 4,001:
A very inefficient way to do qsort in C# to prove C# code can be just as compact and readable as any dynamic code
<
using System.Collections.Generic;
using System.Linq;
Line 3,141 ⟶ 4,023:
}
}
}</
=={{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 3,214 ⟶ 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 3,238 ⟶ 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 3,249 ⟶ 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|COBOL}}==
{{works with|Visual COBOL}}
<
PROGRAM-ID. quicksort RECURSIVE.
Line 3,348 ⟶ 4,270:
GOBACK
.</
=={{header|CoffeeScript}}==
<
quicksort = ([x, xs...]) ->
return [] unless x?
Line 3,357 ⟶ 4,279:
larger = (a for a in xs when a > x)
(quicksort smallerOrEqual).concat(x).concat(quicksort larger)
</syntaxhighlight>
=={{header|Common Lisp}}==
Line 3,363 ⟶ 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 3,394 ⟶ 4,316:
(sub-sort (1+ index) right)))))
(sub-sort 0 (1- (length sequence)))
sequence))</
Functional with destructuring
<
(defun quicksort (list)
(when list
Line 3,404 ⟶ 4,326:
(nconc (quicksort (remove-if (lambda (a) (> a x)) xs))
`(,x)
(quicksort (remove-if (lambda (a) (<= a x)) xs))))))</
=={{header|Cowgol}}==
<
# Comparator interface, on the model of C, i.e:
Line 3,508 ⟶ 4,430:
i := i + 1;
end loop;
print_nl();</
{{out}}
Line 3,516 ⟶ 4,438:
=={{header|Crystal}}==
{{trans|Ruby}}
<
return a if a.size <= 1
p = a[0]
Line 3,524 ⟶ 4,446:
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]</
=={{header|Curry}}==
Copied from [http://www.informatik.uni-kiel.de/~curry/examples/ Curry: Example Programs].
<
qsort :: [Int] -> [Int]
Line 3,534 ⟶ 4,456:
qsort (x:l) = qsort (filter (<x) l) ++ x : qsort (filter (>=x) l)
goal = qsort [2,3,1,0]</
=={{header|D}}==
A Functional version
<
import std.algorithm: filter;
import std.array;
Line 3,550 ⟶ 4,472:
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):
<
T[] quickSort(T)(T[] items) pure nothrow {
Line 3,568 ⟶ 4,490:
void main() {
[4, 65, 2, -31, 0, 99, 2, 83, 782, 1].quickSort.writeln;
}</
Often short functional sieves are not a true implementations of the Sieve of Eratosthenes:
Line 3,575 ⟶ 4,497:
Similarly, one could argue that a true QuickSort is in-place,
as this more efficient version (same output):
<
void quickSort(T)(T[] items) pure nothrow @safe @nogc {
Line 3,589 ⟶ 4,511:
items.quickSort;
items.writeln;
}</
=={{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 3,630 ⟶ 4,727:
print("After sort");
arr.forEach((var i)=>print("$i"));
}</
=={{header|E}}==
<
def swap(container, ixA, ixB) {
Line 3,680 ⟶ 4,777:
quicksortR(array, 0, array.size() - 1)
}
}</
=={{header|EasyLang}}==
<syntaxhighlight lang="text">
proc qsort left right . d[] .
while left < right
# partition
mid = left
for i = left + 1 to right
if
mid += 1
swap
.
.
swap d[left] d[mid]
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
</syntaxhighlight>
=={{header|EchoLisp}}==
<
(lib 'list) ;; list-partition
Line 3,720 ⟶ 4,827:
(list (first L))
(quicksort (second part) proc)))))
</syntaxhighlight>
{{out}}
<
(shuffle (iota 15))
→ (10 0 14 11 13 9 2 5 4 8 1 7 12 3 6)
Line 3,742 ⟶ 4,849:
n 100000 compare# 6198601
</syntaxhighlight>
=={{header|Eero}}==
Translated from Objective-C example on this page.
<
void quicksortInPlace(MutableArray array, const long first, const long last)
Line 3,781 ⟶ 4,888:
Log( 'Sorted: %@', quicksort(b) )
return 0</
Alternative implementation (not necessarily as efficient, but very readable)
<
implementation Array (Quicksort)
Line 3,817 ⟶ 4,924:
Log( 'Sorted: %@', b.quicksort )
return 0</
{{out}}
Line 3,868 ⟶ 4,975:
=={{header|Eiffel}}==
The <syntaxhighlight lang
<
class
QUICKSORT [G -> COMPARABLE]
Line 3,964 ⟶ 5,071:
end
</syntaxhighlight>
A test application:
<
class
APPLICATION
Line 3,995 ⟶ 5,102:
end
</syntaxhighlight>
=={{header|Elena}}==
ELENA
<
import system'routines;
import system'collections;
Line 4,015 ⟶ 5,122:
auto more := new ArrayList();
self.forEach::(item)
{
if (item < pivot)
Line 4,047 ⟶ 5,154:
console.printLine("before:", list.asEnumerable());
console.printLine("after :", list.quickSort().asEnumerable());
}</
{{out}}
<pre>
Line 4,055 ⟶ 5,162:
=={{header|Elixir}}==
<
def qsort([]), do: []
def qsort([h | t]) do
Line 4,061 ⟶ 5,168:
qsort(lesser) ++ [h] ++ qsort(greater)
end
end</
=={{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]]
<
-module( quicksort ).
Line 4,074 ⟶ 5,181:
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):
<
quick_sort(L) -> qs(L, trunc(math:log2(erlang:system_info(schedulers)))).
Line 4,098 ⟶ 5,205:
after 5000 -> receive_results(Ref, L1, L2)
end.
</syntaxhighlight>
=={{header|Emacs Lisp}}==
Line 4,104 ⟶ 5,211:
{{libheader|seq.el}}
<
(defun quicksort (xs)
Line 4,113 ⟶ 5,220:
(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))))</
=={{header|ERRE}}==
<syntaxhighlight lang="erre">
PROGRAM QUICKSORT_DEMO
Line 4,196 ⟶ 5,303:
END FOR
END PROGRAM
</syntaxhighlight>
=={{header|F Sharp|F#}}==
<
let rec qsort = function
hd :: tl ->
Line 4,205 ⟶ 5,312:
List.concat [qsort less; [hd]; qsort greater]
| _ -> []
</syntaxhighlight>
=={{header|Factor}}==
<
dup empty? [
unclip [ [ < ] curry partition [ qsort ] bi@ ] keep
prefix append
] unless ;</
=={{header|Fe}}==
<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 pivot (car lst))
(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 2 -31 99 2 0 83 782 1))
(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}}==
<
# This version preserves duplicates.
\sort==
Line 4,233 ⟶ 5,378:
unique; filter (lt x) xs # all the items greater than x
)
</syntaxhighlight>
=={{header|Forth}}==
<
: exch ( addr1 addr2 -- ) dup @ >r over @ swap ! r> swap ! ;
Line 4,256 ⟶ 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
!
!*Code
!
last = size(a, 1)
if( (last - first)<changesize )then
call insertion_sort(a(first:last))
end
j
!
x =
i =
j = last
do while ( stay
end
end
t = a(i) ! Swap the values
a(i) = a(j)
end
if( first<i - 1 )call fsort(a(first:i - 1)) ! We still have some left to do on the lower
if( j + 1<last )call fsort(a(j + 1:last)) ! We still have some left to do on the upper
return
end subroutine fsort
</syntaxhighlight>
=={{header|FunL}}==
<
qsort( [] ) = []
qsort( p:xs ) = qsort( xs.filter((< p)) ) + [p] + qsort( xs.filter((>= p)) )</
Here is a more efficient version using the <code>partition</code> function.
<
qsort( [] ) = []
qsort( x:xs ) =
Line 4,468 ⟶ 5,479:
println( qsort([4, 2, 1, 3, 0, 2]) )
println( qsort(["Juan", "Daniel", "Miguel", "William", "Liam", "Ethan", "Jacob"]) )</
{{out}}
Line 4,492 ⟶ 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 4,584 ⟶ 5,595:
}
pex(0, len(a)-1)
}</
{{out}}
<pre>
Line 4,593 ⟶ 5,604:
More traditional version of quicksort. It work generically with any container that conforms to <code>sort.Interface</code>.
<
import (
Line 4,644 ⟶ 5,655:
quicksort(sort.StringSlice(b))
fmt.Printf("Sorted: %v\n", b)
}</
{{out}}
<pre>
Line 4,656 ⟶ 5,667:
The famous two-liner, reflecting the underlying algorithm directly:
<
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] ++ qsort zs where
(ys, zs) = partition (< x) xs</
=={{header|Icon}} and {{header|Unicon}}==
<
demosort(quicksort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")
end
Line 4,712 ⟶ 5,723:
suspend lower # 1st return pivot point
suspend X # 2nd return modified X (in case immutable)
end</
Implementation notes:
Line 4,732 ⟶ 5,743:
=={{header|IDL}}==
IDL has a powerful optimized <tt>sort()</tt> built-in. The following is thus merely for demonstration.
<
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</
Example:
Line 4,744 ⟶ 5,755:
=={{header|Idris}}==
<
quicksort [] = []
quicksort (x :: xs) =
let lesser = filter (< x) xs
greater = filter(>= x) xs in
(quicksort lesser) ++ [x] ++ (quicksort greater)</
Example:
Line 4,757 ⟶ 5,768:
=={{header|Io}}==
<
quickSort := method(
if(size > 1) then(
Line 4,774 ⟶ 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}}==
<
imports Main
begin
Line 4,847 ⟶ 5,858:
oops
end
</syntaxhighlight>
=={{header|J}}==
{{eff note|J|/:~}}
<
quicksort=: 3 : 0
Line 4,862 ⟶ 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 4,873 ⟶ 5,884:
{{trans|Python}}
<
if (arr.isEmpty())
return arr;
Line 4,903 ⟶ 5,914:
}
}
</syntaxhighlight>
=== Functional ===
{{works with|Java|1.8}}
<
if (col == null || col.isEmpty())
return Collections.emptyList();
Line 4,918 ⟶ 5,929:
.flatMap(Collection::stream).collect(Collectors.toList());
}
}</
=={{header|JavaScript}}==
Line 4,924 ⟶ 5,935:
===Imperative===
<
function swap(i, j) {
Line 4,962 ⟶ 5,973:
return array;
}</
Example:<
var sorted_array = sort(test_array, function(a,b) { return a<b; });</
{{Out}}<
===Functional===
Line 4,975 ⟶ 5,986:
Using '''destructuring''' and '''satisfying immutability''' we can propose a single expresion solution (from https://github.com/ddcovery/expressive_sort)
<
pivot === void 0 ? [] : [
...qsort(others.filter(n => n < pivot)),
Line 4,982 ⟶ 5,993:
];
qsort( [ 11.8, 14.1, 21.3, 8.5, 16.7, 5.7 ] )</
{{Out}}
<pre>[ 5.7, 8.5, 11.8, 14.1, 16.7, 21.3 ]
Line 4,991 ⟶ 6,002:
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(
Line 5,000 ⟶ 6,011:
}
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 5,012 ⟶ 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:<
Here is an implementation in jq of the pseudo-code (and comments :-) given at the head of this article:<
if length < 2 then . # it is already sorted
else .[0] as $pivot
Line 5,032 ⟶ 6,043:
| (.[0] | quicksort ) + .[1] + (.[2] | quicksort )
end ;
</
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]):
<
A simple polymorphic implementation of an in-place recursive quicksort (based on the pseudocode above):
<
if j > i
pivot = A[rand(i:j)] # random element of A
Line 5,060 ⟶ 6,071:
end
return A
end</
A one-line (but rather inefficient) implementation based on the Haskell version, which operates out-of-place and allocates temporary arrays:
<
{{out}}
<pre>julia> A = [84,77,20,60,47,20,18,97,41,49,31,39,73,68,65,52,1,92,15,9]
Line 5,076 ⟶ 6,087:
=={{header|K}}==
<
Example:
<syntaxhighlight lang="k">
quicksort 1 3 5 7 9 8 6 4 2
</syntaxhighlight>
{{out}}
Line 5,091 ⟶ 6,102:
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 5,106 ⟶ 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 5,114 ⟶ 6,125:
And here is the full if/then/else clause:
<syntaxhighlight lang="k">
:[
0=#x; / if length of x is zero
Line 5,124 ⟶ 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 5,130 ⟶ 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
<
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
}
}</
or using standard <code>partition</code> function
<
match(xs) {
Cons(x,xx) -> {
val (ys, zs) = xx.partition fn(el) { el < x }
qsort(ys) ++ [x] ++ qsort(zs)
}
Nil -> Nil
}
}</
Example:
<
val arr = [24,63,77,26,84,64,56,80,85,17]
println(arr.qsort.show)
}</
{{out}}
Line 5,172 ⟶ 6,183:
A version that reflects the algorithm directly:
<
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:
<
if (size < 2) this
else {
Line 5,187 ⟶ 6,198:
less.qsort() + first() + high.qsort()
}
</syntaxhighlight>
=={{header|Lambdatalk}}==
<
We create a binary tree from a random array, then we walk the canopy.
Line 5,294 ⟶ 6,305:
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}}==
<
def quicksort(xs, lt):
Line 5,313 ⟶ 6,324:
sorted := [ 3, 9, 5, 4, 1, 3, 9, 5, 4, 1 ].quicksort(): _a < _b
print sorted</
=={{header|Logo}}==
<
to small? :list
Line 5,331 ⟶ 6,342:
end
show quicksort [1 3 5 7 9 8 6 4 2]</
<
to incr :name
Line 5,365 ⟶ 6,376:
make "test {1 3 5 7 9 8 6 4 2}
sort :test
show :test</
=={{header|Logtalk}}==
<
quicksort(List, [], Sorted).
Line 5,384 ⟶ 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===
<
function quicksort(t, start, endi)
start, endi = start or 1, endi or #t
Line 5,410 ⟶ 6,421:
--example
print(unpack(quicksort{5, 2, 7, 3, 4, 7, 1}))</
===non in-place===
<
if #t<2 then return t end
local pivot=t[1]
Line 5,428 ⟶ 6,439:
for _,v in ipairs(c) do a[#a+1]=v end
return a
end</
=={{header|Lucid}}==
[http://i.csc.uvic.ca/home/hei/lup/06.html]
<
where
p = first a < a;
Line 5,441 ⟶ 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 {
Line 5,479 ⟶ 6,490:
}
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 {
Line 5,526 ⟶ 6,537:
}
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 {
Line 5,602 ⟶ 6,613:
}
Checkit3
</syntaxhighlight>
=={{header|M4}}==
<
define(`arg1', `$1')dnl
dnl
Line 5,632 ⟶ 6,643:
`sep(arg1$1,(shift$1),`()',`()')')')dnl
dnl
quicksort((3,1,4,1,5,9))</
{{out}}
Line 5,640 ⟶ 6,651:
=={{header|Maclisp}}==
<syntaxhighlight lang="lisp">
;; While not strictly required, it simplifies the
;; implementation considerably to use filter. MACLisp
Line 5,666 ⟶ 6,677:
(LIST PIVOT)
(QUICKSORT (FILTER #'(LAMBDA (X) (> X PIVOT)) REST)))))))
</syntaxhighlight>
=={{header|Maple}}==
<
local temp := arr[a]:
arr[a] := arr[b]:
Line 5,697 ⟶ 6,708:
a:=Array([12,4,2,1,0]);
quicksort(a,1,5);
a;</
{{Out|Output}}
<pre>[0, 1, 2, 4, 12]</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
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]]}
]</
<
qsort[{x_, xs___}] := Join[qsort@Select[{xs}, # <= x &], {x}, qsort@Select[{xs}, # > x &]];</
<
QuickSort[list: {__}] := With[{pivot=RandomChoice[list]},
Join[ <|1->{}, -1->{}|>, GroupBy[list,Order[#,pivot]&] ] // Catenate[ {QuickSort@#[1], #[0], QuickSort@#[-1]} ]&
]</
=={{header|MATLAB}}==
Line 5,719 ⟶ 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 5,739 ⟶ 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 5,754 ⟶ 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 5,791 ⟶ 6,802:
)
a = #(4, 89, -3, 42, 5, 0, 2, 889)
a = quickSort a</
=={{header|Mercury}}==
Line 5,799 ⟶ 6,810:
<
:- module quicksort_task_for_lists.
Line 5,902 ⟶ 6,913:
%%% mode: mercury
%%% prolog-indent-width: 2
%%% end:</
{{out}}
Line 5,915 ⟶ 6,926:
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.)
<
:- module quicksort_task_for_arrays.
Line 5,943 ⟶ 6,954:
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).
Line 6,002 ⟶ 7,013:
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),
Line 6,095 ⟶ 7,108:
%%% mode: mercury
%%% prolog-indent-width: 2
%%% end:</
{{out}}
Line 6,107 ⟶ 7,120:
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 6,118 ⟶ 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 6,129 ⟶ 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 6,135 ⟶ 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 6,262 ⟶ 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 6,359 ⟶ 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 6,379 ⟶ 7,449:
IO.Put(arr[i] & "\n");
END;
END Main.</
=={{header|Mond}}==
Line 6,385 ⟶ 7,455:
Implements the simple quicksort algorithm.
<
{
if( arr.length() < 2 )
Line 6,416 ⟶ 7,486:
return a;
}</
;Usage
<
var sorted = quicksort( array );
printLn( sorted );</
{{out}}
Line 6,440 ⟶ 7,510:
Shows quicksort on a 16-element array.
<syntaxhighlight lang="mumps">
main
new collection,size
Line 6,476 ⟶ 7,546:
. . set:array(i)>array(j) sorted=0
quit sorted
</syntaxhighlight>
;Usage
<syntaxhighlight lang
{{out}}
Line 6,528 ⟶ 7,598:
=={{header|Nanoquery}}==
{{trans|Python}}
<
less = {}
pivotList = {}
Line 6,551 ⟶ 7,621:
return less + pivotList + more
end
end</
=={{header|Nemerle}}==
{{trans|Haskell}}
A little less clean and concise than Haskell, but essentially the same.
<
using System.Console;
using Nemerle.Collections.NList;
Line 6,578 ⟶ 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 6,682 ⟶ 7,752:
return ixStore
</syntaxhighlight>
{{out}}
<pre>
Line 6,715 ⟶ 7,785:
=={{header|Nial}}==
<
pass,
link [
Line 6,722 ⟶ 7,792:
quicksort sublist [ > [pass,first], pass ]
]
]</
Using it.
<
=3 4 5 7 8</
=={{header|Nim}}==
==={{header|Procedural (in place) algorithm }} ===
<
if stop - start > 0:
let pivot = a[start]
Line 6,753 ⟶ 7,823:
var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]
a.quickSort()
echo a</
==={{header|Functional (inmmutability) algorithm }} ===
<
func sorted[T](xs:seq[T]): seq[T] =
Line 6,765 ⟶ 7,835:
)
@[4, 65, 2, -31, 0, 99, 2, 83, 782].sorted.echo</
{{out}}
Line 6,771 ⟶ 7,841:
=={{header|Nix}}==
<
let
qs = l:
Line 6,784 ⟶ 7,854:
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 6,837 ⟶ 7,966:
}
}
</syntaxhighlight>
=={{header|Objective-C}}==
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;
id pivot = array[(first + last) / 2];
Line 6,874 ⟶ 8,003:
}
return 0;
}</
{{out}}
<pre>Unsorted: (
Line 6,925 ⟶ 8,054:
===Declarative and purely functional===
<
| [] -> []
| x::xs ->
Line 6,932 ⟶ 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).
Line 6,940 ⟶ 8,069:
Using aliased array slices from the [https://c-cube.github.io/ocaml-containers/2.6/containers/CCArray_slice/index.html Containers library].
<
let quicksort : int Array.t -> unit = fun arr ->
Line 6,971 ⟶ 8,100:
(* 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 6,987 ⟶ 8,116:
N=30; v=rand(N,1); tic,u=quicksort(v); toc
u</
=={{header|Oforth}}==
Line 6,993 ⟶ 8,122:
Oforth built-in sort uses quick sort algorithm (see lang/collect/ListBuffer.of for implementation) :
<
=={{header|Ol}}==
<
(define (quicksort l ??)
(if (null? l)
Line 7,010 ⟶ 8,139:
(print
(quicksort (iota 100) <))
</syntaxhighlight>
{{Out}}
<pre>
Line 7,020 ⟶ 8,149:
=={{header|ooRexx}}==
{{trans|Python}}
<
say 'before:' a~toString( ,', ')
a = quickSort(a)
Line 7,046 ⟶ 8,175:
more = quickSort(more)
return less~~appendAll(pivotList)~~appendAll(more)
end</
{{out}}
<pre>before: 4, 65, 2, -31, 0, 99, 83, 782, 1
Line 7,052 ⟶ 8,181:
=={{header|Oz}}==
<
fun {QuickSort Xs}
case Xs of nil then nil
Line 7,064 ⟶ 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 7,081 ⟶ 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 {
return @_ if @_ < 2;
Line 7,121 ⟶ 8,277:
@a = quick_sort @a;
print "@a\n";
</syntaxhighlight>
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
Line 7,153 ⟶ 8,309:
<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>
<!--</
{{out}}
<pre>
Line 7,160 ⟶ 8,316:
=={{header|PHP}}==
<
$lte = $gt = array();
if(count($arr) < 2){
Line 7,179 ⟶ 8,335:
$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>
<
function quickSort(array $array) {
// base case
Line 7,201 ⟶ 8,357:
$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===
<
qsort([H|T]) = qsort([E : E in T, E =< H])
++ [H] ++
qsort([E : E in T, E > H]).</
===Recursion===
{{trans|Prolog}}
<
qsort( [H|U], S ) :-
splitBy(H, U, L, R),
Line 7,224 ⟶ 8,380:
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).</
=={{header|PicoLisp}}==
<
(if (cdr L)
(let Pivot (car L)
Line 7,233 ⟶ 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 7,284 ⟶ 8,440:
END MINMAX;
CALL MINMAX(A,AMIN,AMAX,N);
CALL QUICKSORT(A,AMIN,AMAX,N);</
=={{header|PowerShell}}==
===First solution===
<
{
if( $data[ 0 ] -gt $data[ 1 ] )
Line 7,340 ⟶ 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===
<
function quicksort($array) {
$less, $equal, $greater = @(), @(), @()
Line 7,360 ⟶ 8,516:
$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===
<
function quicksort($in) {
$n = $in.count
Line 7,381 ⟶ 8,537:
}
}
</syntaxhighlight>
=={{header|Prolog}}==
<
qsort( [H|U], S ) :- splitBy(H, U, L, R), qsort(L, SL), qsort(R, SR), append(SL, [H|SR], S).
Line 7,392 ⟶ 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:
<
def qSort(a):
Line 7,480 ⟶ 8,598:
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])</
<
if len(a) <= 1:
return a
Line 7,497 ⟶ 8,615:
less = quickSort(less)
more = quickSort(more)
return less + [pivot] * a.count(pivot) + more</
Returning a new list:
<
if len(array) < 2:
return array
Line 7,507 ⟶ 8,625:
less = qsort([i for i in tail if i < head])
more = qsort([i for i in tail if i >= head])
return less + [head] + more</
Sorting a list in place:
<
_quicksort(array, 0, len(array) - 1)
Line 7,527 ⟶ 8,645:
right -= 1
_quicksort(array, start, right)
_quicksort(array, left, stop)</
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 7,542 ⟶ 8,674:
(quicksort [6 8 5 9 3 2 2 1 4 7])
</syntaxhighlight>
=={{header|Quackery}}==
Line 7,548 ⟶ 8,680:
Sort a nest of numbers.
<
[ stack ] is same ( --> s )
Line 7,573 ⟶ 8,705:
[] 10 times [ i^ join ] 3 of
dup echo cr
quicksort echo cr</
'''Output:'''
Line 7,582 ⟶ 8,714:
=={{header|R}}==
{{trans|Octave}}
<
if ( length(v) > 1 )
{
Line 7,593 ⟶ 8,725:
vs <- runif(N)
system.time(u <- qsort(vs))
print(u)</
=={{header|Racket}}==
<
(define (quicksort < l)
(match l
Line 7,604 ⟶ 8,736:
(append (quicksort < xs-lt)
(list x)
(quicksort < xs-gte)))]))</
Examples
<
;returns '(2 3 4 5 6 7 8)
(quicksort string<? '("Mergesort" "Quicksort" "Bubblesort"))
;returns '("Bubblesort" "Mergesort" "Quicksort")</
=={{header|Raku}}==
<syntaxhighlight lang="raku" line>
#| Recursive, single-thread, random pivot, single-pass, quicksort implementation
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 []
Line 7,663 ⟶ 8,924:
sort list ;; just for fun time the builtin function also ( also implementation of quicksort )
print ["time2: " now/time/precise - t0]
</syntaxhighlight>
=={{header|REXX}}==
Line 7,671 ⟶ 8,932:
It is over '''400%''' times faster then the 2<sup>nd</sup> REXX version (using the exact same random numbers).
<
call gen@ /*generate the elements for the array. */
call show@ 'before sort' /*show the before array elements. */
Line 7,777 ⟶ 9,038:
@.1= center(@.1, maxL, '-') /* " " header information. */
@.2= copies(@.2, maxL) /* " " " separator. */
return</
{{out|output|text= when using the internal default input:}}
<pre style="height:60ex">
Line 7,914 ⟶ 9,175:
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'
Line 8,001 ⟶ 9,262:
queue more.i
end
return</
=={{header|Refal}}==
<syntaxhighlight lang="refal">$ENTRY Go {
, 7 6 5 9 8 4 3 1 2 0: e.Arr
= <Prout e.Arr>
<Prout <Sort e.Arr>>;
};
Sort {
= ;
s.N = s.N;
s.Pivot e.X =
<Sort <Filter s.Pivot '-' e.X>>
<Filter s.Pivot '=' e.X>
s.Pivot
<Sort <Filter s.Pivot '+' e.X>>;
};
Filter {
s.N s.Comp = ;
s.N s.Comp s.I e.List, <Compare s.I s.N>: {
s.Comp = s.I <Filter s.N s.Comp e.List>;
s.X = <Filter s.N s.Comp e.List>;
};
};</syntaxhighlight>
{{out}}
<pre>7 6 5 9 8 4 3 1 2 0
0 1 2 3 4 5 6 7 8 9</pre>
=={{header|Ring}}==
<
# Project : Sorting algorithms/Quicksort
Line 8,051 ⟶ 9,339:
svect = left(svect, len(svect) - 1)
see svect + nl
</syntaxhighlight>
Output:
<pre>
Line 8,059 ⟶ 9,347:
-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}}==
<
def quick_sort
return self if length <= 1
Line 8,068 ⟶ 9,375:
less.quick_sort + [pivot] + greatereq.quick_sort
end
end</
or
<
def quick_sort
return self if length <= 1
Line 8,078 ⟶ 9,385:
group[-1].quick_sort + group[0] + group[1].quick_sort
end
end</
or functionally
<
def quick_sort
h, *t = self
h ? t.partition { |e| e < h }.inject { |l, r| l.quick_sort + [h] + r.quick_sort } : []
end
end</
=={{header|Rust}}==
<
println!("Sort numbers in descending order");
let mut numbers = [4, 65, 2, -31, 0, 99, 2, 83, 782, 1];
Line 8,187 ⟶ 9,447:
v.swap(store_index, len - 1);
store_index
}</
{{out}}
Line 8,203 ⟶ 9,463:
Or, using functional style (slower than the imperative style but faster than functional style in other languages):
<
let numbers = [4, 65, 2, -31, 0, 99, 2, 83, 782, 1];
println!("{:?}\n", quick_sort(numbers.iter()));
Line 8,227 ⟶ 9,487:
}
}
</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.
Line 8,233 ⟶ 9,493:
=={{header|SASL}}==
Copied from SASL manual, Appendix II, solution (2)(b)
<
sort () = ()
sort (a : x) = sort {b <- x; b <= a } ++ a : sort { b <- x; b>a}
?</
=={{header|Sather}}==
<
private afilter(a:ARRAY{T}, cmp:ROUT{T,T}:BOOL, p:T):ARRAY{T} is
Line 8,264 ⟶ 9,524:
a := res;
end;
end;</
<
main is
a:ARRAY{INT} := |10, 9, 8, 7, 6, -10, 5, 4, 656, -11|;
Line 8,273 ⟶ 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.
Line 8,282 ⟶ 9,542:
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
}</
Next, a quick sort of a list of some type T, given a lessThan function:
<
case Nil => Nil
case x :: xx =>
val (lo, hi) = xx.partition(lessThan(_, x))
sort(lo, lessThan) ++ (x :: sort(hi, lessThan))
}</
To take advantage of known orderings, a quick sort of a list of some type T,
for which exists an implicit (or explicit) Ordering[T]:
<
case Nil => Nil
case x :: xx =>
val (lo, hi) = xx.partition(ord.lt(_, x))
sort[T](lo) ++ (x :: sort[T](hi))
}</
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.
<
case Nil => Nil
case x :: xx =>
val (lo, hi) = xx.partition(_ < x)
sort(lo) ++ (x :: sort(hi))
}</
What hasn't changed in all these examples is ordering a list. It is possible
Line 8,323 ⟶ 9,583:
the function. Let's see it below, and then remark upon it:
<
(xs: C[T])
(implicit ord: scala.math.Ordering[T],
Line 8,339 ⟶ 9,599:
b.result()
}
}</
The type of our collection is "C[T]", and,
Line 8,362 ⟶ 9,622:
<
(let loop ((low '())
(high '())
Line 8,383 ⟶ 9,643:
(quicksort high gt?))))))
(quicksort '(1 3 5 7 9 8 6 4 2) >)</
With srfi-1:
<
(if (null? l)
'()
Line 8,394 ⟶ 9,654:
(quicksort '(1 3 5 7 9 8 6 4 2) >)
</syntaxhighlight>
Line 8,404 ⟶ 9,664:
<
;;;
;;; Quicksort in R7RS Scheme, working in-place on vectors (that is,
Line 8,509 ⟶ 9,769:
(newline)
;;;-------------------------------------------------------------------</
{{out}}
Line 8,516 ⟶ 9,776:
=={{header|Seed7}}==
<
local
var elemType: compare_elem is elemType.value;
Line 8,550 ⟶ 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 8,576 ⟶ 9,836:
proc swap(rw x, rw y);
[y,x] := [x,y];
end proc;</
Copying sort using comprehensions:
<
print(qsort(a));
Line 8,591 ⟶ 9,851:
end if;
return a;
end proc;</
=={{header|Sidef}}==
<
a.len < 2 && return(a);
var p = a.pop_rand; # to avoid the worst cases
__FUNC__(a.grep{ .< p}) + [p] + __FUNC__(a.grep{ .>= p});
}</
=={{header|Simula}}==
<
BEGIN
Line 8,631 ⟶ 9,891:
END QUICKSORT;
</syntaxhighlight>
=={{header|Standard ML}}==
<
| quicksort (x::xs) =
let
Line 8,641 ⟶ 9,901:
quicksort left @ [x] @ quicksort right
end
</syntaxhighlight>
------------------------------------------------------------
Line 8,647 ⟶ 9,907:
Without using List.partition
<
fun par_helper([], x, l, r) = (l, r)
| par_helper(h::t, x, l, r) =
Line 8,663 ⟶ 9,923:
in
quicksort left @ [h] @ quicksort right
end;</
=={{header|Swift}}==
<
if (range.endIndex - range.startIndex > 1) {
let pivotIndex = partition(&elements, range)
Line 8,676 ⟶ 9,936:
func quicksort<T where T : Comparable>(inout elements: [T]) {
quicksort(&elements, indices(elements))
}</
=={{header|Symsyn}}==
<
x : 23 : 15 : 99 : 146 : 3 : 66 : 71 : 5 : 23 : 73 : 19
Line 8,753 ⟶ 10,013:
return
</syntaxhighlight>
=={{header|Tailspin}}==
Simple recursive quicksort:
<
templates quicksort
@: [];
Line 8,774 ⟶ 10,034:
[4,5,3,8,1,2,6,7,9,8,5] -> quicksort -> !OUT::write
</syntaxhighlight>
In place:
<
templates quicksort
templates partial
Line 8,783 ⟶ 10,043:
def last: $(2);
def pivot: $@quicksort($first);
$(2) -> #
when
def limit: $
@quicksort($first): $@quicksort($limit);
@quicksort($limit): $pivot;
Line 8,792 ⟶ 10,053:
[ $limit + 1, $last ] !
when <?($@quicksort($
when <?($@quicksort($
otherwise
def temp: $@quicksort($
@quicksort($
@quicksort($
end partial
@: $;
Line 8,813 ⟶ 10,074:
[4,5,3,8,1,2,6,7,9,8,5] -> quicksort -> !OUT::write
</syntaxhighlight>
=={{header|Tcl}}==
<
proc quicksort {m} {
Line 8,830 ⟶ 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.
Line 8,898 ⟶ 10,159:
}
}
</syntaxhighlight>
=={{header|UnixPipes}}==
{{works with|Zsh}}
<
(while read n ; do
test $1 -gt $n && echo $n > $2 || echo $n > $3
Line 8,991 ⟶ 10,179:
}
cat to.sort | qsort</
=={{header|Ursala}}==
Line 9,003 ⟶ 10,191:
natural numbers.
<
quicksort "p" = ~&itB^?a\~&a ^|WrlT/~& "p"*|^\~& "p"?hthPX/~&th ~&h
Line 9,009 ⟶ 10,197:
#cast %nL
example = quicksort(nleq) <694,1377,367,506,3712,381,1704,1580,475,1872></
{{out}}
<pre>
Line 9,017 ⟶ 10,205:
=={{header|V}}==
<
[joinparts [p [*l1] [*l2] : [*l1 p *l2]] view].
[split_on_first uncons [>] split].
Line 9,023 ⟶ 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)
Line 9,200 ⟶ 10,254:
quick_sort(mut arr, 0, n)
println('Output: ' + arr.str())
}</
{{out}}
<pre>Input: [4, 65, 2, -31, 0, 99, 2, 83, 782, 1]
Line 9,206 ⟶ 10,260:
=={{header|Wart}}==
<
(+ (qsort+keep (fn(_) (_ < pivot)) ns)
list.pivot
Line 9,212 ⟶ 10,266:
def (qsort x) :case x=nil
nil</
=={{header|Wren}}==
{{libheader|Wren-sort}}
<
var
[4, 65, 2, -31, 0, 99, 2, 83, 782, 1],
[7, 5, 2, 6, 1, 4, 2, 6, 3],
["echo", "lima", "charlie", "whiskey", "golf", "papa", "alfa", "india", "foxtrot", "kilo"]
]
for (a in
System.print("Before: %(a)")
Sort.quick(a)
System.print("After : %(a)")
System.print()
}</
{{out}}
Line 9,243 ⟶ 10,297:
=={{header|XPL0}}==
<
string 0; \use zero-terminated strings
Line 9,276 ⟶ 10,330:
QSort(Str, StrLen(Str), 1);
Text(0, Str); CrLf(0);
]</
{{out}}
Line 9,285 ⟶ 10,339:
=={{header|Z80 Assembly}}==
sjasmplus syntax
<
; Quicksort, inputs (__sdcccall(1) calling convention):
; HL = uint16_t* A (pointer to beginning of array)
Line 9,400 ⟶ 10,454:
ex de,hl ; HL = A+i
pop de ; DE = end() (and return it preserved)
jp quicksort_a_impl</
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}}==
Line 9,407 ⟶ 10,532:
Quick sort immutable sequence using crappy pivot choice:
<
fcn(list,cmp,N){ // spendy to keep recreating cmp
reg pivot=list[0], rest=list[1,*];
Line 9,414 ⟶ 10,539:
T.extend(self.fcn(left,cmp,N),T(pivot),self.fcn(right,cmp,N));
}(list,cmp,0);
}</
In place quick sort:
<
fcn(list,left,right,cmp){
if (left<right){
Line 9,439 ⟶ 10,564:
}(list,0,list.len()-1,cmp);
list;
}</
|