Sortowanie kubełkowe a sortowanie szybkie - java, sortowanie, stream, quicksort, bucket-sort

Pytanie ogólne: Dlaczego sortowanie kubełkowe jest bardziej korzystne niż szybkie sortowanie?

Powiedzmy, że liczby przychodzą ze strumienia, a moje segmenty są podobne (1,10) (11,20) itd.

Następnie sortuję wiadra, a następnie łączę je, posortowując numery.

LUB

Mogę umieścić je w tablicy, a następnie posortować za pomocą Quicksort

Sortowanie segmentów: najgorszy przypadek O (N + K) (N ^ 2); Quicksort: Bestcase O (1) Averagecase O (nlogn) worstcase (N ^ 2);

Dlaczego więc używamy sortowania kubełkowego do rzeczy takich jak strumienie przychodzących liczb całkowitych, które chcemy posortować? Czy to dlatego, że możemy podejmować decyzje w oparciu o liczbę całkowitą w każdym z twoich koszyków?

Dzięki

Odpowiedzi:

Jeśli znamy k z przodu, a jest ono małe (k << n)wtedy sortowanie kubełkowe może wydajnie działać szybciej niż Quicksort, ponieważ n * log (n), średnia dla Quicksort, będzie większa niż (n + k), co jest średnią dla sortowania kubełkowego.

To znaczy.,

sortedList = (n*log(n) > n + k) ? bucketSort(list) : quicksort(list);

Powodem, dla którego może być używany do strumieni, jest tosortowanie kubełkowe jest na miejscu. Możesz utrzymywać posortowaną listę, wydajnie dodając nowe elementy bez konieczności ponownego sortowania za każdym razem. Po prostu manipulujesz strukturą danych (segmentem) bezpośrednio i to wszystko.

Z drugiej strony Quicksort nie jest na miejscu i wymaga pełnego uruchomienia sortowania, aby zwrócić posortowaną listę.