Sorting algorithms/Quicksort: Difference between revisions
→{{header|Python}}
(Sorting algorithms/Quicksort in True BASIC) |
|||
| (50 intermediate revisions by 20 users not shown) | |||
Line 82:
{{trans|Python}}
<syntaxhighlight lang="11l">F _quicksort(&array, start, stop) ->
I stop - start > 0
V pivot = array[start]
Line 2,534:
=={{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}}===
Line 2,624 ⟶ 2,629:
<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>
Line 2,664 ⟶ 2,962:
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}}===
Line 2,712 ⟶ 3,049:
Loop Until StackPtr = 0
End Sub</syntaxhighlight>
==={{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}}==
Line 2,845 ⟶ 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}}==
Line 3,562 ⟶ 4,435:
<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}}==
Line 3,741 ⟶ 4,512:
items.writeln;
}</syntaxhighlight>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
This quick sort routine is infinitely versatile. It sorts an array of pointers. The advantage of this is that pointers can contain anything, ranging from integers, to strings, to floating point numbers to objects. The way each pointer is interpreted is through the compare routine, which is customized for the particular situation. The compare routine can interpret each pointer as a string, an integer, a float or an object and it can treat those items in different ways. For example, the order in which it compares strings controls whether the sort is alphabetical or reverse alphabetical. In this case, I show an integer sort, an alphabetic string sort, a reverse alphabetical string sort and a string sort by length.
<syntaxhighlight lang="Delphi">
{Dynamic array of pointers}
type TPointerArray = array of Pointer;
procedure QuickSort(SortList: TPointerArray; L, R: Integer; SCompare: TListSortCompare);
{Do quick sort on items held in TPointerArray}
{SCompare controls how the pointers are interpreted}
var I, J: Integer;
var P,T: Pointer;
begin
repeat
begin
I := L;
J := R;
P := SortList[(L + R) shr 1];
repeat
begin
while SCompare(SortList[I], P) < 0 do Inc(I);
while SCompare(SortList[J], P) > 0 do Dec(J);
if I <= J then
begin
{Exchange itesm}
T:=SortList[I];
SortList[I]:=SortList[J];
SortList[J]:=T;
if P = SortList[I] then P := SortList[J]
else if P = SortList[J] then P := SortList[I];
Inc(I);
Dec(J);
end;
end
until I > J;
if L < J then QuickSort(SortList, L, J, SCompare);
L := I;
end
until I >= R;
end;
procedure DisplayStrings(Memo: TMemo; PA: TPointerArray);
{Display pointers as strings}
var I: integer;
var S: string;
begin
S:='[';
for I:=0 to High(PA) do
begin
if I>0 then S:=S+' ';
S:=S+string(PA[I]^);
end;
S:=S+']';
Memo.Lines.Add(S);
end;
procedure DisplayIntegers(Memo: TMemo; PA: TPointerArray);
{Display pointer array as integers}
var I: integer;
var S: string;
begin
S:='[';
for I:=0 to High(PA) do
begin
if I>0 then S:=S+' ';
S:=S+IntToStr(Integer(PA[I]));
end;
S:=S+']';
Memo.Lines.Add(S);
end;
function IntCompare(Item1, Item2: Pointer): Integer;
{Compare for integer sort}
begin
Result:=Integer(Item1)-Integer(Item2);
end;
function StringCompare(Item1, Item2: Pointer): Integer;
{Compare for alphabetical string sort}
begin
Result:=AnsiCompareText(string(Item1^),string(Item2^));
end;
function StringRevCompare(Item1, Item2: Pointer): Integer;
{Compare for reverse alphabetical order}
begin
Result:=AnsiCompareText(string(Item2^),string(Item1^));
end;
function StringLenCompare(Item1, Item2: Pointer): Integer;
{Compare for string length sort}
begin
Result:=Length(string(Item1^))-Length(string(Item2^));
end;
{Arrays of strings and integers}
var IA: array [0..9] of integer = (23, 14, 62, 28, 56, 91, 33, 30, 75, 5);
var SA: array [0..15] of string = ('Now','is','the','time','for','all','good','men','to','come','to','the','aid','of','the','party.');
procedure ShowQuickSort(Memo: TMemo);
var L: TStringList;
var PA: TPointerArray;
var I: integer;
begin
Memo.Lines.Add('Integer Sort');
SetLength(PA,Length(IA));
for I:=0 to High(IA) do PA[I]:=Pointer(IA[I]);
Memo.Lines.Add('Before Sorting');
DisplayIntegers(Memo,PA);
QuickSort(PA,0,High(PA),IntCompare);
Memo.Lines.Add('After Sorting');
DisplayIntegers(Memo,PA);
Memo.Lines.Add('');
Memo.Lines.Add('String Sort - Alphabetical');
SetLength(PA,Length(SA));
for I:=0 to High(SA) do PA[I]:=Pointer(@SA[I]);
Memo.Lines.Add('Before Sorting');
DisplayStrings(Memo,PA);
QuickSort(PA,0,High(PA),StringCompare);
Memo.Lines.Add('After Sorting');
DisplayStrings(Memo,PA);
Memo.Lines.Add('');
Memo.Lines.Add('String Sort - Reverse Alphabetical');
QuickSort(PA,0,High(PA),StringRevCompare);
Memo.Lines.Add('After Sorting');
DisplayStrings(Memo,PA);
Memo.Lines.Add('');
Memo.Lines.Add('String Sort - By Length');
QuickSort(PA,0,High(PA),StringLenCompare);
Memo.Lines.Add('After Sorting');
DisplayStrings(Memo,PA);
end;
</syntaxhighlight>
{{out}}
<pre>
Integer Sort
Before Sorting
[23 14 62 28 56 91 33 30 75 5]
After Sorting
[5 14 23 28 30 33 56 62 75 91]
String Sort - Alphabetical
Before Sorting
[Now is the time for all good men to come to the aid of the party.]
After Sorting
[aid all come for good is men Now party. of the the the time to to]
String Sort - Reverse Alphabetical
After Sorting
[to to time the the the party. of Now men is good for come all aid]
String Sort - By Length
After Sorting
[of is to to men aid all for Now the the the time come good party.]
Elapsed Time: 16.478 ms.
</pre>
=={{header|Dart}}==
Line 3,835 ⟶ 4,781:
=={{header|EasyLang}}==
<syntaxhighlight lang="text">
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 mid + 1 right d[]
.
.
d[] = [ 29 4 72 44 55 26 27 77 92 5 ]
print d[]
</syntaxhighlight>
Line 4,159 ⟶ 5,105:
=={{header|Elena}}==
ELENA
<syntaxhighlight lang="elena">import extensions;
import system'routines;
Line 4,176 ⟶ 5,122:
auto more := new ArrayList();
self.forEach::(item)
{
if (item < pivot)
Line 4,459 ⟶ 5,405:
=={{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}}==
Line 4,674 ⟶ 5,486:
[0, 1, 2, 2, 3, 4]
[Daniel, Ethan, Jacob, Juan, Liam, Miguel, William]
</pre>
Line 5,429 ⟶ 6,153:
val ys = xx.filter fn(el) { el < x }
val zs = xx.filter fn(el) { el >= x }
qsort(ys) ++ [x] ++ qsort(zs)
}
Nil -> Nil
Line 5,440 ⟶ 6,164:
Cons(x,xx) -> {
val (ys, zs) = xx.partition fn(el) { el < x }
qsort(ys) ++ [x] ++ qsort(zs)
}
Nil -> Nil
Line 7,826 ⟶ 8,550:
</syntaxhighlight>
=={{header|
<syntaxhighlight lang="
lesser = []
equal = []
greater = []
if len(sequence) <= 1:
return sequence
pivot = sequence[0]
for element in sequence:
if element < pivot:
lesser.append(element)
elif element > pivot:
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 = quick_sort(a)
</syntaxhighlight>
In a Haskell fashion --
Line 7,960 ⟶ 8,646:
_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}}==
Line 8,046 ⟶ 8,746:
=={{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.
#| 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}}==
Line 8,435 ⟶ 9,264:
return</syntaxhighlight>
=={{header|Refal}}==
<syntaxhighlight lang="refal">$ENTRY Go {
, 7 6 5 9 8 4 3 1 2 0: e.Arr
= <Prout e.Arr>
<Prout <Sort e.Arr>>;
};
Sort {
= ;
s.N = s.N;
s.Pivot e.X =
<Sort <Filter s.Pivot '-' e.X>>
<Filter s.Pivot '=' e.X>
s.Pivot
<Sort <Filter s.Pivot '+' e.X>>;
};
Filter {
s.N s.Comp = ;
s.N s.Comp s.I e.List, <Compare s.I s.N>: {
s.Comp = s.I <Filter s.N s.Comp e.List>;
s.X = <Filter s.N s.Comp e.List>;
};
};</syntaxhighlight>
{{out}}
<pre>7 6 5 9 8 4 3 1 2 0
0 1 2 3 4 5 6 7 8 9</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
Line 8,491 ⟶ 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}}==
Line 8,518 ⟶ 9,393:
end
end</syntaxhighlight>
=={{header|Rust}}==
Line 9,215 ⟶ 10,043:
def last: $(2);
def pivot: $@quicksort($first);
$(2) -> #
when
def limit: $
@quicksort($first): $@quicksort($limit);
@quicksort($limit): $pivot;
Line 9,224 ⟶ 10,053:
[ $limit + 1, $last ] !
when <?($@quicksort($
when <?($@quicksort($
otherwise
def temp: $@quicksort($
@quicksort($
@quicksort($
end partial
@: $;
Line 9,263 ⟶ 10,092:
puts [quicksort {8 6 4 2 1 3 5 7 9}] ;# => 1 2 3 4 5 6 7 8 9</syntaxhighlight>
=={{header|TypeScript}}==
Line 9,384 ⟶ 10,160:
}
</syntaxhighlight>
=={{header|UnixPipes}}==
Line 9,518 ⟶ 10,221:
{{omit from|GUISS}}
=={{header|V (Vlang)}}==
Line 9,705 ⟶ 10,270:
=={{header|Wren}}==
{{libheader|Wren-sort}}
<syntaxhighlight lang="
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)
Line 9,891 ⟶ 10,456:
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}}==
| |||