Quicksort (Mercury)

From LiteratePrograms

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

Here is a Quicksort in Mercury.

Contents 1 First Quicksort 2 Test module 3 Compilation and run 4 With Tail Recursive routine

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.

Download code