Informatyka MIMUW

Ćwiczenie 1

Jaka jest maksymalna liczba inwersji w tym przypadku?

Powstaje pytanie jak szybko możemy sortować w tym przypadku. Tak naprawdę naszym celem jest scalenie dwóch uporządkowanych ciągów \( a[1..s] \) i \( a[s+1..n] \) w jeden uporządkowany ciąg \( a[1..n] \). Załóżmy, że dysponujemy dodatkową tablicą \( b[1..s] \). Scalania będziemy wykonywać bezpośrednio w tablicy \( a \). Dlatego w pierwszym kroku naszego algorytmu kopiujemy podciąg \( a[1..s] \) do pomocniczej tablicy \( b \). Następnie przeglądamy ciągi \( a[s+1..n] \) i \( b[1..s] \) z lewa na prawo. W jednym kroku porównujemy ich czołowe elementy. Mniejszy z nich umieszczamy na docelowej pozycji w tablicy \( a \) i na koniec w ciągu, z którego pochodził mniejszy element, przesuwamy się o jedną pozycję w prawo. Formalny zapis tego algorytmu został przedstawiony jako procedura Merge-1.

Algorytm Scalanie-1

procedure  Merge-1; 
begin 
  //kopiowanie a[1..s] do b[1..s] 
  for i := 1 to s do 
    b[i] := a[i];
  //właściwe scalanie 
  i := 1; j := s+1; k := 0;  
  while  (i <= s) and (j <= n) do 
  //Niezmiennik: a[1..k] - scalone podciągi b[1..i-1], a[s+1..j-1] 
  begin
    k := k+1;
    if b[i] <= a[j] then 
      begin a[k] := b[i]; i := i+1 end 
    else
      begin a[k] := a[j]; j := j+1 end 
end; 
//jeśli nie wyczerpaliśmy ciągu b, to przepisujemy go do tablicy a 
for j := i to  s do 
  begin k := k+1; a[k] := b[j] end 
end;

Przeanalizujmy złożoność algorytmu Merge-1. Dopóki nie wyczerpiemy jednego z podciągów \( a[s+1..n] \) lub \( b[1..s] \), po każdym porównaniu elementów \( b[i] \) z \( a[j] \) mniejszy z nich trafia na swoją docelową pozycję w tablicy \( a \). Zatem liczba porównań wynosi w pesymistycznym przypadku \( n-1 \). Niestety, oprócz porównań wielokrotnie przemieszczamy sortowane elementy. Wszystkich takich przemieszczeń mamy w pesymistycznym przypadku \( s+n \): przepisanie \( a[1..s] \) do \( b[1..s] \) plus umieszczenie każdego elementu na jego docelowej pozycji w tablicy a. Zatem przemieszczeń jest nie więcej niż \( 2n \).

Jeśli umiemy scalać, to możemy też sortować. Bardzo łatwo opisać taki algorytm rekurencyjnie. Jeśli sortowany ciąg składa się tylko z 1 elementu, to jest on oczywiście posortowany. Załóżmy zatem, że sortowany ciąg ma co najmniej 2 elementy. Dzielimy go na dwa podciągi złożone z kolejnych elementów. Sortujemy każdy z nich niezależnie rekurencyjnie, a potem scalamy. Oczywiście mamy wybór w podziale wyjściowego ciągu na dwa mniejsze, ale okazuje się, że najlepiej jest, gdy długości obu sortowanych podciągów różnią się co najwyżej o 1. Niech \( Merge(l,p,s) \) będzie procedurą scalającą posortowaną podtablicę \( a[l..s] \) z posortowaną podtablicą \( a[s+1..p] \), która w wyniku daje posortowaną podtablicę \( a[l..p] \).

Ćwiczenie 2
Przerób tak kod procedury Merge-1, żeby otrzymać procedurę Merge(l,p,s). Procedura Merge powinna wykonywać co najwyżej \( p-l \) porównań i co najwyżej \( s-l+1+p-l+1 \) przemieszczeń elementów.

Możemy teraz przystąpić do zapisu sortowania przez scalanie. Niech \( MS(l,p) \) będzie rekurencyjną procedurą sortującą tablicę \( a[l..p] \), którą to definiujemy następująco:

Algorytm Procedura_MS

  procedure MS(l,p); 
  begin 
    if l  <  p then 
      begin 
        s := (l+p) div 2; 
        MS(l,s); 
        MS(s+1,p); 
        Merge(l,p,s)  
      end 
end;

Sam algorytm sortowania przez scalanie \( MergeSort \) ma teraz postać:

Algorytm Sortowanie przez scalanie

algorytm MergeSort; 
begin 
  MS(1,n) 
end

Pesymistyczną liczbę porównań wykonywanych przez algorytm \( MergeSort \) można opisać za pomocą równania rekurencyjnego:

\( T(n) =\{ \begin{array}{ll} 0 & \mbox{dla } n = 1 \\ T(\lfloor \frac{n}{2} \rfloor) + T(\lceil \frac{n}{2} \rceil) + n-1 & \mbox{dla } n > 1 \end{array} . \)

Dokładne rozwiązanie tego równania daje \( T(n) \le n\lceil \log n \rceil \).

Ćwiczenie 3
Wykaż, że w algorytmie \( MergeSort \) nie wykonuje się więcej niż \( \frac{3}{2}n \lceil \log n \rceil \) przemieszczeń elementów. <

Ćwiczenie 4
Podaj przykład 8-elementowej permutacji liczb \( 1, 2, \ldots, 16 \), dla której algorytm MergeSort wykonuje jednocześnie największą liczbę porównań i największą liczbę przemieszczeń elementów.