• Tomasz Żok
• Home
• Publications
• Conferences
• Projects

Problem sortowania

Definicja

• Wejście: ciąg liczb a_1, a_2, \ldots, a_n
• Wyjście: permutacja a_1', a_2', \ldots, a_n' taka, że a_1' \leq a_2' \leq \ldots \leq a_n'
• W dalszych przykładach dane będą w tablicy A indeksowanej od 0 do n-1

Przykład

• Wejście: 4, 2, 0, 1, 3
• Wyjście: 0, 1, 2, 3, 4

Cechy algorytmów

Sortowanie w miejscu

Algorytm sortuje tablicę A w miejscu jeżeli wszystkie elementy przechowywane są tylko w tablicy A za wyjątkiem stałej liczby elementów (np. w zmiennych).

Stabilność

Stabilne algorytmy sortowania utrzymują kolejność występowania elementów o tej samej wartości taką jak w wejściowym ciągu.

Selection Sort

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{SelectionSort}{$ A, n $}
    \FOR {$ i \gets 0 $ \TO $ n - 1 $}
        \STATE {$ j \gets $} \CALL{ArgMin}{$ A, i, n - 1 $}
        \STATE \CALL{Swap}{$ A, i, j $}
    \ENDFOR
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{ArgMin}{$ A, begin, end $}
    \STATE {$ argmin \gets begin $}
    \FOR {$ i \gets begin + 1 $ \TO $ end $}
        \IF {$ A[i] < A[argmin] $}
            \STATE {$ argmin \gets i $}
        \ENDIF
    \ENDFOR
    \RETURN {$ argmin $}
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{Swap}{$ A, i, j $}
    \STATE {$ tmp \gets A[i] $}
    \STATE {$ A[i] \gets A[j] $}
    \STATE {$ A[j] \gets tmp $}
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

Bubble Sort

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{BubbleSort}{$ A, n $}
    \FOR {$ i \gets 0 $ \TO $ n - 1 $}
        \FOR {$ j \gets n - 1 $ \DOWNTO $ i + 1 $}
            \IF {$ A[j] < A[j - 1] $}
                \STATE \CALL{Swap}{$ A, j, j-1 $}
            \ENDIF
        \ENDFOR
    \ENDFOR
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

Insertion Sort

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{InsertionSort}{$ A, n $}
    \FOR {$ j \gets 1 $ \TO $ n - 1 $}
        \STATE {$ key \gets A[j] $}
        \STATE {$ i \gets j - 1 $}
        \WHILE {$ i \geq 0 $ \AND $ A[i] > key $}
            \STATE {$ A[i + 1] \gets A[i] $}
            \STATE {$ i \gets i - 1 $}
        \ENDWHILE
        \STATE {$ A[i + 1] \gets key $}
    \ENDFOR
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

Shell Sort

• W tym algorytmie oprócz tablicy A mamy jeszcze dodatkowy parametr H
• H to tablica składająca się z t liczb naturalnych, a pierwsza wartość H[0] = 1
• Dobór wartości w tablicy H znacząco wpływa na działanie algorytmu ShellSort
• Można zastosować stałą zawartość tablicy H np. [1, 2, 4, 8], jednak lepiej gdy zawartość tablicy zależna jest od n tj. od liczby elementów do posortowania
• Przykładowy sposób generowania tablicy H przedstawiony jako ShellSortIncrements wypełnia tablicę wartościami zgodnie z następującym ciągiem liczbowym:
  \begin{array}{l} h_0 = 1 \\ h_i = 3h_{i-1} + 1 \end{array}
