Dlaczego Java nie używa sortowania radix na operacjach podstawowych?

java.util.Arrays.sort(/* int[], char[], short[], byte[], boolean[] */) jest zaimplementowany jako „zestrojony szybki sortowanie” zamiast sortowania radix.

Jakiś czas temu porównałem prędkość i przy czymś takim jak n> 10000 sortowanie radix było zawsze szybsze. dlaczego?

Spekulowałbym, że:

• Array.sort jest implementowany jako quicksort, ponieważ quicksort może sortować wszystko w przyzwoitym czasie, biorąc pod uwagę komparator.
• Sortowanie listy 10000 pozycji nie jest tak powszechne. Dostęp do struktury danych zawierającej 10000 lub więcej elementów jest dość powszechny. Jeśli potrzebujesz zachować porządek, zrównoważone drzewo wyszukiwania jest często lepszym sposobem niż posortowanie całej tablicy za każdym razem, gdy potrzebujesz najmniejszego elementu.
• Sortowanie prymitywów nie jest tak powszechne, pomimo tego, czego uniwersytet może uczyć.

Chodzi o to, że nie jest to tak częsty przypadek użycia, że ​​jego optymalizacja musi znajdować się w standardowej bibliotece. Jeśli napisałeś aplikację, która ma problemy z wydajnością, w której określasz poprzez profilowanie, że sortowanie tablicy ponad 10000 ints jest faktycznie wąskim gardłem, możesz równie dobrze napisać sortowanie ręcznie lub ponownie rozważyć wybór struktury danych w pierwszej kolejności miejsce.

Back2dos powiedział wszystko, postaram się tylko wyjaśnić punkt, który moim zdaniem jest najważniejszy:

Sortowanie Radix może sortować tylko rzeczywiste wartości pierwotne zawarte w tablicy na podstawie ich wzorców cyfr binarnych. W rzeczywistych scenariuszach inżynierii oprogramowania taki przypadek występuje prawie nigdy . O wiele częściej robimy to sortując tablice bardziej złożonych (nieprymitywnych) struktur danych, a czasami sortujemy tablice indeksów do innych bytów.

Teraz tablica indeksów dla innych jednostek jest w rzeczywistości tablicą operacji podstawowych, ale porządek sortowania zapewnia interfejs komparatora (i / lub delegacja w języku C #), który nie porównuje indeksów, ale jednostki indeksowane przez indeksy. Zatem porządek sortowania nie ma absolutnie żadnego związku z porządkiem wartości prymitywów, a zatem sortowanie radix jest absolutnie bezużyteczne w tym scenariuszu.

Przykład:

Mamy tablicę ciągów: [0] = "Mike", [1] = "Albert", [2] = "Zoro". Następnie deklarujemy tablicę indeksów do tych ciągów: [0] = 0, [1] = 1, [2] = 2. Następnie sortujemy tablicę indeksów, przekazując jej komparator, który nie porównuje samych indeksów, ale rzeczywiste ciągi, do których odwołują się te indeksy. Po posortowaniu wynikowa tablica indeksów będzie wyglądać następująco: [0] = 1, [1] = 0, [2] = 2. Jak widać, ta kolejność sortowania nie ma nic wspólnego z binarnymi wzorcami wartości zawartych w tablicy, a jednak przechodząc przez tę tablicę indeksów i pobierając każdy odpowiedni ciąg, odwiedzamy ciągi w posortowanej kolejności.