Sortowanie i wyszukiwanie

Dowodzony przez drzewo decyzyjne minimalny pesymistyczny koszt Ω(n log n) dla algorytmów sortujących wyłącznie przez porównania kluczy.

Atrybut rekordu, wg którego wyznaczany jest porządek elementów podczas sortowania lub identyfikacja przy wyszukiwaniu.

Uporządkowanie elementów zbioru wedle relacji liniowego porządku zdefiniowanej na kluczach, dające ciąg niemalejący lub nierosnący.

Lokalizacja elementu o zadanym kluczu w strukturze danych lub stwierdzenie jego nieobecności.

Algorytm liniowy sortujący klucze cyfra po cyfrze przy użyciu stabilnego sortowania pomocniczego, bez porównań między kluczami.

Algorytm liniowy zliczający wystąpienia kluczy z ograniczonego zakresu całkowitego i rozmieszczający elementy wg sum prefiksowych.

Wyróżniony element, względem którego algorytm partycjonuje ciąg na część mniejszą i większą, np. w sortowaniu szybkim.

Przestawienie elementów ciągu wokół elementu osiowego tak, by poprzedzające były odeń niewiększe, a następujące niemniejsze.

Algorytm sortowania budujący kopiec binarny i kolejno usuwający korzeń, dający porządek w miejscu w czasie n log n.

Algorytm sortowania typu dziel-i-zwyciężaj, rekurencyjnie dzielący ciąg i scalający posortowane połowy; czas n log n.

Algorytm sortowania dzielący ciąg względem elementu osiowego na części mniejsze i większe; średni czas n log n, pesymistyczny n².

i-ty co do wielkości element zbioru; szczególne przypadki to minimum, maksimum i mediana.

Własność algorytmu sortowania zachowująca względną kolejność elementów o równych kluczach z wejścia.

Własność algorytmu sortującego dane przy stałej, niezależnej od rozmiaru wejścia, dodatkowej pamięci pomocniczej.

Odwzorowanie kluczy w indeksy tablicy przez funkcję skrótu, umożliwiające wyszukiwanie i wstawianie w średnim czasie stałym.

Metoda wyszukiwania w uporządkowanym ciągu, połowiąca przedział poszukiwań przy każdym porównaniu; działa w czasie logarytmicznym.