    1:- module(quicksort,
    2    [
    3        quicksort/3,
    4        quicksort_number_asc/3,
    5        quicksort_number_desc/3
    6    ]).

Binary search on sorted lists

An implementation of the classic Quicksort sorting algorithm on generic lists. Quicksort works by selecting a 'pivot' element from the list to be sorted and partitioning the other elements into two sublists, according to whether they are less than or greater than the pivot.The sublists are then sorted recursively. For a description of the quicksort algorithm, see https://en.wikipedia.org/wiki/Quicksort .
This implementation takes as input a comparator. This is a predicate able to perform a comparison between any two elements of the input list as parameters, and return a negative number, zero, or a positive number, to indicate whether the first parameter is smaller than, equal to, or greater than the second parameter, respectively.

author: - GT Nunes
version: - 1.3.2
copyright: - (c) TheWiseCoder 2020-2021
license: - BSD-3-Clause License */

   28%-------------------------------------------------------------------------------------
   29
   30:- meta_predicate quicksort(+, 3, -),
   31                  quicksort_list(3, +, -),
   32                  quicksort_partition(3, +, +, +, +).

quicksort(+List:list, :Comparator:pred, -SortedList:list) is det

Sort the contents of List according to the given comparison predicate, and unify the result with SortedList.
The comparison predicate must accept two parameters, ValueX and ValueY, which might be any two elements in List, and have the following behavior:

<Comparator>(+ValueX, +ValueY, -Result:number) is det
where Result is unified with
  a) 0 (zero)          - ValueX is equal to ValueY
  b) a negative number - ValueX is less than ValueY
  c) a positive number - ValueX is greater than ValueY

The criteria that will determine the results of the comparisons are entirely up to Comparator, and as such it must be able to handle the values it will receive. Nothing is done if List has less than 2 elements.

Arguments:

`List`	- The list to be sorted
`Comparator`	- Predicate to perform comparisons between any two elements in `List`
`SortedList`	- The resulting sorted list

   55quicksort(List, Comparator, SortedList) :-
   56
   57    % does the input contain more than one element ?
   58    length(List, Len),
   59    (Len > 1 ->
   60        % yes, so sort them using the given comparator
   61        quicksort_list(Comparator, List, SortedList)
   62    ;
   63        % no, so just unify SortedList with List and exit
   64        SortedList = List
   65    ).
   66
   67quicksort_list(_Comparator, [], []).
   68    
   69quicksort_list(Comparator, [ValueX|ValuesX], ValuesY) :-
   70
   71    quicksort_partition(Comparator, ValuesX, ValueX, ValuesLeft, ValuesRight),
   72    quicksort_list(Comparator, ValuesLeft, ListLeft),
   73    quicksort_list(Comparator, ValuesRight, ListRight),
   74    quicksort_append(ListLeft, [ValueX|ListRight], ValuesY).
   75
   76quicksort_partition(_Comparator, [], _ValueY, [], []).
   77
   78quicksort_partition(Comparator, [ValueX|ValuesX],
   79                        ValueY, [ValueX|ListLeft], ListRight) :-
   80
   81    call(Comparator, ValueX, ValueY, Cmp),
   82    Cmp =< 0,
   83    quicksort_partition(Comparator, ValuesX, ValueY, ListLeft, ListRight).
   84
   85quicksort_partition(Comparator, [ValueX|ValuesX],
   86                        ValueY, ListLeft, [ValueX|ListRight]) :-
   87
   88    call(Comparator, ValueX, ValueY, Cmp),
   89    Cmp > 0,
   90    quicksort_partition(Comparator, ValuesX, ValueY, ListLeft, ListRight).
   91
   92quicksort_append([], ValuesY, ValuesY).
   93
   94quicksort_append([ValueX|ValuesX], ValuesY, [ValueX|ValuesZ]) :-
   95    quicksort_append(ValuesX, ValuesY, ValuesZ).
   96
   97%-------------------------------------------------------------------------------------

quicksort_number_asc(+ValueX:number, +ValueY:number, -Cmp:int) is det

Compare the numbers ValueX and ValueY ascendingly.
Unify Cmp with -1, 0, or 1, depending on whether ValueX is smaller than, equal to, or greater than, ValueY.

Arguments:

`ValueX`	- The first value to compare
`ValueY`	- The second value to compare
`Cmp`	- The result of the comparison

  109quicksort_number_asc(ValueX, ValueY, Cmp) :-
  110
  111    (ValueX < ValueY ->
  112        Cmp = -1
  113    ; ValueX > ValueY ->
  114        Cmp = 1
  115    ; otherwise ->
  116        Cmp = 0
  117    ).

quicksort_number_desc(+ValueX:number, +ValueY:number, -Cmp:int) is det

Compare the numbers ValueX and ValueY descendingly.
Unify Cmp with -1, 0, or 1, depending on whether ValueX is greater than, equal to, or smaller than, ValueY.

Arguments:

`ValueX`	- The first value to compare
`ValueY`	- The second value to compare
`Cmp`	- The result of the comparison

  129quicksort_number_desc(ValueX, ValueY, Cmp) :-
  130
  131    (ValueX > ValueY ->
  132        Cmp = -1
  133    ; ValueX < ValueY ->
  134        Cmp = 1
  135    ; otherwise ->
  136        Cmp = 0
  137    )