Algorytmy 4

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

Jakie są dolne ograniczenia dla problemu sortowania za pomocą porównań?

Back

Dolne ograniczenia dla algorytmów sortujących za pomocą porównań wynoszą Ω(n log n).

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 są cechy algorytmu sortowania przez zliczanie?

Back

Działa w czasie liniowym i może sortować wyłącznie liczby całkowite.

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

Jakie są kroki algorytmu sortowania przez zliczanie?

Back

1. Zliczanie wystąpień elementów. 2. Tworzenie tablicy wynikowej na podstawie zliczeń.

Front

Co to jest sortowanie pozycyjne (RadixSort)?

Back

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

Front

Jakie są etapy algorytmu RadixSort?

Back

1. Rozrzucanie liczb do kubełków na podstawie k-tej cyfry. 2. Łączenie kubełków w jeden ciąg.

Front

Jakie są zalety algorytmu RadixSort?

Back

Jest stabilny i może sortować liczby o różnej długości.

Front

Jakie są cechy algorytmu sortowania kubełkowego (BucketSort)?

Back

Dzieli przedział na kubełki, do których wkłada elementy, a następnie sortuje zawartość kubełków.