Nr 01 · Słownik · Teoria informatyki · Algorytmy i struktury danych

Sortowanie i wyszukiwanie

16 pojęć w 9 podgrupach, z prostymi definicjami i źródłami.

Granice sortowania · 1

Podstawy sortowania · 2

  • 01klucz sortowaniaAtrybut rekordu, wg którego wyznaczany jest porządek elementów podczas sortowania lub identyfikacja przy wyszukiwaniu.
  • 02sortowanieUporządkowanie elementów zbioru wedle relacji liniowego porządku zdefiniowanej na kluczach, dające ciąg niemalejący lub nierosnący.

Podstawy wyszukiwania · 1

  • 01wyszukiwanieLokalizacja elementu o zadanym kluczu w strukturze danych lub stwierdzenie jego nieobecności.

Sortowanie bezporownaniowe · 2

  • 01sortowanie pozycyjneradix sortAlgorytm liniowy sortujący klucze cyfra po cyfrze przy użyciu stabilnego sortowania pomocniczego, bez porównań między kluczami.
  • 02sortowanie przez zliczaniecounting sortAlgorytm liniowy zliczający wystąpienia kluczy z ograniczonego zakresu całkowitego i rozmieszczający elementy wg sum prefiksowych.

Sortowanie porownawcze · 5

  • 01element osiowypivotWyróżniony element, względem którego algorytm partycjonuje ciąg na część mniejszą i większą, np. w sortowaniu szybkim.
  • 02partycjonowaniePrzestawienie elementów ciągu wokół elementu osiowego tak, by poprzedzające były odeń niewiększe, a następujące niemniejsze.
  • 03sortowanie przez kopcowanieheapsortAlgorytm sortowania budujący kopiec binarny i kolejno usuwający korzeń, dający porządek w miejscu w czasie n log n.
  • 04sortowanie przez scalaniemerge sortAlgorytm sortowania typu dziel-i-zwyciężaj, rekurencyjnie dzielący ciąg i scalający posortowane połowy; czas n log n.
  • 05sortowanie szybkiequicksortAlgorytm sortowania dzielący ciąg względem elementu osiowego na części mniejsze i większe; średni czas n log n, pesymistyczny n².

Statystyki pozycyjne · 1

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

Wlasnosci sortowania · 2

  • 01sortowanie stabilneWłasność algorytmu sortowania zachowująca względną kolejność elementów o równych kluczach z wejścia.
  • 02sortowanie w miejscuin-placeWłasność algorytmu sortującego dane przy stałej, niezależnej od rozmiaru wejścia, dodatkowej pamięci pomocniczej.

Wyszukiwanie haszowe · 1

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

Wyszukiwanie w ciagu · 1

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

Pozostałe grupy — Algorytmy i struktury danych

Grupa pojęć · Algorytmy i struktury danych16 haseł