Algorytmy 5

Front

Jakie algorytmy sortujące działają w czasie liniowym?

Back

Sortowanie przez zliczanie (Counting Sort), sortowanie pozycyjne (Radix Sort) i sortowanie kubełkowe (Bucket Sort).

Front

Co to są algorytmy sortujące za pomocą porównań?

Back

Algorytmy, które porządkują elementy na podstawie wyników porównań między nimi.

Front

Jakie są dolne ograniczenia dla problemu sortowania?

Back

Dla algorytmów sortujących za pomocą porównań, dolne ograniczenie wynosi Ω(n log n).

Front

Jakie porównania są wykonywane w algorytmach sortujących za pomocą porównań?

Back

Porównania typu a_i < a_j, a_i ≤ a_j, a_i = a_j, a_i > a_j, a_i ≥ a_j.

Front

Co to jest drzewo decyzyjne w kontekście algorytmów sortujących?

Back

Drzewo decyzyjne przedstawia porównania wykonywane przez algorytm sortujący dla danych ustalonego rozmiaru.

Front

Jakie jest dolne ograniczenie na pesymistyczny czas sortowania?

Back

Długość najdłuższej ścieżki od korzenia drzewa decyzyjnego do liści odpowiada pesymistycznej liczbie porównań.

Front

Jakie są cechy algorytmu sortowania przez zliczanie?

Back

Działa w czasie liniowym, ale może sortować tylko liczby całkowite.

Front

Jak działa algorytm sortowania przez zliczanie?

Back

Polega na zliczaniu wystąpień każdej liczby w ciągu, a następnie tworzeniu nowego posortowanego ciągu.

Front

Jakie są wady algorytmu sortowania przez zliczanie?

Back

Wymaga tablicy o liczbie elementów równej największemu elementowi ciągu i może sortować tylko liczby całkowite.

Front

Co to jest sortowanie pozycyjne (Radix Sort)?

Back

Algorytm sortowania, który sortuje liczby na podstawie ich cyfr, zaczynając od najmniej znaczącej.