W dniu 2012-11-24 15:53, PK pisze:
> On 2012-11-24, slawek <s...@h...pl> wrote:
>> Radix sort.
>
> Ale jesteś absolutnie pewien, że rozumiesz radix sort? Czy po prostu
> usłyszałeś od kogoś termin "non-comparative sorting" i myślisz, że jest
> tam schowane takie magiczne zaklęcie, które to robi?

Niedawno był to całkiem niezły watek o sortowaniu.
Sortowania pozycyjne tez były omówione;)

Ale w tym przypadku naiwna implementacja będzie zabójcza.
Losowy dostęp do dysku.

Jeśli podział jest na odcinki po 16 bitów, to dla
każdego (kazdy taki odcinek bedziemy zapisywać do
oddzielnego obszaru pliku) mamy bufor 16kB przy
2GBRAM. Mało.

16 bajtów -> 8 przebiegów zliczania i 8
przebiegów odczytywania + 8 zapisywania.

Gorzej niż w proponowanym alg z mergesort,
no, chyba, ze dane urosną do wielu terabajtów.


> Wiem, że to bardzo skomplikowane, więc powiem wolniej.
> Sortowanie polega na ustawianiu elementów w określonym porządku.
> Porządek definiuje zbiór i relacja. Relacja to operacja porównywania
> dwóch elementów zbioru.
> Bez porównywania nie da się stwierdzić, czy ciąg jest posortowany.
>
> Powiedz mi, czego konkretnie nie rozumiesz. Naprawdę chętnie Ci to
> wyjaśnię.

Ale posortować beż użycia > na elementach sortowanych się da;)
Pewnych specyficznych elementów, jak liczby naturalne.

pzdr
bartekltg