# Quicksort (Mercury)

Other implementations: C | C++ | Eiffel | Erlang | Haskell | JavaScript | Mathematica | Mercury | Oz | Python | Python, arrays | Scala | Visual Basic .NET

Here is a Quicksort in Mercury.

## First Quicksort

```<<quicksort.m>>=
:- module quicksort.
:- interface.
:- import_module list, int.
:- func qsort(list(int)) = list(int).
:- mode qsort(in) = out is det.
:- implementation.
%
% quicksort
%
qsort( []) = [].
qsort( [Hd | Tl]) = Result :- (
/* length 1 */
Tl = [] -> Result = [Hd]
;
/* length 2 */
Tl = [Hd2] -> (
Hd =< Hd2 -> Result = [Hd | [Hd2]]
;
Result = [Hd2 | [Hd]]
)
;
/* else */
InputList = [Hd | Tl],
Pivot = list.index0_det( InputList, list.length( InputList) / 2),
pivot_classify( InputList, Pivot, Lows, Mids, Highs),
Result = list.append( list.append( qsort(Lows), Mids), qsort(Highs))
).
%
% classify list elements
%
:- pred pivot_classify( list(int), int, list(int), list(int), list(int)).
:- mode pivot_classify( in, in, out, out, out) is det.
pivot_classify( [], _Pivot, [], [], []).
pivot_classify( [Hd | Tl], Pivot, Lows, Mids, Highs) :-
( Hd < Pivot -> some [Lows0] (
pivot_classify( Tl, Pivot, Lows0, Mids, Highs),
Lows = [Hd | Lows0]
)
;
Hd > Pivot -> some [Highs0] (
pivot_classify( Tl, Pivot, Lows, Mids, Highs0),
Highs = [Hd | Highs0]
)
;
/* else */
some [Mids0] (
pivot_classify( Tl, Pivot, Lows, Mids0, Highs),
Mids = [Hd | Mids0]
)
).
:- end_module quicksort.
```

## Test module

```<<qsorttest.m>>=
:- module qsorttest.
:- interface.
:- import_module io.
:- pred main(io.state, io.state).
:- mode main(di, uo) is det.
:- implementation.
:- import_module int, list, quicksort.
main -->
sort_and_print( [1, 8, 3, 4, 2, 5]),
%
% empty test
io.nl,
io.write_string("empty test!"),
io.nl,
sort_and_print( []),
%
% single element test
io.nl,
io.write_string("single element test!"),
io.nl,
sort_and_print( [1]).
:- pred sort_and_print(list(int)::in, io.state::di, io.state::uo) is det.
sort_and_print( InputList, !IO) :-
some [SortedList] (
io.write_string("original list: ", !IO),
io.write_list( InputList, ",", io.write_int, !IO),
io.nl(!IO),
io.write_string("sorted list: ", !IO),
SortedList = qsort( InputList),
io.write_list( SortedList, ",", io.write_int, !IO),
io.nl(!IO)
).
:- end_module qsorttest.
```

## Compilation and run

1. compile quicksort.m exporting interfaces (-i)
2. compile qsorttest.m specifying the interfaces used (without extension)
```>mmc -i quicksort.m
>mmc qsorttest.m quicksort
>
>qsorttest
>original list: 1, 8, 3, 4, 2, 5
>sorted list: 1, 2, 3, 4, 5, 8
>
>empty test!
>original list:
>sorted list:
>
>single element test!
>original list: 1
>sorted list: 1
```

## With Tail Recursive routine

To test it change the import clause in the test module, to include quicksort_tr instead of quicksort.

```<<quicksort_tr.m>>=
:- module quicksort_tr.
:- interface.
:- import_module list, int.
:- func qsort(list(int)) = list(int).
:- mode qsort(in) = out is det.
:- implementation.
%
% quicksort
%
qsort( []) = [].
qsort( [Hd | Tl]) = Result :- (
/* length 1 */
Tl = [] -> Result = [Hd]
;
/* length 2 */
Tl = [Hd2] -> (
Hd =< Hd2 -> Result = [Hd | [Hd2]]
;
Result = [Hd2 | [Hd]]
)
;
/* else */
InputList = [Hd | Tl],
Pivot = list.index0_det( InputList, list.length( InputList) / 2),
/* added initial values for accumulators */
pivot_classify( InputList, Pivot, Lows, Mids, Highs, [], [], []),
Result = list.append( list.append( qsort(Lows), Mids), qsort(Highs))
).
%
% classify list elements ( Tail recursive)
%
:- pred pivot_classify( list(int), int, list(int), list(int), list(int), list(int), list(int), list(int)).
:- mode pivot_classify( in, in, out, out, out, in, in, in) is det.
pivot_classify( [], _Pivot, Lows, Mids, Highs, LowsAcum, MidsAcum, HighsAcum) :-
Lows = LowsAcum,
Mids = MidsAcum,
Highs = HighsAcum.
pivot_classify( [Hd | Tl], Pivot, Lows, Mids, Highs, LowsAcum0, MidsAcum0, HighsAcum0) :-
(
( Hd < Pivot -> (
LowsAcum1 = [ Hd | LowsAcum0],
MidsAcum1 = MidsAcum0,
HighsAcum1 = HighsAcum0
)
;
Hd > Pivot -> (
LowsAcum1 = LowsAcum0,
MidsAcum1 = MidsAcum0,
HighsAcum1 = [ Hd | HighsAcum0]
)
;
/* else */
LowsAcum1 = LowsAcum0,
MidsAcum1 = [ Hd | MidsAcum0],
HighsAcum1 = HighsAcum0
),
pivot_classify( Tl, Pivot, Lows, Mids, Highs, LowsAcum1, MidsAcum1, HighsAcum1)
).
:- end_module quicksort_tr.
```