1. Omówić sprawdzian (podać wyniki i właściwe rozwiązania)
2. Przeprowadzić porównanie algorytmów sortowania robiąc:
a. konkretne przykłady działania algorytmów
b. porównując koszty w przypadku ogólnym
3. Zrealizować jakiś z omawianych na wykładzie algorytmów.
Wydaje mi się , ze przyszła pora na następną wejściówkę, która raczej powinna
się nazywać "wyjściówką" o sortowaniu Można zrobić bardzo podobne
zadanka do tych ze sprawdzianu.
Oto kilka pomysłów na pytania' wejściówkowe':
1. Ile porównań wykona algorytm sortowania przez selekcje ,
a ile algorytm Szybkiego sortowania, jeśli zastosujemy je do ciągu 1, 2, 3, 4.
2. Podaj kolejne stany tablicy, której elementy należy uporządkować
rosnąco stosując algorytm sortowania przez wstawianie (insertion_sort), i w
której na początku znajdują się elementy 1 5 2 4 3.
3. Który z algorytmów Merge_sort (sortowania przez scalanie) czy Quick_sort
(algorytm szybkiego sortowania) ma mniejszy koszt w przypadku
pesymistycznym?
4. Czy następujące zdanie jest prawdziwe czy fałszywe?
" Gdybyśmy umieli znajdować element minimalny w dowolnym ciągu z kosztem
stałym, to algorytm sortowania przez selekcję byłby algorytmem
liniowym."