Sorting algorithms/Quicksort: Difference between revisions
→{{header|Python}}
m (→version 1: added wording to the REXX version section header.) |
|||
| (145 intermediate revisions by 49 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.
<syntaxhighlight lang="action!">DEFINE MAX_COUNT="100"
INT ARRAY stack(MAX_COUNT)
INT stackSize
PROC PrintArray(INT ARRAY a INT size)
INT i
Put('[)
FOR i=0 TO size-1
DO
IF i>0 THEN Put(' ) FI
PrintI(a(i))
OD
Put(']) PutE()
RETURN
PROC InitStack()
stackSize=0
RETURN
BYTE FUNC IsEmpty()
IF stackSize=0 THEN
RETURN (1)
FI
RETURN (0)
PROC Push(INT low,high)
stack(stackSize)=low stackSize==+1
stack(stackSize)=high stackSize==+1
RETURN
PROC Pop(INT POINTER low,high)
stackSize==-1 high^=stack(stackSize)
stackSize==-1 low^=stack(stackSize)
RETURN
INT FUNC Partition(INT ARRAY a INT low,high)
INT part,v,i,tmp
v=a(high)
part=low-1
FOR i=low TO high-1
DO
IF a(i)<=v THEN
part==+1
tmp=a(part) a(part)=a(i) a(i)=tmp
FI
OD
part==+1
tmp=a(part) a(part)=a(high) a(high)=tmp
RETURN (part)
PROC QuickSort(INT ARRAY a INT size)
INT low,high,part
InitStack()
Push(0,size-1)
WHILE IsEmpty()=0
DO
Pop(@low,@high)
part=Partition(a,low,high)
IF part-1>low THEN
Push(low,part-1)
FI
IF part+1<high THEN
Push(part+1,high)
FI
OD
RETURN
PROC Test(INT ARRAY a INT size)
PrintE("Array before sort:")
PrintArray(a,size)
QuickSort(a,size)
PrintE("Array after sort:")
PrintArray(a,size)
PutE()
RETURN
PROC Main()
INT ARRAY
a(10)=[1 4 65535 0 3 7 4 8 20 65530],
b(21)=[10 9 8 7 6 5 4 3 2 1 0
65535 65534 65533 65532 65531
65530 65529 65528 65527 65526],
c(8)=[101 102 103 104 105 106 107 108],
d(12)=[1 65535 1 65535 1 65535 1
65535 1 65535 1 65535]
Test(a,10)
Test(b,21)
Test(c,8)
Test(d,12)
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Quicksort.png Screenshot from Atari 8-bit computer]
<pre>
Array before sort:
[1 4 -1 0 3 7 4 8 20 -6]
Array after sort:
[-6 -1 0 1 3 4 4 7 8 20]
Array before sort:
[10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10]
Array after sort:
[-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10]
Array before sort:
[101 102 103 104 105 106 107 108]
Array after sort:
[101 102 103 104 105 106 107 108]
Array before sort:
[1 -1 1 -1 1 -1 1 -1 1 -1 1 -1]
Array after sort:
[-1 -1 -1 -1 -1 -1 1 1 1 1 1 1]
</pre>
=={{header|ActionScript}}==
{{works with|ActionScript|3}}<br>
The functional programming way
<
{
if (array.length <= 1)
Line 585 ⟶ 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 611 ⟶ 733:
equal).concat(
quickSort(greater));
}</
=={{header|Ada}}==
Line 617 ⟶ 739:
The procedure specification is:
<
-- Generic Quick_Sort procedure
-----------------------------------------------------------------------
Line 625 ⟶ 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 670 ⟶ 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 704 ⟶ 826:
Print(Weekly_Sales);
end Sort_Test;</
=={{header|ALGOL 68}}==
<
PROC swap = (REF []INT array, INT first, INT second) VOID:
(
Line 769 ⟶ 891:
print(("After: ", a))
)
</syntaxhighlight>
{{out}}
<pre>
Line 778 ⟶ 900:
=={{header|ALGOL W}}==
<
procedure quicksort ( integer array v( * )
; integer value lb, ub
Line 803 ⟶ 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 824 ⟶ 946:
(Functional ES5 version)
<
on quickSort(xs)
if length of xs > 1 then
Line 889 ⟶ 1,011:
end script
end if
end mReturn</
{{Out}}
<
----
===Straightforward===
Emphasising clarity,
<
-- Algorithm: S.A.R. (Tony) Hoare, 1960.
on quicksort(theList, l, r) -- Sort items l thru r of theList.
set listLength to (count theList)
if (listLength < 2) then return
-- Convert negative and/or transposed range indices.
if (l < 0) then set l to listLength + l + 1
if (r < 0) then set r to listLength + r + 1
if (l > r) then set {l, r} to {r, l}
-- Script object containing the list as a property (to allow faster references to its items)
-- and the recursive subhandler.
script o
property lst : theList
Line 912 ⟶ 1,040:
set j to r
repeat until (i > j)
set
repeat while (
set i to i + 1
set
end repeat
set
repeat while (
set j to j - 1
set
end repeat
if (j > i) then
set my lst's item i to
set my lst's item j to
else if (i > j) then
exit repeat
Line 940 ⟶ 1,068:
end script
return -- nothing
end quicksort
property sort : quicksort
--
local aList
set aList to {28, 9, 95, 22, 67, 55, 20, 41, 60, 53, 100, 72, 19, 67, 14, 42, 29, 20, 74, 39}
sort(aList, 1, -1) -- Sort
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,227 ⟶ 1,348:
iMagicNumber: .int 0xCCCCCCCD
</syntaxhighlight>
=={{header|Arturo}}==
<
if 2 > size items -> return items
Line 1,241 ⟶ 1,362:
]
print quickSort [3 1 2 8 5 7 9 4 6]</
{{out}}
<pre>1 2 3 4 5 6 7 8 9</pre>
=={{header|ATS}}==
=== A quicksort working on non-linear linked lists ===
<syntaxhighlight lang="ats">(*------------------------------------------------------------------*)
(* Quicksort in ATS2, for non-linear lists. *)
(*------------------------------------------------------------------*)
#include "share/atspre_staload.hats"
#define NIL list_nil ()
#define :: list_cons
(*------------------------------------------------------------------*)
(* A simple quicksort working on "garbage-collected" linked lists,
with first element as pivot. This is meant as a demonstration, not
as a superior sort algorithm.
It is based on the "not-in-place" task pseudocode. *)
datatype comparison_result =
| first_is_less_than_second of ()
| first_is_equal_to_second of ()
| first_is_greater_than_second of ()
extern fun {a : t@ype}
list_quicksort$comparison (x : a, y : a) :<> comparison_result
extern fun {a : t@ype}
list_quicksort {n : int}
(lst : list (a, n)) :<> list (a, n)
(* - - - - - - - - - - - - - - - - - - - - - - *)
implement {a}
list_quicksort {n} (lst) =
let
fun
partition {n : nat}
.<n>. (* Proof of termination. *)
(lst : list (a, n),
pivot : a)
:<> [n1, n2, n3 : int | n1 + n2 + n3 == n]
@(list (a, n1), list (a, n2), list (a, n3)) =
(* This implementation is *not* tail recursive. I may get a
scolding for using ATS to risk stack overflow! However, I
need more practice writing non-tail routines. :) Also, a lot
of programmers in other languages would do it this
way--especially if the lists are evaluated lazily. *)
case+ lst of
| NIL => @(NIL, NIL, NIL)
| head :: tail =>
let
val @(lt, eq, gt) = partition (tail, pivot)
prval () = lemma_list_param lt
prval () = lemma_list_param eq
prval () = lemma_list_param gt
in
case+ list_quicksort$comparison<a> (head, pivot) of
| first_is_less_than_second () => @(head :: lt, eq, gt)
| first_is_equal_to_second () => @(lt, head :: eq, gt)
| first_is_greater_than_second () => @(lt, eq, head :: gt)
end
fun
quicksort {n : nat}
.<n>. (* Proof of termination. *)
(lst : list (a, n))
:<> list (a, n) =
case+ lst of
| NIL => lst
| _ :: NIL => lst
| head :: tail =>
let
(* We are careful here to run "partition" on "tail" rather
than "lst", so the termination metric will be provably
decreasing. (Really the compiler *forces* us to take such
care, or else to change :<> to :<!ntm>) *)
val pivot = head
prval () = lemma_list_param tail
val @(lt, eq, gt) = partition {n - 1} (tail, pivot)
prval () = lemma_list_param lt
prval () = lemma_list_param eq
prval () = lemma_list_param gt
val eq = pivot :: eq
and lt = quicksort lt
and gt = quicksort gt
in
lt + (eq + gt)
end
prval () = lemma_list_param lst
in
quicksort {n} lst
end
(*------------------------------------------------------------------*)
val example_strings =
$list ("choose", "any", "element", "of", "the", "array",
"to", "be", "the", "pivot",
"divide", "all", "other", "elements", "except",
"the", "pivot", "into", "two", "partitions",
"all", "elements", "less", "than", "the", "pivot",
"must", "be", "in", "the", "first", "partition",
"all", "elements", "greater", "than", "the", "pivot",
"must", "be", "in", "the", "second", "partition",
"use", "recursion", "to", "sort", "both", "partitions",
"join", "the", "first", "sorted", "partition", "the",
"pivot", "and", "the", "second", "sorted", "partition")
implement
list_quicksort$comparison<string> (x, y) =
let
val i = strcmp (x, y)
in
if i < 0 then
first_is_less_than_second
else if i = 0 then
first_is_equal_to_second
else
first_is_greater_than_second
end
implement
main0 () =
let
val sorted_strings = list_quicksort<string> example_strings
fun
print_strings {n : nat} .<n>.
(strings : list (string, n),
i : int) : void =
case+ strings of
| NIL => if i <> 1 then println! () else ()
| head :: tail =>
begin
print! head;
if i = 8 then
begin
println! ();
print_strings (tail, 1)
end
else
begin
print! " ";
print_strings (tail, succ i)
end
end
in
println! (length example_strings);
println! (length sorted_strings);
print_strings (sorted_strings, 1)
end
(*------------------------------------------------------------------*)</syntaxhighlight>
{{out}}
<pre>$ patscc -O3 -DATS_MEMALLOC_GCBDW quicksort_task_for_lists.dats -lgc && ./a.out
62
62
all all all and any array be be
be both choose divide element elements elements elements
except first first greater in in into join
less must must of other partition partition partition
partition partitions partitions pivot pivot pivot pivot pivot
recursion second second sort sorted sorted than than
the the the the the the the the
the the to to two use</pre>
=== A quicksort working on linear linked lists ===
This program was derived from the quicksort for non-linear linked lists.
<syntaxhighlight lang="ats">(*------------------------------------------------------------------*)
(* Quicksort in ATS2, for linear lists. *)
(*------------------------------------------------------------------*)
#include "share/atspre_staload.hats"
#define NIL list_vt_nil ()
#define :: list_vt_cons
(*------------------------------------------------------------------*)
(* A simple quicksort working on linear linked lists, with first
element as pivot. This is meant as a demonstration, not as a
superior sort algorithm.
It is based on the "not-in-place" task pseudocode. *)
#define FIRST_IS_LESS_THAN_SECOND 1
#define FIRST_IS_EQUAL_TO_SECOND 2
#define FIRST_IS_GREATER_THAN_SECOND 3
typedef comparison_result =
[i : int | (i == FIRST_IS_LESS_THAN_SECOND ||
i == FIRST_IS_EQUAL_TO_SECOND ||
i == FIRST_IS_GREATER_THAN_SECOND)]
int i
extern fun {a : vt@ype}
list_vt_quicksort$comparison (x : !a, y : !a) :<> comparison_result
extern fun {a : vt@ype}
list_vt_quicksort {n : int}
(lst : list_vt (a, n)) :<!wrt> list_vt (a, n)
(* - - - - - - - - - - - - - - - - - - - - - - *)
implement {a}
list_vt_quicksort {n} (lst) =
let
fun
partition {n : nat}
.<n>. (* Proof of termination. *)
(lst : list_vt (a, n),
pivot : !a)
:<> [n1, n2, n3 : int | n1 + n2 + n3 == n]
@(list_vt (a, n1), list_vt (a, n2), list_vt (a, n3)) =
(* This implementation is *not* tail recursive. I may get a
scolding for using ATS to risk stack overflow! However, I
need more practice writing non-tail routines. :) Also, a lot
of programmers in other languages would do it this
way--especially if the lists are evaluated lazily. *)
case+ lst of
| ~ NIL => @(NIL, NIL, NIL)
| ~ head :: tail =>
let
val @(lt, eq, gt) = partition (tail, pivot)
prval () = lemma_list_vt_param lt
prval () = lemma_list_vt_param eq
prval () = lemma_list_vt_param gt
in
case+ list_vt_quicksort$comparison<a> (head, pivot) of
| FIRST_IS_LESS_THAN_SECOND => @(head :: lt, eq, gt)
| FIRST_IS_EQUAL_TO_SECOND => @(lt, head :: eq, gt)
| FIRST_IS_GREATER_THAN_SECOND => @(lt, eq, head :: gt)
end
fun
quicksort {n : nat}
.<n>. (* Proof of termination. *)
(lst : list_vt (a, n))
:<!wrt> list_vt (a, n) =
case+ lst of
| NIL => lst
| _ :: NIL => lst
| ~ head :: tail =>
let
(* We are careful here to run "partition" on "tail" rather
than "lst", so the termination metric will be provably
decreasing. (Really the compiler *forces* us to take such
care, or else to add !ntm to the effects.) *)
val pivot = head
prval () = lemma_list_vt_param tail
val @(lt, eq, gt) = partition {n - 1} (tail, pivot)
prval () = lemma_list_vt_param lt
prval () = lemma_list_vt_param eq
prval () = lemma_list_vt_param gt
val eq = pivot :: eq
and lt = quicksort lt
and gt = quicksort gt
in
list_vt_append (lt, list_vt_append (eq, gt))
end
prval () = lemma_list_vt_param lst
in
quicksort {n} lst
end
(*------------------------------------------------------------------*)
implement
list_vt_quicksort$comparison<Strptr1> (x, y) =
let
val i = compare (x, y)
in
if i < 0 then
FIRST_IS_LESS_THAN_SECOND
else if i = 0 then
FIRST_IS_EQUAL_TO_SECOND
else
FIRST_IS_GREATER_THAN_SECOND
end
implement
list_vt_map$fopr<string><Strptr1> (s) = string0_copy s
implement
list_vt_freelin$clear<Strptr1> (x) = strptr_free x
implement
main0 () =
let
val example_strings =
$list_vt
("choose", "any", "element", "of", "the", "array",
"to", "be", "the", "pivot",
"divide", "all", "other", "elements", "except",
"the", "pivot", "into", "two", "partitions",
"all", "elements", "less", "than", "the", "pivot",
"must", "be", "in", "the", "first", "partition",
"all", "elements", "greater", "than", "the", "pivot",
"must", "be", "in", "the", "second", "partition",
"use", "recursion", "to", "sort", "both", "partitions",
"join", "the", "first", "sorted", "partition", "the",
"pivot", "and", "the", "second", "sorted", "partition")
val example_strptrs =
list_vt_map<string><Strptr1> (example_strings)
val sorted_strptrs = list_vt_quicksort<Strptr1> example_strptrs
fun
print_strptrs {n : nat} .<n>.
(strptrs : !list_vt (Strptr1, n),
i : int) : void =
case+ strptrs of
| NIL => if i <> 1 then println! () else ()
| @ head :: tail =>
begin
print! head;
if i = 8 then
begin
println! ();
print_strptrs (tail, 1)
end
else
begin
print! " ";
print_strptrs (tail, succ i)
end;
fold@ strptrs
end
in
println! (length example_strings);
println! (length sorted_strptrs);
print_strptrs (sorted_strptrs, 1);
list_vt_freelin<Strptr1> sorted_strptrs;
list_vt_free<string> example_strings
end
(*------------------------------------------------------------------*)</syntaxhighlight>
{{out}}
<pre>$ patscc -O3 -DATS_MEMALLOC_LIBC quicksort_task_for_list_vt.dats && ./a.out
62
62
all all all and any array be be
be both choose divide element elements elements elements
except first first greater in in into join
less must must of other partition partition partition
partition partitions partitions pivot pivot pivot pivot pivot
recursion second second sort sorted sorted than than
the the the the the the the the
the the to to two use</pre>
=== A quicksort working on arrays of non-linear elements ===
<syntaxhighlight lang="ats">(*------------------------------------------------------------------*)
(* Quicksort in ATS2, for arrays of non-linear values. *)
(*------------------------------------------------------------------*)
#include "share/atspre_staload.hats"
#define NIL list_nil ()
#define :: list_cons
(*------------------------------------------------------------------*)
(* A simple quicksort working on arrays of non-linear values, using
a programmer-selectible pivot.
It is based on the "in-place" task pseudocode. *)
extern fun {a : t@ype} (* A "less-than" predicate. *)
array_quicksort$lt (x : a, y : a) : bool
extern fun {a : t@ype}
array_quicksort$select_pivot {n : int}
{i, j : nat | i < j; j < n}
(arr : &array (a, n) >> _,
first : size_t i,
last : size_t j) : a
extern fun {a : t@ype}
array_quicksort {n : int}
(arr : &array (a, n) >> _,
n : size_t n) : void
(* - - - - - - - - - - - - - - - - - - - - - - *)
fn {a : t@ype}
swap {n : int}
{i, j : nat | i < n; j < n}
(arr : &array(a, n) >> _,
i : size_t i,
j : size_t j) : void =
{
val x = arr[i] and y = arr[j]
val () = (arr[i] := y) and () = (arr[j] := x)
}
implement {a}
array_quicksort {n} (arr, n) =
let
sortdef index = {i : nat | i < n}
typedef index (i : int) = [0 <= i; i < n] size_t i
typedef index = [i : index] index i
macdef lt = array_quicksort$lt<a>
fun
quicksort {i, j : index}
(arr : &array(a, n) >> _,
first : index i,
last : index j) : void =
if first < last then
{
val pivot : a =
array_quicksort$select_pivot<a> (arr, first, last)
fun
search_rightwards (arr : &array (a, n),
left : index) : index =
if arr[left] \lt pivot then
let
val () = assertloc (succ left <> n)
in
search_rightwards (arr, succ left)
end
else
left
fun
search_leftwards (arr : &array (a, n),
left : index,
right : index) : index =
if right < left then
right
else if pivot \lt arr[right] then
let
val () = assertloc (right <> i2sz 0)
in
search_leftwards (arr, left, pred right)
end
else
right
fun
partition (arr : &array (a, n) >> _,
left0 : index,
right0 : index) : @(index, index) =
let
val left = search_rightwards (arr, left0)
val right = search_leftwards (arr, left, right0)
in
if left <= right then
let
val () = assertloc (succ left <> n)
and () = assertloc (right <> i2sz 0)
in
swap (arr, left, right);
partition (arr, succ left, pred right)
end
else
@(left, right)
end
val @(left, right) = partition (arr, first, last)
val () = quicksort (arr, first, right)
and () = quicksort (arr, left, last)
}
in
if i2sz 2 <= n then
quicksort {0, n - 1} (arr, i2sz 0, pred n)
end
(*------------------------------------------------------------------*)
val example_strings =
$list ("choose", "any", "element", "of", "the", "array",
"to", "be", "the", "pivot",
"divide", "all", "other", "elements", "except",
"the", "pivot", "into", "two", "partitions",
"all", "elements", "less", "than", "the", "pivot",
"must", "be", "in", "the", "first", "partition",
"all", "elements", "greater", "than", "the", "pivot",
"must", "be", "in", "the", "second", "partition",
"use", "recursion", "to", "sort", "both", "partitions",
"join", "the", "first", "sorted", "partition", "the",
"pivot", "and", "the", "second", "sorted", "partition")
implement
array_quicksort$lt<string> (x, y) =
strcmp (x, y) < 0
implement
array_quicksort$select_pivot<string> {n} (arr, first, last) =
(* Median of three, with swapping around of elements during pivot
selection. See https://archive.ph/oYENx *)
let
macdef lt = array_quicksort$lt<string>
val middle = first + ((last - first) / i2sz 2)
val xfirst = arr[first]
and xmiddle = arr[middle]
and xlast = arr[last]
in
if (xmiddle \lt xfirst) xor (xlast \lt xfirst) then
begin
swap (arr, first, middle);
if xlast \lt xmiddle then
swap (arr, first, last);
xfirst
end
else if (xmiddle \lt xfirst) xor (xmiddle \lt xlast) then
begin
if xlast \lt xfirst then
swap (arr, first, last);
xmiddle
end
else
begin
swap (arr, middle, last);
if xmiddle \lt xfirst then
swap (arr, first, last);
xlast
end
end
implement
main0 () =
let
prval () = lemma_list_param example_strings
val n = length example_strings
val @(pf, pfgc | p) = array_ptr_alloc<string> (i2sz n)
macdef arr = !p
val () = array_initize_list (arr, n, example_strings)
val () = array_quicksort<string> (arr, i2sz n)
val sorted_strings = list_vt2t (array2list (arr, i2sz n))
val () = array_ptr_free (pf, pfgc | p)
fun
print_strings {n : nat} .<n>.
(strings : list (string, n),
i : int) : void =
case+ strings of
| NIL => if i <> 1 then println! () else ()
| head :: tail =>
begin
print! head;
if i = 8 then
begin
println! ();
print_strings (tail, 1)
end
else
begin
print! " ";
print_strings (tail, succ i)
end
end
in
println! (length example_strings);
println! (length sorted_strings);
print_strings (sorted_strings, 1)
end
(*------------------------------------------------------------------*)</syntaxhighlight>
{{out}}
<pre>$ patscc -O3 -DATS_MEMALLOC_GCBDW quicksort_task_for_arrays.dats -lgc && ./a.out
62
62
all all all and any array be be
be both choose divide element elements elements elements
except first first greater in in into join
less must must of other partition partition partition
partition partitions partitions pivot pivot pivot pivot pivot
recursion second second sort sorted sorted than than
the the the the the the the the
the the to to two use</pre>
=== A quicksort working on arrays of linear elements ===
The quicksort for arrays of non-linear elements ''makes a copy'' of the pivot value, and compares this copy with array elements ''by value''. Here, however, the array elements are ''linear'' values. They cannot be copied, unless a special "copy" procedure is provided. We do not want to require such a procedure. So we must do something else.
What we do is move the pivot to the last element of the array, by safely swapping it with the original last element. We partition the array to the left of the last element, comparing array elements with the pivot (that is, the last element) ''by reference''.
<syntaxhighlight lang="ats">(*------------------------------------------------------------------*)
(* Quicksort in ATS2, for arrays of (possibly) linear values. *)
(*------------------------------------------------------------------*)
#include "share/atspre_staload.hats"
#define NIL list_vt_nil ()
#define :: list_vt_cons
(*------------------------------------------------------------------*)
(* A simple quicksort working on arrays of non-linear values, using
a programmer-selectible pivot.
It is based on the "in-place" task pseudocode. *)
extern fun {a : vt@ype} (* A "less-than" predicate. *)
array_quicksort$lt {px, py : addr}
(pfx : !(a @ px),
pfy : !(a @ py) |
px : ptr px,
py : ptr py) : bool
extern fun {a : vt@ype}
array_quicksort$select_pivot_index {n : int}
{i, j : nat | i < j; j < n}
(arr : &array (a, n),
first : size_t i,
last : size_t j)
: [k : int | i <= k; k <= j] size_t k
extern fun {a : vt@ype}
array_quicksort {n : int}
(arr : &array (a, n) >> _,
n : size_t n) : void
(* - - - - - - - - - - - - - - - - - - - - - - *)
prfn (* Subdivide an array view into three views. *)
array_v_subdivide3 {a : vt@ype} {p : addr} {n1, n2, n3 : nat}
(pf : @[a][n1 + n2 + n3] @ p)
:<prf> @(@[a][n1] @ p,
@[a][n2] @ (p + n1 * sizeof a),
@[a][n3] @ (p + (n1 + n2) * sizeof a)) =
let
prval (pf1, pf23) =
array_v_split {a} {p} {n1 + n2 + n3} {n1} pf
prval (pf2, pf3) =
array_v_split {a} {p + n1 * sizeof a} {n2 + n3} {n2} pf23
in
@(pf1, pf2, pf3)
end
prfn (* Join three contiguous array views into one view. *)
array_v_join3 {a : vt@ype} {p : addr} {n1, n2, n3 : nat}
(pf1 : @[a][n1] @ p,
pf2 : @[a][n2] @ (p + n1 * sizeof a),
pf3 : @[a][n3] @ (p + (n1 + n2) * sizeof a))
:<prf> @[a][n1 + n2 + n3] @ p =
let
prval pf23 =
array_v_unsplit {a} {p + n1 * sizeof a} {n2, n3} (pf2, pf3)
prval pf = array_v_unsplit {a} {p} {n1, n2 + n3} (pf1, pf23)
in
pf
end
fn {a : vt@ype} (* Safely swap two elements of an array. *)
swap_elems_1 {n : int}
{i, j : nat | i <= j; j < n}
{p : addr}
(pfarr : !array_v(a, p, n) >> _ |
p : ptr p,
i : size_t i,
j : size_t j) : void =
let
fn {a : vt@ype}
swap {n : int}
{i, j : nat | i < j; j < n}
{p : addr}
(pfarr : !array_v(a, p, n) >> _ |
p : ptr p,
i : size_t i,
j : size_t j) : void =
{
(* Safely swapping linear elements requires that views of
those elements be split off from the rest of the
array. Why? Because those elements will temporarily be in
an uninitialized state. (Actually they will be "?!", but
the difference is unimportant here.)
Remember, a linear value is consumed by using it.
The view for the whole array can be reassembled only after
new values have been stored, making the entire array once
again initialized. *)
prval @(pf1, pf2, pf3) =
array_v_subdivide3 {a} {p} {i, j - i, n - j} pfarr
prval @(pfi, pf2_) = array_v_uncons pf2
prval @(pfj, pf3_) = array_v_uncons pf3
val pi = ptr_add<a> (p, i)
and pj = ptr_add<a> (p, j)
val xi = ptr_get<a> (pfi | pi)
and xj = ptr_get<a> (pfj | pj)
val () = ptr_set<a> (pfi | pi, xj)
and () = ptr_set<a> (pfj | pj, xi)
prval pf2 = array_v_cons (pfi, pf2_)
prval pf3 = array_v_cons (pfj, pf3_)
prval () = pfarr := array_v_join3 (pf1, pf2, pf3)
}
in
if i < j then
swap {n} {i, j} {p} (pfarr | p, i, j)
else
() (* i = j must be handled specially, due to linear typing.*)
end
fn {a : vt@ype} (* Safely swap two elements of an array. *)
swap_elems_2 {n : int}
{i, j : nat | i <= j; j < n}
(arr : &array(a, n) >> _,
i : size_t i,
j : size_t j) : void =
swap_elems_1 (view@ arr | addr@ arr, i, j)
overload swap_elems with swap_elems_1
overload swap_elems with swap_elems_2
overload swap with swap_elems
fn {a : vt@ype} (* Safely compare two elements of an array. *)
lt_elems_1 {n : int}
{i, j : nat | i < n; j < n}
{p : addr}
(pfarr : !array_v(a, p, n) |
p : ptr p,
i : size_t i,
j : size_t j) : bool =
let
fn
compare {n : int}
{i, j : nat | i < j; j < n}
{p : addr}
(pfarr : !array_v(a, p, n) |
p : ptr p,
i : size_t i,
j : size_t j,
gt : bool) : bool =
let
prval @(pf1, pf2, pf3) =
array_v_subdivide3 {a} {p} {i, j - i, n - j} pfarr
prval @(pfi, pf2_) = array_v_uncons pf2
prval @(pfj, pf3_) = array_v_uncons pf3
val pi = ptr_add<a> (p, i)
and pj = ptr_add<a> (p, j)
val retval =
if gt then
array_quicksort$lt<a> (pfj, pfi | pj, pi)
else
array_quicksort$lt<a> (pfi, pfj | pi, pj)
prval pf2 = array_v_cons (pfi, pf2_)
prval pf3 = array_v_cons (pfj, pf3_)
prval () = pfarr := array_v_join3 (pf1, pf2, pf3)
in
retval
end
in
if i < j then
compare {n} {i, j} {p} (pfarr | p, i, j, false)
else if j < i then
compare {n} {j, i} {p} (pfarr | p, j, i, true)
else
false
end
fn {a : vt@ype} (* Safely compare two elements of an array. *)
lt_elems_2 {n : int}
{i, j : nat | i < n; j < n}
(arr : &array (a, n),
i : size_t i,
j : size_t j) : bool =
lt_elems_1 (view@ arr | addr@ arr, i, j)
overload lt_elems with lt_elems_1
overload lt_elems with lt_elems_2
implement {a}
array_quicksort {n} (arr, n) =
let
sortdef index = {i : nat | i < n}
typedef index (i : int) = [0 <= i; i < n] size_t i
typedef index = [i : index] index i
macdef lt = array_quicksort$lt<a>
fun
quicksort {i, j : index}
(arr : &array(a, n) >> _,
first : index i,
last : index j) : void =
if first < last then
{
val pivot =
array_quicksort$select_pivot_index<a> (arr, first, last)
(* Swap the pivot with the last element. *)
val () = swap (arr, pivot, last)
val pivot = last
fun
search_rightwards (arr : &array (a, n),
left : index) : index =
if lt_elems<a> (arr, left, pivot) then
let
val () = assertloc (succ left <> n)
in
search_rightwards (arr, succ left)
end
else
left
fun
search_leftwards (arr : &array (a, n),
left : index,
right : index) : index =
if right < left then
right
else if lt_elems<a> (arr, pivot, right) then
let
val () = assertloc (right <> i2sz 0)
in
search_leftwards (arr, left, pred right)
end
else
right
fun
partition (arr : &array (a, n) >> _,
left0 : index,
right0 : index) : @(index, index) =
let
val left = search_rightwards (arr, left0)
val right = search_leftwards (arr, left, right0)
in
if left <= right then
let
val () = assertloc (succ left <> n)
and () = assertloc (right <> i2sz 0)
in
swap (arr, left, right);
partition (arr, succ left, pred right)
end
else
@(left, right)
end
val @(left, right) = partition (arr, first, pred last)
val () = quicksort (arr, first, right)
and () = quicksort (arr, left, last)
}
in
if i2sz 2 <= n then
quicksort {0, n - 1} (arr, i2sz 0, pred n)
end
(*------------------------------------------------------------------*)
implement
array_quicksort$lt<Strptr1> (pfx, pfy | px, py) =
compare (!px, !py) < 0
implement
array_quicksort$select_pivot_index<Strptr1> {n} (arr, first, last) =
(* Median of three. *)
let
val middle = first + ((last - first) / i2sz 2)
in
if lt_elems<Strptr1> (arr, middle, first)
xor lt_elems<Strptr1> (arr, last, first) then
first
else if lt_elems<Strptr1> (arr, middle, first)
xor lt_elems<Strptr1> (arr, middle, last) then
middle
else
last
end
implement
list_vt_map$fopr<string><Strptr1> (s) = string0_copy s
implement
list_vt_freelin$clear<Strptr1> (x) = strptr_free x
implement
main0 () =
let
val example_strings =
$list_vt
("choose", "any", "element", "of", "the", "array",
"to", "be", "the", "pivot",
"divide", "all", "other", "elements", "except",
"the", "pivot", "into", "two", "partitions",
"all", "elements", "less", "than", "the", "pivot",
"must", "be", "in", "the", "first", "partition",
"all", "elements", "greater", "than", "the", "pivot",
"must", "be", "in", "the", "second", "partition",
"use", "recursion", "to", "sort", "both", "partitions",
"join", "the", "first", "sorted", "partition", "the",
"pivot", "and", "the", "second", "sorted", "partition")
val example_strptrs =
list_vt_map<string><Strptr1> (example_strings)
prval () = lemma_list_vt_param example_strptrs
val n = length example_strptrs
val @(pf, pfgc | p) = array_ptr_alloc<Strptr1> (i2sz n)
macdef arr = !p
val () = array_initize_list_vt<Strptr1> (arr, n, example_strptrs)
val () = array_quicksort<Strptr1> (arr, i2sz n)
val sorted_strptrs = array2list (arr, i2sz n)
fun
print_strptrs {n : nat} .<n>.
(strptrs : !list_vt (Strptr1, n),
i : int) : void =
case+ strptrs of
| NIL => if i <> 1 then println! () else ()
| @ head :: tail =>
begin
print! head;
if i = 8 then
begin
println! ();
print_strptrs (tail, 1)
end
else
begin
print! " ";
print_strptrs (tail, succ i)
end;
fold@ strptrs
end
in
println! (length example_strings);
println! (length sorted_strptrs);
print_strptrs (sorted_strptrs, 1);
list_vt_freelin<Strptr1> sorted_strptrs;
array_ptr_free (pf, pfgc | p);
list_vt_free<string> example_strings
end
(*------------------------------------------------------------------*)</syntaxhighlight>
{{out}}
<pre>$ patscc -O3 -DATS_MEMALLOC_LIBC quicksort_task_for_arrays_2.dats
62
62
all all all and any array be be
be both choose divide element elements elements elements
except first first greater in in into join
less must must of other partition partition partition
partition partitions partitions pivot pivot pivot pivot pivot
recursion second second sort sorted sorted than than
the the the the the the the the
the the to to two use</pre>
=== A ''stable'' quicksort working on linear lists ===
See the code at [[Quickselect_algorithm#Quickselect_working_on_linear_lists|the quickselect task]].
{{out}}
<pre>$ patscc -O3 -DATS_MEMALLOC_LIBC quickselect_task_for_list_vt.dats && ./a.out quicksort
stable sort by first character:
duck, deer, dolphin, elephant, earwig, giraffe, pronghorn, wildebeest, woodlouse, whip-poor-will</pre>
=={{header|AutoHotkey}}==
Translated from the python example:
<
for k, v in QuickSort(a)
Out .= "," v
Line 1,277 ⟶ 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 1,303 ⟶ 2,414:
more := quicksort(more)
Return less . pivotList . more
}</
=={{header|AWK}}==
<
# the following qsort implementation extracted from:
#
Line 1,420 ⟶ 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 1,509 ⟶ 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 1,552 ⟶ 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.
_Define A-Z As _INTEGER64
Sub Quicksort_QB64 (QWORDS~&&())
Left = LBound(QWORDS~&&)
Right = UBound(QWORDS~&&)
LeftMargin = Left
ReDim Stack&&(Left To Right)
StackPtr = 0
StackPtr = StackPtr + 1
Stack&&(StackPtr + LeftMargin) = Left
StackPtr = StackPtr + 1
Stack&&(StackPtr + LeftMargin) = Right
Do 'Until StackPtr = 0
Right = Stack&&(StackPtr + LeftMargin)
StackPtr = StackPtr - 1
Left = Stack&&(StackPtr + LeftMargin)
StackPtr = StackPtr - 1
Do 'Until Left >= Right
Pivot~&& = QWORDS~&&((Left + Right) \ 2)
Indx = Left
Jndx = Right
Do
Do While (QWORDS~&&(Indx) < Pivot~&&)
Indx = Indx + 1
Loop
Do While (QWORDS~&&(Jndx) > Pivot~&&)
Jndx = Jndx - 1
Loop
If Indx <= Jndx Then
If Indx < Jndx Then Swap QWORDS~&&(Indx), QWORDS~&&(Jndx)
Indx = Indx + 1
Jndx = Jndx - 1
End If
Loop While Indx <= Jndx
If Indx < Right Then
StackPtr = StackPtr + 1
Stack&&(StackPtr + LeftMargin) = Indx
StackPtr = StackPtr + 1
Stack&&(StackPtr + LeftMargin) = Right
End If
Right = Jndx
Loop Until Left >= Right
Loop Until StackPtr = 0
End Sub</syntaxhighlight>
==={{header|QuickBASIC}}===
{{works with|FreeBASIC}}
{{works with|PowerBASIC for DOS}}
{{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 1,607 ⟶ 3,624:
}
newline()
}</
=={{header|Beads}}==
<
calc main_init
Line 1,646 ⟶ 3,663:
swap arr[i+1] <=> arr[highIndex]
return (i+1)
</syntaxhighlight>
{{out}}
Line 1,653 ⟶ 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 1,671 ⟶ 3,688:
)
& out$Q$(1900 optimized variants of 4001/2 Quicksort (quick,sort) are (quick,sober) features of 90 languages)
);</
{{out}}
<pre> 90
Line 1,686 ⟶ 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 1,733 ⟶ 3,765:
quicksort(A + i, len - i);
}
</syntaxhighlight>
{{out}}
Line 1,743 ⟶ 3,775:
Randomized sort with separated components.
<syntaxhighlight lang="c">
#include <stdlib.h> // REQ: rand()
Line 1,773 ⟶ 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 1,951 ⟶ 3,983:
}
#endregion
}</
'''Example''':
<
using System;
Line 1,963 ⟶ 3,995:
Console.WriteLine(String.Join(" ", entries));
}
}</
{{out}}
<pre>1 2 3 4 5 6 7 8 9</pre>
Line 1,969 ⟶ 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 1,991 ⟶ 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 2,064 ⟶ 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 2,088 ⟶ 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 2,099 ⟶ 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 2,198 ⟶ 4,270:
GOBACK
.</
=={{header|CoffeeScript}}==
<
quicksort = ([x, xs...]) ->
return [] unless x?
Line 2,207 ⟶ 4,279:
larger = (a for a in xs when a > x)
(quicksort smallerOrEqual).concat(x).concat(quicksort larger)
</syntaxhighlight>
=={{header|Common Lisp}}==
Line 2,213 ⟶ 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 2,244 ⟶ 4,316:
(sub-sort (1+ index) right)))))
(sub-sort 0 (1- (length sequence)))
sequence))</
Functional with destructuring
<
(defun quicksort (list)
(when list
Line 2,254 ⟶ 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 2,358 ⟶ 4,430:
i := i + 1;
end loop;
print_nl();</
{{out}}
Line 2,366 ⟶ 4,438:
=={{header|Crystal}}==
{{trans|Ruby}}
<
return a if a.size <= 1
p = a[0]
Line 2,374 ⟶ 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 2,384 ⟶ 4,456:
qsort (x:l) = qsort (filter (<x) l) ++ x : qsort (filter (>=x) l)
goal = qsort [2,3,1,0]</
=={{header|D}}==
A
<syntaxhighlight lang
import std.algorithm: filter;
import std.array;
xs.length == 0 ? [] :
xs[1 .. $].filter!(x => x< xs[0]).array.quickSort ~
xs[0 .. 1] ~
void main()
</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 2,419 ⟶ 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 2,426 ⟶ 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 2,440 ⟶ 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 2,481 ⟶ 4,727:
print("After sort");
arr.forEach((var i)=>print("$i"));
}</
=={{header|E}}==
<
def swap(container, ixA, ixB) {
Line 2,531 ⟶ 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 2,571 ⟶ 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 2,593 ⟶ 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 2,632 ⟶ 4,888:
Log( 'Sorted: %@', quicksort(b) )
return 0</
Alternative implementation (not necessarily as efficient, but very readable)
<
implementation Array (Quicksort)
Line 2,668 ⟶ 4,924:
Log( 'Sorted: %@', b.quicksort )
return 0</
{{out}}
Line 2,719 ⟶ 4,975:
=={{header|Eiffel}}==
The <syntaxhighlight lang
<
class
QUICKSORT [G -> COMPARABLE]
Line 2,815 ⟶ 5,071:
end
</syntaxhighlight>
A test application:
<
class
APPLICATION
Line 2,846 ⟶ 5,102:
end
</syntaxhighlight>
=={{header|Elena}}==
ELENA
<
import system'routines;
import system'collections;
Line 2,866 ⟶ 5,122:
auto more := new ArrayList();
self.forEach::(item)
{
if (item < pivot)
Line 2,898 ⟶ 5,154:
console.printLine("before:", list.asEnumerable());
console.printLine("after :", list.quickSort().asEnumerable());
}</
{{out}}
<pre>
Line 2,906 ⟶ 5,162:
=={{header|Elixir}}==
<
def qsort([]), do: []
def qsort([h | t]) do
Line 2,912 ⟶ 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 2,925 ⟶ 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 2,949 ⟶ 5,205:
after 5000 -> receive_results(Ref, L1, L2)
end.
</syntaxhighlight>
=={{header|Emacs Lisp}}==
'''Unoptimized'''
{{libheader|seq.el}}
<syntaxhighlight lang="lisp">(require 'seq)
(defun quicksort (xs)
(if (null xs)
=={{header|ERRE}}==
<syntaxhighlight lang="erre">
PROGRAM QUICKSORT_DEMO
Line 3,045 ⟶ 5,303:
END FOR
END PROGRAM
</syntaxhighlight>
=={{header|F Sharp|F#}}==
<
let rec qsort = function
hd :: tl ->
Line 3,054 ⟶ 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 3,082 ⟶ 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 3,105 ⟶ 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 3,317 ⟶ 5,479:
println( qsort([4, 2, 1, 3, 0, 2]) )
println( qsort(["Juan", "Daniel", "Miguel", "William", "Liam", "Ethan", "Jacob"]) )</
{{out}}
Line 3,341 ⟶ 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 3,433 ⟶ 5,595:
}
pex(0, len(a)-1)
}</
{{out}}
<pre>
Line 3,442 ⟶ 5,604:
More traditional version of quicksort. It work generically with any container that conforms to <code>sort.Interface</code>.
<
import (
Line 3,493 ⟶ 5,655:
quicksort(sort.StringSlice(b))
fmt.Printf("Sorted: %v\n", b)
}</
{{out}}
<pre>
Line 3,505 ⟶ 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]
(ys, zs) = partition (< x) xs</syntaxhighlight>
=={{header|Icon}} and {{header|Unicon}}==
<
demosort(quicksort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")
end
Line 3,562 ⟶ 5,723:
suspend lower # 1st return pivot point
suspend X # 2nd return modified X (in case immutable)
end</
Implementation notes:
Line 3,582 ⟶ 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 3,594 ⟶ 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 3,607 ⟶ 5,768:
=={{header|Io}}==
<
quickSort := method(
if(size > 1) then(
Line 3,624 ⟶ 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 3,697 ⟶ 5,858:
oops
end
</syntaxhighlight>
=={{header|J}}==
{{eff note|J|/:~}}
<
quicksort=: 3 : 0
Line 3,712 ⟶ 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 3,723 ⟶ 5,884:
{{trans|Python}}
<
if (arr.isEmpty())
return arr;
Line 3,753 ⟶ 5,914:
}
}
</syntaxhighlight>
=== Functional ===
{{works with|Java|1.8}}
<
if (col == null || col.isEmpty())
return Collections.emptyList();
Line 3,768 ⟶ 5,929:
.flatMap(Collection::stream).collect(Collectors.toList());
}
}</
=={{header|JavaScript}}==
Line 3,774 ⟶ 5,935:
===Imperative===
<
function swap(i, j) {
Line 3,812 ⟶ 5,973:
return array;
}</
Example:<
var sorted_array = sort(test_array, function(a,b) { return a<b; });</
{{Out}}<
===Functional===
====ES6====
Using '''destructuring''' and '''satisfying immutability''' we can propose a single expresion solution (from https://github.com/ddcovery/expressive_sort)
<syntaxhighlight lang="javascript">const qsort = ([pivot, ...others]) =>
pivot === void 0 ? [] : [
...qsort(others.filter(n => n < pivot)),
...qsort(others.filter(n => n >= pivot))
];
qsort( [ 11.8, 14.1, 21.3, 8.5, 16.7, 5.7 ] )</syntaxhighlight>
{{Out}}
<pre>[ 5.7, 8.5, 11.8, 14.1, 16.7, 21.3 ]
</pre>
====ES5====
Unlike what happens with ES6, there are no destructuring nor lambdas, but we can '''ensure immutability''' and propose a '''single expression''' solution with standard anonymous functions
<syntaxhighlight lang
function qsort( xs ){
return xs.length === 0 ? [] : [].concat(
qsort( xs.slice(1).filter(function(x){ return x< xs[0] })),
xs[0],
)
}
qsort( [ 11.8, 14.1, 21.3, 8.5, 16.7, 5.7 ] )
</syntaxhighlight>
{{Out}}
<pre>[5.7, 8.5, 11.8, 14.1, 16.7, 21.3]</pre>
=={{header|Joy}}==
<
DEFINE qsort ==
[small] # termination condition: 0 or 1 element
Line 3,927 ⟶ 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 3,947 ⟶ 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 3,975 ⟶ 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 3,991 ⟶ 6,087:
=={{header|K}}==
<
Example:
<syntaxhighlight lang="k">
quicksort 1 3 5 7 9 8 6 4 2
</syntaxhighlight>
{{out}}
Line 4,006 ⟶ 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 4,021 ⟶ 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 4,029 ⟶ 6,125:
And here is the full if/then/else clause:
<syntaxhighlight lang="k">
:[
0=#x; / if length of x is zero
Line 4,039 ⟶ 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 4,045 ⟶ 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 4,087 ⟶ 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 4,102 ⟶ 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 4,209 ⟶ 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 4,228 ⟶ 6,324:
sorted := [ 3, 9, 5, 4, 1, 3, 9, 5, 4, 1 ].quicksort(): _a < _b
print sorted</
=={{header|Logo}}==
<
to small? :list
Line 4,246 ⟶ 6,342:
end
show quicksort [1 3 5 7 9 8 6 4 2]</
<
to incr :name
Line 4,280 ⟶ 6,376:
make "test {1 3 5 7 9 8 6 4 2}
sort :test
show :test</
=={{header|Logtalk}}==
<
quicksort(List, [], Sorted).
Line 4,299 ⟶ 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 4,325 ⟶ 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 4,343 ⟶ 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 4,356 ⟶ 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 4,394 ⟶ 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 4,441 ⟶ 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 4,517 ⟶ 6,613:
}
Checkit3
</syntaxhighlight>
=={{header|M4}}==
<
define(`arg1', `$1')dnl
dnl
Line 4,547 ⟶ 6,643:
`sep(arg1$1,(shift$1),`()',`()')')')dnl
dnl
quicksort((3,1,4,1,5,9))</
{{out}}
Line 4,553 ⟶ 6,649:
(1,1,3,4,5,9)
</pre>
=={{header|Maclisp}}==
<syntaxhighlight lang="lisp">
;; While not strictly required, it simplifies the
;; implementation considerably to use filter. MACLisp
;; Doesn't have one out of the box, so we bring our own
(DEFUN FILTER (F LIST)
(COND
((EQ LIST NIL) NIL)
((FUNCALL F (CAR LIST))
(CONS (CAR LIST) (FILTER F (CDR LIST))))
(T
(FILTER F (CDR LIST)))))
;; And then, quicksort.
(DEFUN QUICKSORT (LIST)
(COND
((OR (EQ LIST ())
(EQ (CDR LIST) ()))
LIST)
(T
(LET
((PIVOT (CAR LIST))
(REST (CDR LIST)))
(APPEND
(QUICKSORT (FILTER #'(LAMBDA (X) (<= X PIVOT)) REST))
(LIST PIVOT)
(QUICKSORT (FILTER #'(LAMBDA (X) (> X PIVOT)) REST)))))))
</syntaxhighlight>
=={{header|Maple}}==
<
local temp := arr[a]:
arr[a] := arr[b]:
Line 4,583 ⟶ 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}}==
<syntaxhighlight lang="mathematica">QuickSort[x_List] := Module[{pivot},
If[Length@x <= 1, Return[x]];
pivot = RandomChoice@x;
Flatten@{QuickSort[Cases[x, j_ /; j < pivot]], Cases[x, j_ /; j == pivot], QuickSort[Cases[x, j_ /; j > pivot]]}
]</
<syntaxhighlight lang="mathematica">qsort[{}] = {};
qsort[{x_, xs___}] := Join[qsort@Select[{xs}, # <= x &], {x}, qsort@Select[{xs}, # > x &]];</syntaxhighlight>
<syntaxhighlight lang="mathematica">QuickSort[{}] := {}
QuickSort[list: {__}] := With[{pivot=RandomChoice[list]},
Join[ <|1->{}, -1->{}|>, GroupBy[list,Order[#,pivot]&] ] // Catenate[ {QuickSort@#[1], #[0], QuickSort@#[-1]} ]&
]</
=={{header|MATLAB}}==
Line 4,608 ⟶ 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 4,628 ⟶ 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 4,643 ⟶ 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 4,680 ⟶ 6,802:
)
a = #(4, 89, -3, 42, 5, 0, 2, 889)
a = quickSort a</
=={{header|Mercury}}==
=== A quicksort that works on linked lists ===
{{works with|Mercury|22.01.1}}
<syntaxhighlight lang="mercury">%%%-------------------------------------------------------------------
:- module quicksort_task_for_lists.
:- interface.
:- import_module io.
:- pred main(io, io).
:- mode main(di, uo) is det.
:- implementation.
:- import_module int.
:- import_module list.
%%%-------------------------------------------------------------------
%%%
%%% Partitioning a list into three:
%%%
%%% Left elements less than the pivot
%%% Middle elements equal to the pivot
%%% Right elements greater than the pivot
%%%
%%% The implementation is tail-recursive.
%%%
:- pred partition(comparison_func(T), T, list(T),
list(T), list(T), list(T)).
:- mode partition(in, in, in, out, out, out) is det.
partition(Compare, Pivot, Lst, Left, Middle, Right) :-
partition(Compare, Pivot, Lst, [], Left, [], Middle, [], Right).
:- pred partition(comparison_func(T), T, list(T),
list(T), list(T),
list(T), list(T),
list(T), list(T)).
:- mode partition(in, in, in,
in, out,
in, out,
in, out) is det.
partition(_, _, [], Left0, Left, Middle0, Middle, Right0, Right) :-
Left = Left0,
Middle = Middle0,
Right = Right0.
partition(Compare, Pivot, [Head | Tail], Left0, Left,
Middle0, Middle, Right0, Right) :-
Compare(Head, Pivot) = Cmp,
(if (Cmp = (<))
then partition(Compare, Pivot, Tail,
[Head | Left0], Left,
Middle0, Middle,
Right0, Right)
else if (Cmp = (=))
then partition(Compare, Pivot, Tail,
Left0, Left,
[Head | Middle0], Middle,
Right0, Right)
else partition(Compare, Pivot, Tail,
Left0, Left,
Middle0, Middle,
[Head | Right0], Right)).
%%%-------------------------------------------------------------------
%%%
%%% Quicksort using the first element as pivot.
%%%
%%% This is not the world's best choice of pivot, but it is the
%%% easiest one to get from a linked list.
%%%
%%% This implementation is *not* tail-recursive--as most quicksort
%%% implementations also are not. (However, do an online search on
%%% "quicksort fortran 77" and you will find some "tail-recursive"
%%% implementations, with the tail recursions expressed as gotos.)
%%%
:- func quicksort(comparison_func(T), list(T)) = list(T).
quicksort(_, []) = [].
quicksort(Compare, [Pivot | Tail]) = Sorted_Lst :-
partition(Compare, Pivot, Tail, Left, Middle, Right),
quicksort(Compare, Left) = Sorted_Left,
quicksort(Compare, Right) = Sorted_Right,
Sorted_Left ++ [Pivot | Middle] ++ Sorted_Right = Sorted_Lst.
%%%-------------------------------------------------------------------
:- func example_numbers = list(int).
example_numbers = [1, 3, 9, 5, 8, 6, 5, 1, 7, 9, 8, 6, 4, 2].
:- func int_compare(int, int) = comparison_result.
int_compare(I, J) = Cmp :-
if (I < J) then (Cmp = (<))
else if (I = J) then (Cmp = (=))
else (Cmp = (>)).
main(!IO) :-
quicksort(int_compare, example_numbers) = Sorted_Numbers,
print("unsorted: ", !IO),
print_line(example_numbers, !IO),
print("sorted: ", !IO),
print_line(Sorted_Numbers, !IO).
%%%-------------------------------------------------------------------
%%% local variables:
%%% mode: mercury
%%% prolog-indent-width: 2
%%% end:</syntaxhighlight>
{{out}}
<pre>$ mmc quicksort_task_for_lists.m && ./quicksort_task_for_lists
unsorted: [1, 3, 9, 5, 8, 6, 5, 1, 7, 9, 8, 6, 4, 2]
sorted: [1, 1, 2, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9]</pre>
=== A quicksort that works on arrays ===
{{works with|Mercury|22.01.1}}
The in-place partitioning algorithm here is similar to but not quite the same as that of the task pseudocode. I wrote it by referring to some Fortran code I wrote several months ago for a quickselect. (That quickselect had a random pivot, however.)
<syntaxhighlight lang="mercury">%%%-------------------------------------------------------------------
:- module quicksort_task_for_arrays.
:- interface.
:- import_module io.
:- pred main(io, io).
:- mode main(di, uo) is det.
:- implementation.
:- import_module array.
:- import_module int.
:- import_module list.
%%%-------------------------------------------------------------------
%%%
%%% Partitioning a subarray into two halves: one with elements less
%%% than or equal to a pivot, the other with elements greater than or
%%% equal to a pivot.
%%%
%%% The implementation is tail-recursive.
%%%
:- pred partition(pred(T, T), T, int, int, array(T), array(T), int).
:- mode partition(pred(in, in) is semidet, in, in, in,
array_di, array_uo, out).
partition(Less_than, Pivot, I_first, I_last, Arr0, Arr, I_pivot) :-
I = I_first - 1,
J = I_last + 1,
partition_loop(Less_than, Pivot, I, J, Arr0, Arr, I_pivot).
:- pred partition_loop(pred(T, T), T, int, int,
array(T), array(T), int).
:- mode partition_loop(pred(in, in) is semidet, in, in, in,
array_di, array_uo, out).
partition_loop(Less_than, Pivot, I, J, Arr0, Arr, Pivot_index) :-
if (I = J) then (Arr = Arr0,
Pivot_index = I)
else (I1 = I + 1,
I2 = search_right(Less_than, Pivot, I1, J, Arr0),
(if (I2 = J) then (Arr = Arr0,
Pivot_index = J)
else (J1 = J - 1,
J2 = search_left(Less_than, Pivot, I2, J1, Arr0),
swap(I2, J2, Arr0, Arr1),
partition_loop(Less_than, Pivot, I2, J2, Arr1, Arr,
Pivot_index)))).
:- func search_right(pred(T, T), T, int, int, array(T)) = int.
:- mode search_right(pred(in, in) is semidet,
in, in, in, in) = out is det.
search_right(Less_than, Pivot, I, J, Arr0) = K :-
if (I = J) then (I = K)
else if Less_than(Pivot, Arr0^elem(I)) then (I = K)
else (search_right(Less_than, Pivot, I + 1, J, Arr0) = K).
:- func search_left(pred(T, T), T, int, int, array(T)) = int.
:- mode search_left(pred(in, in) is semidet,
in, in, in, in) = out is det.
search_left(Less_than, Pivot, I, J, Arr0) = K :-
if (I = J) then (J = K)
else if Less_than(Arr0^elem(J), Pivot) then (J = K)
else (search_left(Less_than, Pivot, I, J - 1, Arr0) = K).
%%%-------------------------------------------------------------------
%%%
%%% Quicksort with median of three as pivot.
%%%
%%% Like most quicksort implementations, this one is *not*
%%% tail-recursive.
%%%
%% quicksort/3 sorts an entire array.
:- pred quicksort(pred(T, T), array(T), array(T)).
:- mode quicksort(pred(in, in) is semidet, array_di, array_uo) is det.
quicksort(Less_than, Arr0, Arr) :-
bounds(Arr0, I_first, I_last),
quicksort(Less_than, I_first, I_last, Arr0, Arr).
%% quicksort/5 sorts a subarray.
:- pred quicksort(pred(T, T), int, int, array(T), array(T)).
:- mode quicksort(pred(in, in) is semidet, in, in,
array_di, array_uo) is det.
quicksort(Less_than, I_first, I_last, Arr0, Arr) :-
if (I_last - I_first >= 2)
then (median_of_three(Less_than, I_first, I_last,
Arr0, Arr1, Pivot),
%% Partition only from I_first to I_last - 1.
partition(Less_than, Pivot, I_first, I_last - 1,
Arr1, Arr2, K),
%% Now everything that is less than the pivot is to the
%% left of K.
%% Put the pivot at K, moving the element that had been there
%% to the end. If K = I_last, then this element is actually
%% garbage and will be overwritten with the pivot, which turns
%% out to be the greatest element. Otherwise, the moved
%% element is not less than the pivot and so the partitioning
%% is preserved.
Arr2^elem(K) = Elem_to_move,
(Arr2^elem(I_last) := Elem_to_move) = Arr3,
(Arr3^elem(K) := Pivot) = Arr4,
%% Sort the subarray on either side of the pivot.
quicksort(Less_than, I_first, K - 1, Arr4, Arr5),
quicksort(Less_than, K + 1, I_last, Arr5, Arr))
else if (I_last - I_first = 1) % Two elements.
then (Elem_first = Arr0^elem(I_first),
Elem_last = Arr0^elem(I_last),
(if Less_than(Elem_first, Elem_last)
then (Arr = Arr0)
else ((Arr0^elem(I_first) := Elem_last) = Arr1,
(Arr1^elem(I_last) := Elem_first) = Arr)))
else (Arr = Arr0). % Zero or one element.
%% median_of_three/6 both chooses a pivot and rearranges the array
%% elements so one may partition them from I_first to I_last - 1,
%% leaving the pivot element out of the array.
:- pred median_of_three(pred(T, T), int, int, array(T), array(T), T).
:- mode median_of_three(pred(in, in) is semidet, in, in,
array_di, array_uo, out) is det.
median_of_three(Less_than, I_first, I_last, Arr0, Arr, Pivot) :-
I_middle = I_first + ((I_last - I_first) // 2),
Elem_first = Arr0^elem(I_first),
Elem_middle = Arr0^elem(I_middle),
Elem_last = Arr0^elem(I_last),
(if pred_xor(Less_than, Less_than,
Elem_middle, Elem_first,
Elem_last, Elem_first)
then (Pivot = Elem_first,
(if Less_than(Elem_middle, Elem_last)
then (Arr1 = (Arr0^elem(I_first) := Elem_middle),
Arr = (Arr1^elem(I_middle) := Elem_last))
else (Arr = (Arr0^elem(I_first) := Elem_last))))
else if pred_xor(Less_than, Less_than,
Elem_middle, Elem_first,
Elem_middle, Elem_last)
then (Pivot = Elem_middle,
(if Less_than(Elem_first, Elem_last)
then (Arr = (Arr0^elem(I_middle) := Elem_last))
else (Arr1 = (Arr0^elem(I_first) := Elem_last),
Arr = (Arr1^elem(I_middle) := Elem_first))))
else (Pivot = Elem_last,
(if Less_than(Elem_first, Elem_middle)
then (Arr = Arr0)
else (Arr1 = (Arr0^elem(I_first) := Elem_middle),
Arr = (Arr1^elem(I_middle) := Elem_first))))).
:- pred pred_xor(pred(T, T), pred(T, T), T, T, T, T).
:- mode pred_xor(pred(in, in) is semidet,
pred(in, in) is semidet,
in, in, in, in) is semidet.
pred_xor(P, Q, W, X, Y, Z) :-
if P(W, X) then (not Q(Y, Z)) else Q(Y, Z).
%%%-------------------------------------------------------------------
:- func example_numbers = list(int).
example_numbers = [1, 3, 9, 5, 8, 6, 5, 0, 1, 7, 9, 8, 6, 4, 2, -28,
30, 31, 1, 3, 9, 5, 8, 6, 5, 1, 6, 4, 2, -28, 30,
-50, 500, -1234, 1234, 12].
main(!IO) :-
(array.from_list(example_numbers, Arr0)),
print_line("", !IO),
print_line(Arr0, !IO),
print_line("", !IO),
print_line(" |", !IO),
print_line(" V", !IO),
print_line("", !IO),
quicksort(<, Arr0, Arr1),
print_line(Arr1, !IO),
print_line("", !IO).
%%%-------------------------------------------------------------------
%%% local variables:
%%% mode: mercury
%%% prolog-indent-width: 2
%%% end:</syntaxhighlight>
{{out}}
<pre>$ mmc quicksort_task_for_arrays.m && ./quicksort_task_for_arrays
array([1, 3, 9, 5, 8, 6, 5, 0, 1, 7, 9, 8, 6, 4, 2, -28, 30, 31, 1, 3, 9, 5, 8, 6, 5, 1, 6, 4, 2, -28, 30, -50, 500, -1234, 1234, 12])
|
V
array([-1234, -50, -28, -28, 0, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 8, 8, 8, 9, 9, 9, 12, 30, 30, 31, 500, 1234])
</pre>
=={{header|MiniScript}}==
Quick implementation for Miniscript, simply goes through the list reference and swaps the positions
<syntaxhighlight lang="miniscript">Partition = function(a, low, high)
pivot = a[low]
leftwall = low
for i in range(low + 1, high)
if a[i] < pivot then
leftwall = leftwall + 1
temp = a[leftwall]
a[leftwall] = a[i]
a[i] = temp
end if
end for
temp = a[leftwall]
a[leftwall] = pivot
a[low] = temp
return leftwall
end function
QuickSort = function(a, low=null, high=null)
if not low then low = 0
if not high then high = a.len - 1
if low < high then
pivot_location = Partition(a, low, high)
QuickSort a, low, pivot_location - 1
QuickSort a, pivot_location + 1, high
end if
return a
end function
print QuickSort([3, 5, 2, 4, 1])
</syntaxhighlight>
{{out}}
<pre>[1, 2, 3, 4, 5]</pre>
=={{header|Miranda}}==
<syntaxhighlight lang="miranda">main :: [sys_message]
main = [Stdout ("Before: " ++ show testlist ++ "\n"),
Stdout ("After: " ++ show (quicksort testlist) ++ "\n")]
where testlist = [4,65,2,-31,0,99,2,83,782,1]
quicksort [] = []
quicksort [x] = [x]
quicksort xs = (quicksort less) ++ equal ++ (quicksort more)
where pivot = hd xs
less = [x | x<-xs; x<pivot]
equal = [x | x<-xs; x=pivot]
more = [x | x<-xs; x>pivot]</syntaxhighlight>
{{out}}
<pre>Before: [4,65,2,-31,0,99,2,83,782,1]
After: [-31,0,1,2,2,4,65,83,99,782]</pre>
=={{header|Modula-2}}==
Line 4,692 ⟶ 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 4,703 ⟶ 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 4,709 ⟶ 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 4,836 ⟶ 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 4,933 ⟶ 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 4,953 ⟶ 7,449:
IO.Put(arr[i] & "\n");
END;
END Main.</
=={{header|Mond}}==
Line 4,959 ⟶ 7,455:
Implements the simple quicksort algorithm.
<
{
if( arr.length() < 2 )
Line 4,990 ⟶ 7,486:
return a;
}</
;Usage
<
var sorted = quicksort( array );
printLn( sorted );</
{{out}}
Line 5,014 ⟶ 7,510:
Shows quicksort on a 16-element array.
<syntaxhighlight lang="mumps">
main
new collection,size
Line 5,050 ⟶ 7,546:
. . set:array(i)>array(j) sorted=0
quit sorted
</syntaxhighlight>
;Usage
<syntaxhighlight lang
{{out}}
Line 5,102 ⟶ 7,598:
=={{header|Nanoquery}}==
{{trans|Python}}
<
less = {}
pivotList = {}
Line 5,125 ⟶ 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 5,152 ⟶ 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 5,256 ⟶ 7,752:
return ixStore
</syntaxhighlight>
{{out}}
<pre>
Line 5,289 ⟶ 7,785:
=={{header|Nial}}==
<
pass,
link [
Line 5,296 ⟶ 7,792:
quicksort sublist [ > [pass,first], pass ]
]
]</
Using it.
<
=3 4 5 7 8</
=={{header|Nim}}==
==={{header|Procedural (in place) algorithm }} ===
<syntaxhighlight lang="nim">proc quickSortImpl[T](a: var openarray[T], start, stop: int) =
if stop - start > 0:
let pivot = a[start]
Line 5,325 ⟶ 7,823:
var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]
a.quickSort()
echo a</
==={{header|Functional (inmmutability) algorithm }} ===
<syntaxhighlight lang="nim">import sequtils,sugar
func sorted[T](xs:seq[T]): seq[T] =
if xs.len==0: @[] else: concat(
xs[1..^1].filter(x=>x<xs[0]).sorted,
@[xs[0]],
xs[1..^1].filter(x=>x>=xs[0]).sorted
)
@[4, 65, 2, -31, 0, 99, 2, 83, 782].sorted.echo</syntaxhighlight>
{{out}}
<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>
=={{header|Nix}}==
<
let
qs = l:
Line 5,343 ⟶ 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 5,396 ⟶ 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 5,433 ⟶ 8,003:
}
return 0;
}</
{{out}}
<pre>Unsorted: (
Line 5,484 ⟶ 8,054:
===Declarative and purely functional===
<
| [] -> []
| x::xs ->
Line 5,491 ⟶ 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 5,499 ⟶ 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 5,530 ⟶ 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 5,546 ⟶ 8,116:
N=30; v=rand(N,1); tic,u=quicksort(v); toc
u</
=={{header|Oforth}}==
Line 5,552 ⟶ 8,122:
Oforth built-in sort uses quick sort algorithm (see lang/collect/ListBuffer.of for implementation) :
<
=={{header|Ol}}==
<syntaxhighlight lang="scheme">
(define (quicksort l ??)
(if (null? l)
'()
(append (quicksort (filter (lambda (x) (?? (car l) x)) (cdr l)) ??)
(list (car l))
(quicksort (filter (lambda (x) (not (?? (car l) x))) (cdr l)) ??))))
(print
(quicksort (list 1 3 5 9 8 6 4 3 2) >))
(print
(quicksort (iota 100) >))
(print
(quicksort (iota 100) <))
</syntaxhighlight>
{{Out}}
<pre>
(1 2 3 3 4 5 6 8 9)
(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99)
(99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0)
</pre>
=={{header|ooRexx}}==
{{trans|Python}}
<
say 'before:' a~toString( ,', ')
a = quickSort(a)
Line 5,582 ⟶ 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 5,588 ⟶ 8,181:
=={{header|Oz}}==
<
fun {QuickSort Xs}
case Xs of nil then nil
Line 5,600 ⟶ 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 5,617 ⟶ 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 5,657 ⟶ 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 5,689 ⟶ 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 5,696 ⟶ 8,316:
=={{header|PHP}}==
<
$lte = $gt = array();
if(count($arr) < 2){
Line 5,715 ⟶ 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 5,737 ⟶ 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===
<syntaxhighlight lang="picat">qsort([]) = [].
qsort([H|T]) = qsort([E : E in T, E =< H])
++ [H] ++
qsort([E : E in T, E > H]).</syntaxhighlight>
===Recursion===
{{trans|Prolog}}
<syntaxhighlight lang="picat">qsort( [], [] ).
qsort( [H|U], S ) :-
splitBy(H, U, L, R),
qsort(L, SL),
qsort(R, SR),
append(SL, [H|SR], S).
% splitBy( H, U, LS, RS )
% True if LS = { L in U | L <= H }; RS = { R in U | R > H }
splitBy( _, [], [], []).
splitBy( H, [U|T], [U|LS], RS ) :- U =< H, splitBy(H, T, LS, RS).
splitBy( H, [U|T], LS, [U|RS] ) :- U > H, splitBy(H, T, LS, RS).</syntaxhighlight>
=={{header|PicoLisp}}==
<
(if (cdr L)
(let Pivot (car L)
Line 5,747 ⟶ 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 5,798 ⟶ 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 5,854 ⟶ 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 5,874 ⟶ 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 5,895 ⟶ 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 5,906 ⟶ 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 = []
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 =
</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 5,994 ⟶ 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 6,011 ⟶ 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 6,021 ⟶ 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 6,041 ⟶ 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 6,056 ⟶ 8,674:
(quicksort [6 8 5 9 3 2 2 1 4 7])
</syntaxhighlight>
=={{header|Quackery}}==
Line 6,062 ⟶ 8,680:
Sort a nest of numbers.
<
[ stack ] is same ( --> s )
Line 6,087 ⟶ 8,705:
[] 10 times [ i^ join ] 3 of
dup echo cr
quicksort echo cr</
'''Output:'''
Line 6,096 ⟶ 8,714:
=={{header|R}}==
{{trans|Octave}}
<
if ( length(v) > 1 )
{
Line 6,107 ⟶ 8,725:
vs <- runif(N)
system.time(u <- qsort(vs))
print(u)</
=={{header|Racket}}==
<
(define (quicksort < l)
(match l
Line 6,118 ⟶ 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 6,177 ⟶ 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}}==
===version 1===
This REXX version doesn't use or modify the program stack.
It is over '''400%''' times faster then the 2<sup>nd</sup> REXX version (using the exact same random numbers).
<syntaxhighlight lang="rexx">/*REXX program sorts a stemmed array using the quicksort algorithm. */
call gen@ /*generate the elements for the array. */
call show@ 'before sort' /*show the before array elements. */
Line 6,188 ⟶ 8,938:
call show@ ' after sort' /*show the after array elements. */
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
inOrder: parse arg n; do j=1 for n-1; k= j+1; if @.j>@.k then return 0; end; return 1
/*──────────────────────────────────────────────────────────────────────────────────────*/
qSort: procedure expose @.; a.1=1; parse arg b.1; $= 1 /*access @.; get @. size; pivot.*/
if inOrder(b.1) then return /*Array already in order? Return*/
do while $\==0; L= a.$; t= b.$; $= $ - 1; if t<2 then iterate
H= L + t - 1; ?= L + t % 2
Line 6,285 ⟶ 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 6,421 ⟶ 9,174:
{{trans|Python}}The Python code translates very well to [[ooRexx]] but here is a way to implement it in classic REXX as well.
This REXX version doesn't handle numbers with leading/trailing/embedded blanks, or textual values that have blanks (or whitespace) in them.
<syntaxhighlight lang="rexx">
/*REXX*/
a = '4 65 2 -31 0 99 83 782 1'
do i = 1 to words(a)
queue word(a, i)
Line 6,506 ⟶ 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 6,556 ⟶ 9,339:
svect = left(svect, len(svect) - 1)
see svect + nl
</syntaxhighlight>
Output:
<pre>
Line 6,564 ⟶ 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 6,573 ⟶ 9,375:
less.quick_sort + [pivot] + greatereq.quick_sort
end
end</
or
<
def quick_sort
return self if length <= 1
Line 6,583 ⟶ 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 6,692 ⟶ 9,447:
v.swap(store_index, len - 1);
store_index
}</
{{out}}
Line 6,708 ⟶ 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 6,732 ⟶ 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 6,738 ⟶ 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 6,769 ⟶ 9,524:
a := res;
end;
end;</
<
main is
a:ARRAY{INT} := |10, 9, 8, 7, 6, -10, 5, 4, 656, -11|;
Line 6,778 ⟶ 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 6,787 ⟶ 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 6,828 ⟶ 9,583:
the function. Let's see it below, and then remark upon it:
<
(xs: C[T])
(implicit ord: scala.math.Ordering[T],
Line 6,844 ⟶ 9,599:
b.result()
}
}</
The type of our collection is "C[T]", and,
Line 6,864 ⟶ 9,619:
=== List quicksort ===
<syntaxhighlight lang="scheme">(define (split-by l p k)
(let loop ((low '())
(high '())
Line 6,885 ⟶ 9,643:
(quicksort high gt?))))))
(quicksort '(1 3 5 7 9 8 6 4 2) >)</
With srfi-1:
<
(if (null? l)
'()
Line 6,896 ⟶ 9,654:
(quicksort '(1 3 5 7 9 8 6 4 2) >)
</syntaxhighlight>
=== Vector quicksort (in place) ===
{{works with|Chibi Scheme}}
{{works with|Gauche Scheme}}
{{works with|CHICKEN Scheme|5.3.0}}
For CHICKEN:{{libheader|r7rs}}
<syntaxhighlight lang="scheme">;;;-------------------------------------------------------------------
;;;
;;; Quicksort in R7RS Scheme, working in-place on vectors (that is,
;;; arrays). I closely follow the "better quicksort algorithm"
;;; pseudocode, and thus the code is more "procedural" than
;;; "functional".
;;;
;;; I use a random pivot. If you can generate a random number quickly,
;;; this is a good method, but for this demonstration I have taken a
;;; fast linear congruential generator and made it brutally slow. It's
;;; just a demonstration. :)
;;;
(import (scheme base))
(import (scheme case-lambda))
(import (scheme write))
;;;-------------------------------------------------------------------
;;;
;;; Add "while" loops to the language.
;;;
(define-syntax while
(syntax-rules ()
((_ pred? body ...)
(let loop ()
(when pred?
(begin body ...)
(loop))))))
;;;-------------------------------------------------------------------
;;;
;;; In-place quicksort.
;;;
(define vector-quicksort!
(case-lambda
;; Use a default pivot selector.
((<? vec)
;; Random pivot.
(vector-quicksort! (lambda (vec i-first i-last)
(vector-ref vec (randint i-first i-last)))
<? vec))
;; Specify a pivot selector.
((pivot-select <? vec)
;;
;; The recursion:
;;
(let quicksort! ((i-first 0)
(i-last (- (vector-length vec) 1)))
(let ((n (- i-last i-first -1)))
(when (> n 1)
(let* ((pivot (pivot-select vec i-first i-last)))
(let ((left i-first)
(right i-last))
(while (<= left right)
(while (< (vector-ref vec left) pivot)
(set! left (+ left 1)))
(while (> (vector-ref vec right) pivot)
(set! right (- right 1)))
(when (<= left right)
(let ((lft (vector-ref vec left))
(rgt (vector-ref vec right)))
(vector-set! vec left rgt)
(vector-set! vec right lft)
(set! left (+ left 1))
(set! right (- right 1)))))
(quicksort! i-first right)
(quicksort! left i-last)))))))))
;;;-------------------------------------------------------------------
;;;
;;; A simple linear congruential generator, attributed by
;;; https://en.wikipedia.org/w/index.php?title=Linear_congruential_generator&oldid=1083800601
;;; to glibc and GCC. No attempt has been made to optimize this code.
;;;
(define seed 1)
(define two**31 (expt 2 31))
(define (random-integer)
(let* ((s0 seed)
(s1 (truncate-remainder (+ (* 1103515245 s0) 12345)
two**31)))
(set! seed s1)
s0))
(define randint
(case-lambda
((n) (truncate-remainder (random-integer) n))
((i-first i-last) (+ i-first (randint (- i-last i-first -1))))))
;;;-------------------------------------------------------------------
;;;
;;; A demonstration of in-place vector quicksort.
;;;
(define vec1 (vector-copy #(60 53 100 72 19 67 14
31 4 1 5 9 2 6 5 3 5 8
28 9 95 22 67 55 20 41
42 29 20 74 39)))
(vector-quicksort! < vec1)
(write vec1)
(newline)
;;;-------------------------------------------------------------------</syntaxhighlight>
{{out}}
<pre>$ gosh vector-quicksort.scm
#(1 2 3 4 5 5 5 6 8 9 9 14 19 20 20 22 28 29 31 39 41 42 53 55 60 67 67 72 74 95 100)</pre>
=={{header|Seed7}}==
<
local
var elemType: compare_elem is elemType.value;
Line 6,933 ⟶ 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 6,959 ⟶ 9,836:
proc swap(rw x, rw y);
[y,x] := [x,y];
end proc;</
Copying sort using comprehensions:
<
print(qsort(a));
Line 6,974 ⟶ 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 7,014 ⟶ 9,891:
END QUICKSORT;
</syntaxhighlight>
=={{header|Standard ML}}==
<
| quicksort (x::xs) =
let
Line 7,024 ⟶ 9,901:
quicksort left @ [x] @ quicksort right
end
</syntaxhighlight>
------------------------------------------------------------
Line 7,030 ⟶ 9,907:
Without using List.partition
<
fun par_helper([], x, l, r) = (l, r)
| par_helper(h::t, x, l, r) =
Line 7,046 ⟶ 9,923:
in
quicksort left @ [h] @ quicksort right
end;</
=={{header|Swift}}==
<
if (range.endIndex - range.startIndex > 1) {
let pivotIndex = partition(&elements, range)
Line 7,059 ⟶ 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 7,136 ⟶ 10,013:
return
</syntaxhighlight>
=={{header|Tailspin}}==
Simple recursive quicksort:
<
templates quicksort
@: [];
Line 7,157 ⟶ 10,034:
[4,5,3,8,1,2,6,7,9,8,5] -> quicksort -> !OUT::write
</syntaxhighlight>
In place:
<
templates quicksort
templates partial
Line 7,166 ⟶ 10,043:
def last: $(2);
def pivot: $@quicksort($first);
$(2) -> #
when
def limit: $
@quicksort($first): $@quicksort($limit);
@quicksort($limit): $pivot;
Line 7,175 ⟶ 10,053:
[ $limit + 1, $last ] !
when <?($@quicksort($
when <?($@quicksort($
otherwise
def temp: $@quicksort($
@quicksort($
@quicksort($
end partial
@: $;
Line 7,196 ⟶ 10,074:
[4,5,3,8,1,2,6,7,9,8,5] -> quicksort -> !OUT::write
</syntaxhighlight>
=={{header|Tcl}}==
<
proc quicksort {m} {
Line 7,213 ⟶ 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 7,281 ⟶ 10,159:
}
}
</syntaxhighlight>
=={{header|UnixPipes}}==
{{works with|Zsh}}
<
(while read n ; do
test $1 -gt $n && echo $n > $2 || echo $n > $3
Line 7,374 ⟶ 10,179:
}
cat to.sort | qsort</
=={{header|Ursala}}==
Line 7,386 ⟶ 10,191:
natural numbers.
<
quicksort "p" = ~&itB^?a\~&a ^|WrlT/~& "p"*|^\~& "p"?hthPX/~&th ~&h
Line 7,392 ⟶ 10,197:
#cast %nL
example = quicksort(nleq) <694,1377,367,506,3712,381,1704,1580,475,1872></
{{out}}
<pre>
Line 7,400 ⟶ 10,205:
=={{header|V}}==
<
[joinparts [p [*l1] [*l2] : [*l1 p *l2]] view].
[split_on_first uncons [>] split].
Line 7,406 ⟶ 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 7,544 ⟶ 10,240:
}
fn quick_sort(
if low < high {
pi := partition(mut arr, low, high)
Line 7,558 ⟶ 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 7,564 ⟶ 10,260:
=={{header|Wart}}==
<
(+ (qsort+keep (fn(_) (_ < pivot)) ns)
list.pivot
Line 7,570 ⟶ 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 7,601 ⟶ 10,297:
=={{header|XPL0}}==
<
string 0; \use zero-terminated strings
Line 7,634 ⟶ 10,330:
QSort(Str, StrLen(Str), 1);
Text(0, Str); CrLf(0);
]</
{{out}}
<pre>
.Pabcdeefghiiijklmnoooqrstuuvwxyz
</pre>
=={{header|Z80 Assembly}}==
sjasmplus syntax
<syntaxhighlight lang="z80">;--------------------------------------------------------------------------------------------------------------------
; Quicksort, inputs (__sdcccall(1) calling convention):
; HL = uint16_t* A (pointer to beginning of array)
; DE = uint16_t len (number of word elements in array)
; modifies: AF, A'F', BC, DE, HL
; WARNING: array can't be aligned to start/end of 64ki address space, like HL == 0x0000, or having last value at 0xFFFE
; WARNING: stack space required is on average about 6*log(len) (depending on the data, in extreme case it may be more)
quicksort_a:
; convert arguments to HL=A.begin(), DE=A.end() and continue with quicksort_a_impl
ex de,hl
add hl,hl
add hl,de
ex de,hl
; |
; fallthrough into implementation
; |
; v
;--------------------------------------------------------------------------------------------------------------------
; Quicksort implementation, inputs:
; HL = uint16_t* A.begin() (pointer to beginning of array)
; DE = uint16_t* A.end() (pointer beyond array)
; modifies: AF, A'F', BC, HL (DE is preserved)
quicksort_a_impl:
; array must be located within 0x0002..0xFFFD
ld c,l
ld b,h ; BC = A.begin()
; if (len < 2) return; -> if (end <= begin+2) return;
inc hl
inc hl
or a
sbc hl,de ; HL = -(2*len-2), len = (2-HL)/2
ret nc ; case: begin+2 >= end <=> (len < 2)
push de ; preserve A.end() for recursion
push bc ; preserve A.begin() for recursion
; uint16_t pivot = A[len / 2];
rr h
rr l
dec hl
res 0,l
add hl,de
ld a,(hl)
inc hl
ld l,(hl)
ld h,b
ld b,l
ld l,c
ld c,a ; HL = A.begin(), DE = A.end(), BC = pivot
; flip HL/DE meaning, it makes simpler the recursive tail and (A[j] > pivot) test
ex de,hl ; DE = A.begin(), HL = A.end(), BC = pivot
dec de ; but keep "from" address (related to A[i]) at -1 as "default" state
; for (i = 0, j = len - 1; ; i++, j--) { ; DE = (A+i-1).hi, HL = A+j+1
.find_next_swap:
; while (A[j] > pivot) j--;
.find_j:
dec hl
ld a,b
sub (hl)
dec hl ; HL = A+j (finally)
jr c,.find_j ; if cf=1, A[j].hi > pivot.hi
jr nz,.j_found ; if zf=0, A[j].hi < pivot.hi
ld a,c ; if (A[j].hi == pivot.hi) then A[j].lo vs pivot.lo is checked
sub (hl)
jr c,.find_j
.j_found:
; while (A[i] < pivot) i++;
.find_i:
inc de
ld a,(de)
inc de ; DE = (A+i).hi (ahead +0.5 for swap)
sub c
ld a,(de)
sbc a,b
jr c,.find_i ; cf=1 -> A[i] < pivot
; if (i >= j) break; // DE = (A+i).hi, HL = A+j, BC=pivot
sbc hl,de ; cf=0 since `jr c,.find_i`
jr c,.swaps_done
add hl,de ; DE = (A+i).hi, HL = A+j
; swap(A[i], A[j]);
inc hl
ld a,(de)
ldd
ex af,af
ld a,(de)
ldi
ex af,af
ld (hl),a ; Swap(A[i].hi, A[j].hi) done
dec hl
ex af,af
ld (hl),a ; Swap(A[i].lo, A[j].lo) done
inc bc
inc bc ; pivot value restored (was -=2 by ldd+ldi)
; --j; HL = A+j is A+j+1 for next loop (ready)
; ++i; DE = (A+i).hi is (A+i-1).hi for next loop (ready)
jp .find_next_swap
.swaps_done:
; i >= j, all elements were already swapped WRT pivot, call recursively for the two sub-parts
dec de ; DE = A+i
; quicksort_c(A, i);
pop hl ; HL = A
call quicksort_a_impl
; quicksort_c(A + i, len - i);
ex de,hl ; HL = A+i
pop de ; DE = end() (and return it preserved)
jp quicksort_a_impl</syntaxhighlight>
Full example with test/debug data for ZX Spectrum is at [[https://gist.github.com/ped7g/0c4e94796b474994ed88d0bdd1bf2f25 github]].
=={{header|Zig}}==
{{trans|Rust}}
'''Works with:''' 0.10.x, 0.11.x, 0.12.0-dev.1390+94cee4fb2
<syntaxhighlight lang="zig">const std = @import("std");
pub fn quickSort(comptime T: type, arr: []T, comptime compareFn: fn (T, T) bool) void {
if (arr.len < 2) return;
const pivot_index = partition(T, arr, compareFn);
quickSort(T, arr[0..pivot_index], compareFn);
quickSort(T, arr[pivot_index + 1 .. arr.len], compareFn);
}
fn partition(comptime T: type, arr: []T, comptime compareFn: fn (T, T) bool) usize {
const pivot_index = arr.len / 2;
const last_index = arr.len - 1;
std.mem.swap(T, &arr[pivot_index], &arr[last_index]);
var store_index: usize = 0;
for (arr[0 .. arr.len - 1]) |*elem_ptr| {
if (compareFn(elem_ptr.*, arr[last_index])) {
std.mem.swap(T, elem_ptr, &arr[store_index]);
store_index += 1;
}
}
std.mem.swap(T, &arr[store_index], &arr[last_index]);
return store_index;
}</syntaxhighlight>
<syntaxhighlight lang="zig">const std = @import("std");
pub fn main() void {
const print = std.debug.print;
var arr = [_]i16{ 4, 65, 2, -31, 0, 99, 2, 83, 782, 1 };
print("Before: {any}\n\n", .{arr});
print("Sort numbers in ascending order.\n", .{});
quickSort(i16, &arr, struct {
fn sortFn(left: i16, right: i16) bool {
return left < right;
}
}.sortFn);
print("After: {any}\n\n", .{arr});
print("Sort numbers in descending order.\n", .{});
quickSort(i16, &arr, struct {
fn sortFn(left: i16, right: i16) bool {
return left > right;
}
}.sortFn);
print("After: {any}\n\n", .{arr});
}</syntaxhighlight>
{{out}}
<pre>
Before: { 4, 65, 2, -31, 0, 99, 2, 83, 782, 1 }
Sort numbers in ascending order.
After: { -31, 0, 1, 2, 2, 4, 65, 83, 99, 782 }
Sort numbers in descending order.
After: { 782, 99, 83, 65, 4, 2, 2, 1, 0, -31 }
</pre>
Line 7,645 ⟶ 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 7,652 ⟶ 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 7,677 ⟶ 10,564:
}(list,0,list.len()-1,cmp);
list;
}</
| |||