A
indeksowanej od 0
do n-1
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).
Stabilne algorytmy sortowania utrzymują kolejność występowania elementów o tej samej wartości taką jak w wejściowym ciągu.
\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}
\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}
\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}
\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}
\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}
\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}
\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}
\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}
\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}
\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}