Witam mam do napisania algorytm sortowania bąbelkowego za pomocą maszyny Turinga. Wiem w jaki sposób porównywać i zamieniać dane, lecz nie wiem w jaki sposób zakończyć działanie tzn. jak sprawdzić czy ciąg został już posortowany . Maszyna ma posortować wymieszane dane wejściowe "abcd". Prosił bym o jakieś wskazówki .
0
2
Nie bardzo rozumiem. Przecież sortowanie bąbelkowe ma jasny warunek końca. Co jedno przejście przez ciąg danych "odcinasz" sobie jeden symbol, na przykład przez oznaczenie go sobie a', b' itd. I potem jak robisz kolejny przebieg to już bez tego jednego elementu. Sortowanie o którym mówisz działa akurat tak że w każdym obiegu pętli przesuwa na koniec jeden element który będzie na "swoim miejscu".
Załóżmy że mamy:
bdac -> bd -> ad -> cd -> bacd i widać że 'd' juz jest na swoim miejscu więc oznaczamy je jako d' i teraz jak drugi raz lecimy od początku sortując to nie wykonujemy już porównania z tym d'.