• Ustawiając w ShellSortIncrements wielkość tablicy H na 20 jesteśmy w stanie sortować ok. 5 miliardów elementów, ponieważ wartość ciągu h_{20} \approx 5 \cdot 10^9

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{ShellSort}{$ A, n, H, t $}
    \FOR {$ s \gets t - 1 $ \DOWNTO $ 0 $}
        \STATE {$ h \gets H[s] $}
        \FOR {$ j \gets h $ \TO $ n -1 $}
            \STATE {$ key \gets A[j] $}
            \STATE {$ i \gets j - h $}
            \WHILE {$ i \geq 0 $ \AND $ A[i] > key $}
                \STATE {$ A[i + h] \gets A[i] $}
                \STATE {$ i \gets i - h $}
            \ENDWHILE
            \STATE {$ A[i + h] \gets key $}
        \ENDFOR
    \ENDFOR
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{ShellSortIncrements}{$ n $}
    \STATE {$ tmp \gets \emptyset $} \COMMENT {tablica o rozmiarze 20}
    \STATE {$ h \gets 1 $}
    \STATE {$ i \gets 0 $}
    \WHILE {$ h < n $}
        \STATE {$ tmp[i] \gets h $}
        \STATE {$ h \gets 3h + 1 $}
        \STATE {$ i \gets i + 1 $}
    \ENDWHILE
    \STATE {$ H \gets \emptyset $} \COMMENT {tablica o rozmiarze $ i $}
    \FOR {$ t \gets 0 $ \TO $ i - 1 $}
        \STATE {$ H[t] \gets tmp[i - t - 1] $}
    \ENDFOR
    \RETURN $ H $
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Quick Sort

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{QuickSort}{$ A, p, r $}
    \IF {$ p < r $}
        \STATE {$ q \gets $} \CALL{Partition}{$ A, p, r $}
        \STATE \CALL{QuickSort}{$ A, p, q - 1 $}
        \STATE \CALL{QuickSort}{$ A, q + 1, r $}
    \ENDIF
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Partition}{$ A, p, r $}
    \STATE {$ x \gets A[r] $}
    \STATE {$ i \gets p - 1 $}
    \FOR {$ j \gets p $ \TO $ r $}
        \IF {$ A[j] \leq x $}
            \STATE {$ i \gets i + 1 $}
            \STATE \CALL{Swap}{$ A, i, j $}
        \ENDIF
    \ENDFOR
    \STATE {$ i \gets i + 1 $}
    \STATE \CALL{Swap}{$ A, i, r $}
    \RETURN {$ i $}
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Randomized Quick Sort

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{RandomizedQuickSort}{$ A, p, r $}
    \IF {$ p < r $}
        \STATE {$ q \gets $} \CALL{RandomizedPartition}{$ A, p, r $}
        \STATE \CALL{RandomizedQuickSort}{$ A, p, q - 1 $}
        \STATE \CALL{RandomizedQuickSort}{$ A, q + 1, r $}
    \ENDIF
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{RandomizedPartition}{$ A, p, r $}
    \STATE {$ i \gets $} \CALL{Random}{$ p, r $}
    \STATE \CALL{Swap}{$ A, i, r $}
    \RETURN \CALL{Partition}{$ A, p, r $}
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Heap Sort

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{HeapSort}{$ A, n $}
    \STATE \CALL{BuildMaxHeap}{$ A, n $}
    \FOR {$ i \gets n - 1 $ \DOWNTO $ 1 $}
        \STATE \CALL{Swap}{$ A, 0, i $}
        \STATE \CALL{MaxHeapify}{$ A, 0, i $}
    \ENDFOR
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{BuildMaxHeap}{$ A, n $}
    \FOR {$ i \gets \dfrac{n}{2} $ \DOWNTO $ 0 $}
        \STATE \CALL{MaxHeapify}{$ A, i, n $}
    \ENDFOR
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{MaxHeapify}{$ A, i, n $}
    \STATE {$ l \gets $} \CALL{Left}{$ i $}
    \STATE {$ r \gets $} \CALL{Right}{$ i $}
    \STATE {$ largest \gets i $}
    \IF {$ l < n $ \AND $ A[l] > A[largest] $}
        \STATE {$ largest \gets l $}
    \ENDIF
    \IF {$ r < n $ \AND $ A[r] > A[largest] $}
        \STATE {$ largest \gets r $}
    \ENDIF
    \IF {$ largest \neq i $}
        \STATE \CALL{Swap}{$ A, i, largest $}
        \STATE \CALL{MaxHeapify}{$ A, largest, n $}
    \ENDIF
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Left}{$ i $}
    \RETURN {$ 2i + 1 $}
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Right}{$ i $}
    \RETURN {$ 2i + 2 $}
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Merge Sort

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{MergeSort}{$ A, p, r $}
    \IF {$ p < r $}
        \STATE {$ q \gets \dfrac{p + r}{2} $}
        \STATE \CALL{MergeSort}{$ A, p, q $}
        \STATE \CALL{MergeSort}{$ A, q + 1, r $}
        \STATE \CALL{Merge}{$ A, p, q, r $}
    \ENDIF
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{Merge}{$ A, p, q, r $}
    \STATE {$ n_1 \gets q - p + 1 $}
    \STATE {$ n_2 \gets r - q $}
    \STATE {$ L \gets \emptyset $} \COMMENT {tablica o rozmiarze $ n_1 + 1 $}
    \STATE {$ R \gets \emptyset $} \COMMENT {tablica o rozmiarze $ n_2 + 1 $}
    \FOR {$ i \gets 0 $ \TO $ n_1 - 1 $}
        \STATE {$ L[i] \gets A[p + i - 1] $}
    \ENDFOR
    \FOR {$ j \gets 0 $ \TO $ n_2 - 1 $}
        \STATE {$ R[i] \gets A[q + j] $}
    \ENDFOR
    \STATE {$ L[n_1] \gets \infty $}
    \STATE {$ R[n_2] \gets \infty $}
    \STATE {$ i \gets 1 $}
    \STATE {$ j \gets 1 $}
    \FOR {$ k \gets p $ \TO $ r $}
        \IF {$ L[i] \leq R[j] $}
            \STATE {$ A[k] \gets L[i] $}
            \STATE {$ i \gets i + 1 $}
        \ELSE
            \STATE {$ A[k] \gets R[j] $}
            \STATE {$ j \gets j + 1 $}
        \ENDIF
    \ENDFOR
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

