Sorting algorithms/Quicksort: Difference between revisions
→{{header|PascalABC.NET}}
(→{{header|BASIC}}: ANSI BASIC added.) |
|||
| (5 intermediate revisions by 5 users not shown) | |||
Line 3,419:
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}}===
Line 4,691 ⟶ 4,780:
=={{header|EasyLang}}==
<syntaxhighlight
proc qsort left right . d[] .
.
.
.
swap d[left] d[mid]
qsort left mid - 1 d[]
qsort mid + 1 right d[]
.
proc sort . d[] .
Line 4,721 ⟶ 4,803:
print d[]
</syntaxhighlight>
{{out}}
<pre>
[ 4 5 26 27 29 44 55 72 77 92 ]
</pre>
=={{header|EchoLisp}}==
Line 8,175 ⟶ 8,261:
<pre>
[-50, -34, -25, -20, -10, 5, 9, 11, 13, 19, 29, 30, 35, 36]
</pre>
=={{header|PascalABC.NET}}==
<syntaxhighlight lang="delphi">
function Partition(a: array of integer; l,r: integer): integer;
begin
var i := l - 1;
var j := r + 1;
var x := a[l];
while True do
begin
repeat
i += 1;
until a[i]>=x;
repeat
j -= 1;
until a[j]<=x;
if i<j then
Swap(a[i],a[j])
else
begin
Result := j;
exit;
end;
end;
end;
procedure QuickSort(a: array of integer; l,r: integer);
begin
if l>=r then exit;
var j := Partition(a,l,r);
QuickSort(a,l,j);
QuickSort(a,j+1,r);
end;
const n = 20;
begin
var a := ArrRandom(n);
Println('Before: ');
Println(a);
QuickSort(a,0,a.Length-1);
Println('After sorting: ');
Println(a);
end.
</syntaxhighlight>
{{out}}
<pre>
Before:
[67,95,79,96,14,56,25,9,4,56,70,62,33,52,13,12,73,19,8,72]
After sorting:
[4,8,9,12,13,14,19,25,33,52,56,56,62,67,70,72,73,79,95,96]
</pre>
Line 8,557 ⟶ 8,695:
_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 = list(filter(lambda x: x < pivot, unsorted_list))
same = list(filter(lambda x: x == pivot, unsorted_list))
more = list(filter(lambda x: x > pivot, unsorted_list))
return quicksort(less) + same + quicksort(more)
</syntaxhighlight>
=={{header|Qi}}==
| |||