Zadania do lekcji 8¶

Zadanie 801

Potraktuj listę do posortowania \(A\) jako listę punktów o współrzędnych \((i, A[i])\). Narysuj te punkty na wykresie. Zrób oddzielny wykres dla każdego etapu sortowania korzystając z algorytmu sortowania bąbelkowego. Spróbuj zrobić animację.

Zadanie 802

Zaimplementuj algorytm sortowania przez wstawianie. Jego opis znajedziesz np. na wikipedii.

Zadanie 803

Od czasu do czasu powstają algorytmy, które nie do końca mają sens. Tworzy się je, bo można... To zupełnie tak jak zapytano Reinholda Messnera dlaczego chodzi po górach. odpowiedział po prostu “bo są”.

Sortowanie z użyciem bardzo konkretnych algorytmów, gdzie porównujemy wartości w mniej lub bardziej skuteczny sposób to tylko jedna z możliwości. Pomyślmy nieco bardziej abstrakcyjnie. Jeżeli mielibyśmy poukładać talię kart w pewien sposób, to możemy oczywiście wykorzystać sortowanie przez wstawianie i zwykle to robimy. Ale można by taką talię wziąć i wyrzucić w górę. Gdy karty spadną to istnieje szansa (bardzo mała), że same, losowo poukładają się w oczekiwany sposób. Jeżeli to nie nastąpi to można by spróbować raz jeszcze, albo nawet kilka razy...

Zadanie polega na napisaniu programu realizującego właśnie taki algorytm. Załóż, że masz listę L liczb. Przeorganizuj ją losowo i sprawdź, czy jest posortowana. Jeżeli nie to spróbuj raz jeszcze...

Nie testuj na zbyt dużych listach, bo złożoność obliczeniowa tego typu algorytmu randomizowanego to \(O((n - 1)!)\), gdzie n to liczba elementów.