Counting Sort

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{CountingSort}{$ A, B, k $}
    \STATE {$ C \gets \emptyset $} \COMMENT {tablica o rozmiarze $ k $}
    \FOR {$ i \gets 0 $ \TO $ k $}
        \STATE {$ C[i] \gets 0 $}
    \ENDFOR
    \FOR {$ j \gets 0 $ \TO $ n - 1 $}
        \STATE {$ C[A[j]] \gets C[A[j]] + 1 $}
    \ENDFOR
    \FOR {$ i \gets 1 $ \TO $ k $}
        \STATE {$ C[i] \gets C[i] + C[i-1] $}
    \ENDFOR
    \FOR {$ j \gets n -1 $ \DOWNTO $ 0 $}
        \STATE {$ B[C[A[j]]] \gets A[j] $}
        \STATE {$ C[A[j]] \gets C[A[j]] - 1 $}
    \ENDFOR
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

Generatory instancji

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{FillRandom}{$ A, n $}
    \FOR {$ i \gets 0 $ \TO $ n  $}
        \STATE {$ A[i] \gets $ \CALL{RandomNumber}{}}
    \ENDFOR
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{FillIncreasing}{$ A, n $}
    \FOR {$ i \gets 0 $ \TO $ n  $}
        \STATE {$ A[i] \gets i $}
    \ENDFOR
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{FillDecreasing}{$ A, n $}
    \FOR {$ i \gets 0 $ \TO $ n  $}
        \STATE {$ A[i] \gets -i $}
    \ENDFOR
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{FillVShaped}{$ A, n $}
    \STATE {$ i \gets 0 $}
    \STATE {$ j \gets n - 1 $}
    \STATE {$ k \gets 0 $}

    \WHILE {$ i < j$}
        \STATE {$ A[i] \gets k $}
        \STATE {$ A[j] \gets k - 1 $}
        \STATE {$ i \gets i + 1 $}
        \STATE {$ j \gets j - 1 $}
        \STATE {$ k \gets k - 2 $}
    \ENDWHILE

    \IF {$ i = j $}
        \STATE {$ A[i] \gets k $}
    \ENDIF
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

Treść zadania

• Poniżej znajdują się wymagania na określoną ocenę
• Każdy wyższy próg wymaga spełnienia założeń z niższych progów (na ocenę 5.0 trzeba spełnić wszystkie)
• Należy wykonać eksperymenty obliczeniowe i przygotować sprawozdanie:
  • Dla każdego generatora instancji i każdego algorytmu należy zmierzyć czas działania w zależności od wielkości instancji
  • W sprawozdaniu muszą znaleźć się tabele oraz wykresy pokazujące zmierzone wartości
  • W sprawozdaniu należy również umieścić wnioski z analizy np. czy dla danego rozkładu danych określony algorytm działa szybciej/wolniej i z czego to wynika
• Na oceny 3.0, 3.5 i 4.0 w sprawozdaniu powinny się znaleźć 4 wykresy (po jednym na każdy rodzaj danych wejściowych)
• Na oceny 4.5 i 5.0 wymagane są dodatkowe 4 wykresy pokazujące czas działania tylko dla RandomizedQuickSort i HeapSort

Na ocenę 3.0

• Zaimplementuj generatory instancji:
  • Wartości losowe
  • Wartości rosnące
  • Wartości malejące
  • Rozkład V-kształtny
• Zaimplementuj algorytm SelectionSort

Na ocenę 3.5

• Zaimplementuj algorytm InsertionSort

Na ocenę 4.0

• Zaimplementuj algorytm QuickSort

Na ocenę 4.5

• Zaimplementuj algorytm RandomizedQuickSort

Na ocenę 5.0

• Zaimplementuj algorytm HeapSort

Przykładowy wykres

• Prawidłowy wykres ma: tytuł, opisane obie osie (wraz z jednostką gdzie to jest stosowne) oraz legendę