Ćwiczenia 2: sortowanie, część I

Zadanie 1 (Algorytm Shella)

Udowodnij, że jeżeli dwuwymiarową tablicę liczbową, posortowaną niemalejąco kolumnami, posortujemy wierszami, to nadal będzie ona posortowana kolumnami.
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.
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.
Załóżmy, że tablica $A$ jest jednocześnie 2- i 3-posortowana. Ile wynosi maksymalna liczba inwersji w takiej tablicy?
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)$ .

Wskazówka

Zastosuj sortowanie przez wstawianie i skorzystaj z rozwiązania zadania 2.

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.

Wskazówka

Zastosuj sortowanie przez wybór.

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)$ .

Wskazówka

Rozważmy przypadek, gdy oba scalane podciągi mają długości co najmniej

$\sqrt n$ . Idea algorytmu: podziel sortowane podciągi na bloki o długościach

$\sqrt n$ ; posortuj bloki względem ich ostatnich elementów; potraktuj pierwszy blok (jego elementy) jako bufor; scalaj w pętli dwa kolejne bloki zapisując wynik w buforze i przesuwając bufor w prawo; posortuj bufor i scal go z posortowaną resztą.

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.

Informatyka MIMUW