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?

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ę.

> Nie. Nie ma żadnych danych.

To albo coś o możliwych danych zakładasz albo rozwiązujesz problem
w ogólnym przypadku. Ogólnie jest to sortowanie.

> Patrz wyżej - na link. Sam nie wiedziałem, że to ma jakieś praktyczne
> znaczenie. A jednak: ma.

Oczywiście że ma. Sam zajmuję się tym na co dzień. Chodzi o to, że
do Twojego problemu istnieje fundamentalne ograniczenie matematyczne.
Patrzysz na skomplikowany przypadek, więc wydaje Ci się, że coś
stworzysz. Mam zatem prostszy wariant. Daję Ci 2 liczby: {a,b}.
Zaproponuj sposób na sprawdzenie (na komputerze klasycznym), czy a=b
bez używania relacji "=". Będziesz tego potrzebował, jeśli chcesz
rozwiązać swój problem tak, jak to sobie wymarzyłeś.

Wszystkie metody, o których piszesz, są przybliżone. Dokładnie tak
jak w publikacji, której pierwsze zdanie tu zacytowałem.

pozdrawiam,
PK