How to resolve the algorithm Sorting algorithms/Quicksort step by step in the Mercury programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Sorting algorithms/Quicksort step by step in the Mercury programming language
Table of Contents
Problem Statement
Sort an array (or list) elements using the quicksort algorithm. The elements must have a strict weak order and the index of the array can be of any discrete type. For languages where this is not possible, sort an array of integers.
Quicksort, also known as partition-exchange sort, uses these steps.
The best pivot creates partitions of equal length (or lengths differing by 1). The worst pivot creates an empty partition (for example, if the pivot is the first or last element of a sorted array). The run-time of Quicksort ranges from O(n log n) with the best pivots, to O(n2) with the worst pivots, where n is the number of elements in the array.
This is a simple quicksort algorithm, adapted from Wikipedia. A better quicksort algorithm works in place, by swapping elements within the array, to avoid the memory allocation of more arrays. Quicksort has a reputation as the fastest sort. Optimized variants of quicksort are common features of many languages and libraries. One often contrasts quicksort with merge sort, because both sorts have an average time of O(n log n). Quicksort is at one end of the spectrum of divide-and-conquer algorithms, with merge sort at the opposite end.
With quicksort, every element in the first partition is less than or equal to every element in the second partition. Therefore, the merge phase of quicksort is so trivial that it needs no mention! This task has not specified whether to allocate new arrays, or sort in place. This task also has not specified how to choose the pivot element. (Common ways to are to choose the first element, the middle element, or the median of three elements.) Thus there is a variety among the following implementations.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Sorting algorithms/Quicksort step by step in the Mercury programming language
Source code in the mercury programming language
%%%-------------------------------------------------------------------
:- 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:
%%%-------------------------------------------------------------------
:- 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:
You may also check:How to resolve the algorithm Arrays step by step in the MiniScript programming language
You may also check:How to resolve the algorithm Sum multiples of 3 and 5 step by step in the PureBasic programming language
You may also check:How to resolve the algorithm Pythagorean triples step by step in the MATLAB / Octave programming language
You may also check:How to resolve the algorithm 100 prisoners step by step in the jq programming language
You may also check:How to resolve the algorithm Mandelbrot set step by step in the Pascal programming language