Bubble-sort im Prolog-Sprache

Muss ich implementieren Sie den bubble-sort-Funktion (die Sortier-Algorithmus).

Habe ich bereits umgesetzt bubblesort und swap eine Hilfe-Funktion für bubblesort:

swap([X,Y|T1],[Y,X|T1]):-(Y<X,!).
swap([X|T1],[X|T2]):- swap(T1,T2).

bubblesort([],[]) :- !.
bubblesort(T1,T2) :- (bubblesort(swap(T1,T2),T2)).

Bekomme ich eine Endlosschleife. Ich muss die Signatur der Funktion:

bubblesort(T1,T2)

Ich bin stecken geblieben auf diese Frage für 2 Stunden. Hat jemand eine Idee, wie ich das tun kann?

  • Ahh Prolog... Schlechte Erinnerungen 🙂
  • Ahh BubbleSort... Schlechte Erinnerungen 🙂
  • Ahh, BubbleSort und Prolog... gute Erinnerungen 😉
  • Wenn Hausaufgaben, Kennzeichnen Sie bitte als solche.
InformationsquelleAutor tech-ref | 2011-01-20
  1. 1

    Das problem verursacht wurde durch rekursive Abfragen. Beim Abfragen bubblesort(T1, T2),
    es fragt bubblesort(swap(T1, T2), T2), dann durch die zweite Klausel von bubblesort/2,
    bubblesort(swap(swap(T1, T2), T2'), T2) und T2 ist einheitlich wie T2, und dann Schleife.
    Es hat nie das erste Ergebnis swap(T1, T2) Abfrage.

    InformationsquelleAutor Yau-Hsien Huang
  2. 1

    Bis es keine änderung im swap-Verfahren, halten, tauschen. Wenn es keine änderung in der swap-dann haben Sie sortierte Liste.

    bubblesort ( List, SortedList) :-
    swap ( List, List1 ), ! ,
    bubblesort ( List1, SortedList) .
bubblesort ( List, List).

swap ( [ X, Y | Rest ], [ Y, X | Rest ] ) :-
    X > Y, ! .
swap ( [ Z | Rest ], [ Z | Rest1 ] ) : -
    swap (Rest, Rest1 ).
    InformationsquelleAutor ppeczek
  3. 0

    Den einfachen bubble-sort-Algorithmus ist im wesentlichen aus zwei Schleifen:

    1. Durchlaufen der Liste, 'swapping' jedes paar von Elementen, wenn Sie nicht "in Ordnung" (innere Schleife).
    2. Wiederholen (1) auf das Ergebnis, bis die Liste vollständig sortiert ist (äußere Schleife).

    Die innere Schleife (1) ausgedrückt werden kann, wie diese:

    % performs a single pass of a bubble-sort on a list
do_bubble_sort([], []).
do_bubble_sort([X], [X]).
do_bubble_sort([X0,X1|Xs], [X0|Rem]) :-
    X0 =< X1, !,
    do_bubble_sort([X1|Xs], Rem).
do_bubble_sort([X0,X1|Xs], [X1|Rem]) :-
    do_bubble_sort([X0|Xs], Rem).

    do_bubble_sort/2 oben nimmt eine Liste und rekursiv swaps aufeinander folgende Elemente entlang der Liste, wenn Sie nicht erfüllen die =< test (3. Klausel). Diese innere Schleife wird dann aufgerufen durch die äußere Schleife Prädikat bubble_sort/2, wie unten gezeigt:

    % repeatedly performs a bubble sort on a list until it is sorted
bubble_sort(L, SL) :-
    do_bubble_sort(L, L0),
    (sorted_order(L0) ->
        SL = L0
    ;   bubble_sort(L0, SL)
    ).

    Dieses Prädikat nimmt die input-Liste und rekursiv gilt do_bubble_sort/2 bis das Prädikat sorted_order/1 gelingt es, auf das Ergebnis, d.h., wenn die Liste irgendwann sortiert. sorted_order/1 werden können, die wie folgt definiert sind:

    % checks a list of things are in sorted (ascending) order
sorted_order([]).
sorted_order([_]) :- !.
sorted_order([X0,X1|R]) :-
    X0 =< X1,
    sorted_order([X1|R]).

    Dieses Prädikat nimmt eine Liste und rekursiv überprüft, dass jedes paar von aufeinander folgenden Elemente werden in sortierter Reihenfolge (durch die =< testen, nur da wir in do_bubble_sort/2 - dies ist wichtig, da sonst der Algorithmus vielleicht nicht beenden!)

    InformationsquelleAutor sharky
  4. 0

    Es fast weh tut, etwas zu schreiben, so ineffizient:

    bubblesort(L, L1) :-
        (   bubble(L, L2)
        ->  bubblesort(L2, L1)
        ;   L = L1 ).

bubble([A, B|T], L) :-
        (   A > B
        ->  L = [B, A|T]
        ;   L = [A | L1],
            bubble([B|T], L1)).

:- bubblesort([2,4,2,3, 2, 6,6,3,1, 11, 2, 3, 1], Out).
    InformationsquelleAutor salva
  5. -1
    bubblesort ( List, SortedList) :-
    swap ( List, List1 ), ! ,
    bubblesort ( List1, SortedList) .
bubblesort ( List, List).
    InformationsquelleAutor T.Dilak
Schreibe einen Kommentar