Prolog … 快速排序法 … 白話版… XD

sort.pl

Prolog … 快速排序法 … 白話版… XD

/* 
 * [] 附加 Result 的 結果為 Result
 */
append([], Result, Result).

/*     
 *  Tail 附加 Other 的結果為 Subappend => [Head | Tail] 附加 Other 的結果為 [Head | Subappend]
 *       
 */
append([Head | Tail], Other, [Head | Subappend]) :-
    append(Tail, Other, Subappend).
    
/* 
 * Pivot 作為 [] 的切分，小於等於 Pivot 的清單會是 []，大於 Pivot 的清單會是 []
 */
partition(Pivot, [], [], []). 

/*
 *  Head 小於等於 Pivot，而且 Pivot 作為 Tail 的切分時，小於等於 Pivot 的清單會是 Smaller，大於 Pivot 的清單會是 Bigger => 
 *      Pivot 作為 [Head | Tail] 的切分，小於等於 Pivot 的清單是 [Head | Smaller]，大於 Pivot 的清單會是 Bigger 
 */
partition(Pivot, [Head | Tail], [Head | Smaller], Bigger) :- 
   Head @=< Pivot,
   partition(Pivot, Tail, Smaller, Bigger).

/*
 *  Head 大於 Pivot，而且 Pivot 作為 Tail 的切分時，小於等於 Pivot 的清單會是 Smaller，大於 Pivot 的清單會是 Bigger =>
 *       Pivot 作為 [Head | Tail] 的切分，小於等於 Pivot 的清單是 Smaller，大於 Pivot 的清單會是 [Head | Bigger]
 */
partition(Pivot, [Head | Tail], Smaller, [Head | Bigger]) :- 
   Head @> Pivot,
    partition(Pivot, Tail, Smaller, Bigger).

/*
 * [] 快速排序後的結果是 []
 */
quicksort([], []).

/*
 * 
 *   Head 作為 Tail 的切分，小於等於 Head 的清單是 Smaller，大於 Head 的清單為 Bigger，而且
 *   Smaller 快速排序後的結果會是 SmallerSorted，Bigger 快速排序後的結果是會是 BiggerSorted，而且
 *   SmallerSorted 附加 [Head | BiggerSorted] 的結果，會是 Sorted =>
 *           [Head|Tail] 快速排序後的結果是 Sorted 
 */
quicksort([Head|Tail], Sorted) :-
  partition(Head, Tail, Smaller, Bigger),
  quicksort(Smaller, SmallerSorted),
  quicksort(Bigger, BiggerSorted),
  append(SmallerSorted, [Head | BiggerSorted], Sorted).