W dniu 2012-10-14 14:09, kenobi pisze:

>>
>
> hehe, uzywam wielu nazw, sam kasperski

Nazwy są po to, aby komunikować się z innymi.
Jeśli nazwa nie dekoduje się u rozmówcy,
nie jest nic warta.

> nazywa to sortowaniem liniowym, (mozna tez
> mowic sortowanie przez histogram itp)

A można mówić magic harry potter sort. Tylko po co.


> nie jestem pewien zreszta czy ten counting
> sort to zupelnie to samo; zliczac mozna

To samo.
http://city17.ca/out.of.print.book.pdf
Tylko gośc zupełnie poważnie mówi o gigabajtach
RAMu sortując inty.

> roznie a to jest specjalny sposob na
> gruncie kodu - wcale nie twierdze ze to jest
> unikalny sposob kasperskiego jest to jednak
> jedna z nie bardzo znanych metod gdy tymczasem
> daje ona kopa w dpe wszystkim innym algorytmom

Jest to jeden z najpowszechniej znanych algorytmów,
jest w każdej książce do "ASD" i uczą go na każdym
kursie 'algorytmiki'.

Jest bardzo ważnym przykładem, bo mówimy 'Sortując
przez porównania nie da się zejść poniżej log_2 (n!)
~ n log[n] porównań. Dowód:[...] Ale jeśli posortujemy
inaczej, nie porównując par elementów, to ograniczenie
nas nie dotyczy, zobaczcie: [i to countsort]'.

BTW. Sortowanie przez porównanie działa na dowolnych
obiektach. Sortowanie przez zliczanie/pozycyjne
potrzebuje tym więcej przebiegów, im dłuższe w zapisie
bitowym są dane. Ostatecznie, jeśli sortujemy n liczb
z zakresu np 0-100n, zlozonośc asymptotyczna spowrotem
jest n log[n]. W przyrodzie nic nie ginie;)


Korzyść i przyspieszenie wynika z tego, że dane
spałniają pewną własność. Tutaj, mają mały zakres.
podobnie, jeśli potrafimy powiedzieć coś o ich,
rozkładzie, potrafimy sortowac liniowo (w sensie czasu
oczekiwanego) za pomocą kubełków.



BTW Obstwiałbym, że więcej osób zna to sortowanie przez
zliczanie niż postać Kaspersiego.

pzdr
bartekltg