Intro

QuickSort is een recursief sorteeralgoritme bedacht door Tony Hoare. Hij werkte destijds aan een project in verband met computervertalingen. Daarvoor was het nodig om korte Russische zinnen snel en efficiënt te sorteren. Het algemene werkingsprincipe van QuickSort wordt weleens kort omschreven als verdeel en heers.

Het doel van QuickSort is om een rij van ongesorteerde getallen, gesorteerd terug te geven. Dit gebeurt in 4 stappen.

  1. Kies een Spil element (ook wel pivot genoemd)
  2. Partitionering: splits de rij op in 2 rijen, Kleiner en Groter die respectievelijk de getallen kleiner en strikt groter dan de spil bevatten (de spil zelf zit in geen van beide rijen).
  3. Pas de vorige stappen toe op de rijen Kleiner en Groter om hun gesorteerde evenbeeld te vinden (KleinerGesorteerd en GroterGesorteerd)
  4. Plak nu die rijen aan elkaar met de spil in het midden, dus opeenvolgende KleinerGesorteerd, Spil, GroterGesorteerd.

Het basisgeval van de recursie is de lege lijst, die is per definitie gesorteerd.Naar: Wikipedia1

Oefening

Schrijf een predicaat qs(+Lijst, -Orde) die een gesorteerde verschillijst variant van Lijst teruggeeft als Orde. Gebruik het QuickSort algoritme hierboven beschreven Hiervoor hoef je de rij niet “inplace” te partitioneren. Gebruik verschillijsten om de resultaten aan elkaar te “plakken”.

?- qs([10, 5, 9, 5, 4, 11, 23, 5, 1], S-[]).
S = [1, 4, 5, 5, 5, 9, 10, 11, 23]

?- qs([1337,42,7], S-[an,other,end, 1,2,3]).
S = [7, 42, 1337, an, other, end, 1, 2, 3]