Sortieren einer Liste in Prolog

Prolog hat eine einzigartige Weise des Umgangs mit Dingen, zumal praktisch jede operation beinhaltet die Rekursion der einen oder anderen Art.

Eines der klassischen Beispiele für jede Sprache ist die Sortierung einer Liste von Integer-zahlen in aufsteigender Reihenfolge.

Was eine optimale Art und Weise (ohne Verwendung von zu vielen built-in-Prädikate, die verhindert, ein Art - /2-Prädikat) zu Sortieren, eine zufällige Liste von Integer-zahlen?

InformationsquelleAutor Raceimaztion | 2011-12-08
  1. 7

    Römischen Bartók Prolog-Programmierung Website gibt Beispiele von verschiedenen algorithmen Sortieren, endend mit einer optimierten quicksort.

    quick_sort2(List,Sorted):-q_sort(List,[],Sorted).
q_sort([],Acc,Acc).
q_sort([H|T],Acc,Sorted):-
    pivoting(H,T,L1,L2),
    q_sort(L1,Acc,Sorted1),q_sort(L2,[H|Sorted1],Sorted)
    • Nur ein Hinweis: das Prädikat (mit dem schwenkbaren/4 umgesetzt in deinem link) führt eine absteigende Sortierung, Sie haben eine Umkehrung der Vergleichsoperatoren schwenken/4 führen Sie eine aufsteigende Sortierung.
    InformationsquelleAutor dommer
  2. 5

    Soweit ich weiß die beste Sortier-algorithmen, geschrieben in Prolog direkt, ohne Verweis auf eine spezielle built-ins benutzen eine form von merge-sort.

    Eine häufige Optimierung ist zu Beginn der Zusammenführung nicht mit Listen der Länge 1, aber mit bereits sortierten Segmenten.

    Ist, um die Liste zu Sortieren [4,5,3,6,2,7,1,2] die Listen [4,5],[3,6],[2,7],[1,2] würde zusammengeführt werden.

    Diese kann noch weiter optimiert werden durch zusammensetzen von sortierten Listen nicht nur in aufsteigender Richtung, aber auch in die andere Richtung. Für das obige Beispiel würde dies bedeuten, dass die sortiert-segment zusammengesetzt ist, wie folgt:

    [4,5|_]
[3,4,5|_]
[3,4,5,6|_]
...

    Beachten Sie, dass im Prolog-es ist geradlinig zu verlängern, eine Liste sowohl am Anfang und am Ende.

    Also, wir haben zu fusionieren [1,2,3,4,5,6,7] und [2] nur.

    Einem aktuellen system mit der original-Implementierung (~1984) von Richard O ' Keefe ist Ciao-Prolog in
    ciao-1.15/lib/sort.pl    .

    • Laden Sie die aktuelle version von Ciao.
    • Mein Favorit sind die Bäume für die Sortierung, siehe auch stackoverflow.com/questions/3270543/... , aber Prolog Bäume mit mehr kopieren als Java-Bäume.
    InformationsquelleAutor false
Schreibe einen Kommentar