Informatyka MIMUW

Zadanie 1 (Algorytm Shella)

1. Udowodnij, że jeżeli dwuwymiarową tablicę liczbową, posortowaną niemalejąco kolumnami, posortujemy wierszami, to nadal będzie ona posortowana kolumnami.
2. Niech \( \displaystyle A[1..n] \) będzie tablicą liczb całkowitych i niech \( \displaystyle h \) będzie dodatnią liczbą całkowitą. Powiem, że \( \displaystyle A \) jest \( h \)-posortowana, jeżeli dla każdego \( \displaystyle i = 1, \ldots, n - h \), \( \displaystyle A[i] \le A[i+h]\). Algorytm \(h\)-sortowania nazywamy każdy algorytm, który sortuje niemalejąco i niezależnie wszystkie podtablice \( \displaystyle A[i], A[i+h], A[i+2h], \ldots \), dla \( \displaystyle i = 1, 2, \ldots, \min( n, h)\). Udowodnij, że jeżeli \(h_2\)-posortujemy \(h_1\)-posortowaną tablicę \( A \), to będzie ona nadal \(h_1\)-posortowana.
3. Niech \( k \) będzie dodatnią liczbą całkowitą i niech \( h_1, h_2, \ldots, h_k \) będzie malejącym ciągiem dodatnich liczb całkowitych, w którym \( h_k = 1\). Rozważmy następujący algorytm sortowania:

   for i := 1 to k do
   \( \mbox{ }\) wykonaj \( h_i \)-sortowanie algorytmem sortowania przez wstawianie, niezależnie na każdym podciągu;

   Udowodnij, że powyższy algorytm sortuje.

4. Załóżmy, że tablica \( A \) jest jednocześnie 2- i 3-posortowana. Ile wynosi maksymalna liczba inwersji w takiej tablicy?
5. Zanalizuj złożoność algorytmu Shella przy założeniu, że ciąg \( h_1, h_2, \ldots, h_k \) składa się ze wszystkich liczb postaci \( 2^p3^q \) i mniejszych od \( n \), gdzie \( p \) i \( q \) są nieujemnymi liczbami całkowitymi.

Zadanie 2 (Przesunięcie cykliczne w miejscu)

Dana jest \(n\)-elementowa tablica \(A[1..n]\) oraz liczba całkowita \(k \in [1..n] \). Zaproponuj liniowy algorytmy przesunięcia cyklicznego elementów tablic \( A \) o \( k \) pozycji w lewo.

Przykład: ciąg \( [1,2,3,4,5] \) przesunięty cyklicznie o 2 w lewo ma postać \( [3,4,5,1,2] \).

Zadanie 3 (Proste scalanie w miejscu)

Dane są dodatnie liczby całkowite \( k, n \), \( k \le n\), oraz tablica liczb całkowitych \( A[1..n] \) taka, że podtablice \( a[1..k] \) i \( a[k+1..n] \) są uporządkowane nie malejąco. Przy założeniu, że \( k = O(\sqrt n) \) zaproponuj algorytm sortowania tablicy (scalania dwóch ciągów uporządkowanych) \( A \) w miejscu i w czasie \(O(n)\).

Zadanie 4 (Sortowanie blokowe)

Niech \( \displaystyle A[1..n] \) będzie tablicą liczb całkowitych. Przyjmijmy, że \( \displaystyle n = r^2 \) dla pewnego naturalnego \( r \). Zawartość tablic \( A \) traktujemy jako zapis \( r \) rekordów (bloków). Każdy rekord-blok zajmuje spójny fragment tablicy od pozycji \( (i-1)r+1 \) do pozycji \( ir \), dla pewnego \( i \in [1..r] \). Kluczem w rekordzie jest ostatni element bloku. Zaproponuj sortowanie rekordów względem ich kluczy. Twój algorytm powinien działać w miejscu i w czasie liniowym. Kolejność elementów w rekordzie nie może ulec zmianie.

Zadanie 5 (Scalanie w miejscu)

Dane są dodatnie liczby całkowite \( k \le n \) oraz tablica liczb całkowitych \( A[1..n] \) taka, że podtablice \( A[1..k] \) i \( A[k+1..n] \) są uporządkowane nie malejąco. Zaproponuj algorytm sortowania tablicy (scalania dwóch ciągów uporządkowanych) \( A \) w miejscu i w czasie \(O(n)\).

Zadanie 6 (Sortowanie w miejscu i stabilnie)

Zaproponuj algorytm, który sortuje \(n\)-elementowe ciągi zer i jedynek w czasie \( O(n\log n)\), w miejscu i stabilnie.

Zadanie 7 (Sortowanie optymalne 5 elementów)

Zaproponuj algorytm sortujący za pomocą minimalnej liczby porównań ciągi 5-elementowe.