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 .
Maszyna Turinga sortowanie bąbelkowe
- Rejestracja: dni
- Ostatnio: dni
- Lokalizacja: Space: the final frontier
- Postów: 26433
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'.