« poprzedni punkt   następny punkt »



Ćwiczenia do wykładu 05
 
  1. Który z wymienionych algorytmów sortowania InsertionSort, MergeSort, QuickSort, SelectioSort jest stabilny?
     
  2. 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.
     
  3. Przedstaw kolejne stany tablicy pomocniczej podczas sortowania ciągu  2,3,4,2,1,2,5,1,1,4,1 przy pomocy algorytmu CountingSort.
     
  4. 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.
     
  5. 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.
     
  6. Zaimplementuj algorytm sortowania pozycyjnego zakładając, że  elementy sortowanego ciągu znajdują się w kolejce q.
     
  7. 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.
     
  8. Zaproponuj liniowy algorytm sortowania ciągu złożonego z samych zer i jedynek.
     
  9. 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.
« poprzedni punkt    następny punkt »