Interaktivní vizualizace a porovnání výkonu.
Popisuje horní mez časové nebo paměťové náročnosti. Určuje, jak roste potřebný čas při zvětšení vstupních dat.
Časová složitost: Počet porovnání a prohození. Měří se Worst Case (O) a Best Case (Ω).
Prostorová složitost: Potřeba paměti navíc. In-Place algoritmy jako Bubble nebo Select mají O(1). Merge Sort potřebuje nová pole, takže má O(n).
| Algoritmus | Best Case (Ω) | Average Case (Θ) | Worst Case (O) | Space (Paměť) |
|---|---|---|---|---|
| Bubble Sort | Ω(n) | Θ(n2) | O(n2) | O(1) |
| Selection Sort | Ω(n2) | Θ(n2) | O(n2) | O(1) |
| Insertion Sort | Ω(n) | Θ(n2) | O(n2) | O(1) |
| Quick Sort | Ω(n log n) | Θ(n log n) | O(n2) | O(log n) |
| Merge Sort | Ω(n log n) | Θ(n log n) | O(n log n) | O(n) |
procedure bubbleSort(A):
n = length(A)
for i from 0 to n-1:
for j from 0 to n-i-1:
if A[j] > A[j+1]:
swap(A[j], A[j+1])
procedure selectionSort(A):
for i from 0 to n-1:
min = i
for j from i+1 to n:
if A[j] < A[min]:
min = j
swap(A[i], A[min])
procedure insertionSort(A):
for i from 1 to n-1:
key = A[i]
j = i - 1
while j >= 0 and A[j] > key:
A[j+1] = A[j]
j = j - 1
A[j+1] = key
procedure quickSort(A, low, high):
if low < high:
pi = partition(A, low, high)
quickSort(A, low, pi-1)
quickSort(A, pi+1, high)
procedure mergeSort(A): if length(A) <= 1: return A mid = length(A) / 2 L = mergeSort(A[0..mid]) R = mergeSort(A[mid..end]) return merge(L, R)