Ćwiczenia do wykładu 05
- Który z wymienionych algorytmów sortowania InsertionSort, MergeSort,
QuickSort, SelectioSort jest stabilny?
- Zaimplementuj następującą wersję rekurencyjnego algorytmu sortowania
przez scalanie: jeżeli długość rozważanego ciągu jest mniejsza niż M, to
sortujemy go stosując algorytm InsertionSort, w przeciwnym przypadku
dzielimy ciąg na dwie części, a do ich posortowania stosujemy to samo
postępowanie. Następnie posortowane części scalamy.
Zbadaj koszt tego algorytmu.
- Przedstaw kolejne stany tablicy pomocniczej podczas sortowania ciągu
2,3,4,2,1,2,5,1,1,4,1 przy pomocy algorytmu CountingSort.
- Przedstaw wynik każdego z czterech etapów sortowania algorytmem RadixSort
następującego ciągu słów w porządku leksykograficznym: rola, kopa, pora, para,
kara, poza, koza, ropa.
- Rozważmy następujący algorytm scalania, będący modyfikacją algorytmu
InsertionSort. Sortowanie ciągu n elementowego odbywa się w n-1 krokach. W
i-tym kroku (i zmienia się od 2 do n) dla elementu z pozycji i-tej znajdujemy
metodą binarnych poszukiwań właściwą mu pozycję j wśród elementów już
uporządkowanych na pozycjach od 1 do i-1. Wszystkie elementy od pozycji
j-tej do (i-1)-szej przesuwamy o jedną pozycję wyżej, a na zwolnione j-te
miejsce wstawiamy element i-ty.
Zbadaj koszt tego algorytmu i zaimplementuj go.
- Zaimplementuj algorytm sortowania pozycyjnego zakładając, że
elementy sortowanego ciągu znajdują się w kolejce q.
- Przypuśćmy, że w wąskiej i dość długiej szufladce znajdują się
jednakowego rozmiaru kule czerwone, niebieskie i białe. Odpowiednio c, n i b
kul. Szufladka ma na dnie specjalne wyżłobienia, pozwalające umieścić, w
każdym z nich, jedną kulę. Zadanie polega na takim ułożeniu kul, by kule
niebieskie poprzedzały białe, a kule białe poprzedzały kule czerwone. Jedyną
dozwoloną operacją (poza sprawdzeniem koloru kuli) jest operacja zamiany
miejscami dwóch kul. Zaproponuj algorytm pozwalający
zrealizować zadanie możliwie małą liczbą operacji. Oszacuj koszt tego
algorytmu.
- Zaproponuj liniowy algorytm sortowania ciągu złożonego z samych zer i
jedynek.
- Na prostokątnej tablicy o rozmiarze n x m ogłoszeń powieszono k plakatów.
Niestety niektóre z nich zostały częściowo lub całkowicie zasłonięte przez
inne. Napisz algorytm, który pozwoli ustalić, który z plakatów jest całkowicie
widoczny. Zakładamy, że położenie lewego górnego rogu każdego plakatu
oraz jego długość, są liczbami całkowitymi.