Sprawdź się
Algorytm Bogo Sort to algorytm, którego działanie polega na ciągłym losowym ustawianiu sortowanych elementów i sprawdzaniu, czy po wymieszaniu elementy są posortowane. Operacje mieszania powtarzane są aż do posortowania elementów. Aby posortować talię kart tym algorytmem należy wyrzucić talię w powietrze, pozbierać z podłogi i sprawdzić, czy karty ułożyły się w oczekiwanym porządku. Czynność powtarzamy aż do uzyskania oczekiwanego efektu. Jego złożoność obliczeniowa wynosi .
Uzupełnij symulację przedstawiającą złożoność obliczeniową algorytmu Bogo Sort.
Innym ciekawym przykładem algorytmu sortowania jest sortowanie naiwne. Polega ono na tym, że przeglądamy kolejne pary elementów sortowanego zbioru. Jeśli elementy są w złej kolejności, należy zamienić je miejscami i rozpocząć operację od początku zbioru. Jeśli po przejrzeniu wszystkich par nie wystąpi zamiana, zbiór jest posortowany.
Zapisz za pomocą pseudokodu ten algorytm.
Specyfikacja problemu:
Dane:
liczby– tablica liczb naturalnych
Wynik:
posortowana niemalejąco tablica
liczby
Sortowanie koktajlowe jest przykładem zmodyfikowanego sortowania bąbelkowego. W jego przypadku po przejściu przez zbiór elementów od pierwszego do ostatniego elementu, kolejny przebieg odbywa się od ostatniego elementu do pierwszego. Algorytm sprawdza kolejne pary – jeśli liczby są w odpowiedniej kolejności, przechodzi do porównania kolejnej pary. Jeśli nie, zamienia liczby miejscami. Za każdym kolejnym przejściem algorytm zmniejsza zakres sprawdzanych liczb, ponieważ po każdym największy lub najmniejszy element sprawdzanego zbioru zostaje posortowany. Posortowane są również te elementy, które wcześniej zostały umieszczone na odpowiednich (posortowanych) pozycjach.
Krótka animacja przedstawiająca działanie algorytmu:
Film dostępny pod adresem /preview/resource/R1La2fCJ1fIu7
Animacja przedstawiająca działanie algorytmu.
Zapisz za pomocą pseudokodu ten algorytm.
Specyfikacja problemu:
Dane:
liczby– tablica liczb naturalnych
Wynik:
posortowana niemalejąco tablica
liczby