On 12.10.2012 23:20, bartekltg wrote:
> W dniu 2012-10-12 21:08, Michoo pisze:
>> On 12.10.2012 19:28, bartekltg wrote:
>>> W dniu 2012-10-12 19:14, Michoo pisze:

>>> Chwytliwa nazwa. Sięgnąłem do ASD Diksa i spółki. Tam
>>> bąbelki prewencyjnie przemilczają;)
>> Ale to jest ogólnie całkiem niezła książka.
>
> Przecież chwalę.
> Patrząc na tę dyskusję brak bąbelków
> można uznać jedynie za zaletę;)

Chodziło mi właśnie o to, że "nie ma bo to jest dobra książka" ;)

>
>
>> Nie wiedzieć czemu w edukacji stosuje się bąble do nauczania na samym
>> poczatku, [...]
>
> Przytargane z wiki:
> http://www.cs.duke.edu/~ola/papers/bubble.pdf
Fajne.

>
>>>
>>> BTW, jakiś mały flejmik selectionsort vs insertionsort? ;>
>> Tu nie ma o czym dyskutować ;) - selectionsort jest najszybszy w
>> zapisaniu i najprostszy w wyjaśnieniu a poza przypadkami danych
>> częściowo (mocno) posortowanych szybszy od insertion.
>
>>
>> Insertion jest niezły jako kolejny krok do uczenia algorytmów - można
>> pokazać, ze coś co teoretycznie jest szybkie w praktyce po uwzględnieniu
>> kosztu operacji na rzeczywistej pamięci ma ukryty koszt.
>
> No i widzisz, już mamy pole do posprzeczania się:)
>
> Insertionsort jest w oczywisty sposób szybszy w sensie
> oczekiwanej liczby porównań (w select wyszukujemy maks
> wśród tablic długości n, n-1, n-2...4,3,2, w insert
> wkładamy zadany element w tablice długości 1,2..n-1,
> a średnio włożymy w połowę długości.

Zgadza się.

>
> Jeśli więc porównanie jest znacznie kosztowniejsze od
> przesunięcia, wolimy mieć dwa razy mniej porównań,
> nawet kosztem dodatkowych ~n^2 przesunięć.

Widziałem nawet takie rozważanie gdzie wyszukiwanie w części
posortowanej było robione przeszukiwaniem binarnym, a wstawianie było w
czasie stałym - dostajemy złożoność insertion sort n*log(n) ;)


>
> Jeśli sortowalibyśmy listę, problem w ogóle znika.
Lista musi być na tyle duża, że nie możemy jej skopiować do struktury o
dostępie swobodnym, ale jest to naciągane, bo przy złożoności n^2
prawdopodobnie taniej będzie przenieść listę na pamięć zewnętrzną,
zwolnić, wczytać do tablicy, posortować jakimś q/heap sortem, zapisać na
pamięć zewnętrzną, zwolnić, wczytać do listy ;)

>
> A czasem o wyborze może zadecydować stabilność sortowania.

Jeżeli dobrze widzę to i insertion i selection może być stabilny.

>
> Tak więc ja bym nie był tak pewny odpowiedzi:)
>
> A poważnie, z tą pamięcią to ciekawy problem.
> Jeśli już mamy całość w cache (nie rozważamy
> przecież na serio sortowania dużych tablic)
> ale jednocześnie porównanie jest tanie (inty).

> Żeby nie był to problem czysto akademicki,
> niech to będzie 'końcówka qsorta'. Wtedy wywoływany
> obszar i tak już najpewniej jest pod ręką.

Ale w takiej sytuacji jest heapsort działający zawsze w n*log(n) ;)

>
> Heh, możnaby jakimś studentom zadać;)

Wygrzebałem stare sprawozdanie na "algorytmy i struktury danych".
Najszybszym algorytmem dla losowych danych był wtedy heapsort napisany w
assemblerze (ale miałem na jego optymalizację dobre 3 godziny podczas
jazdy pociągiem). Największym zaskoczeniem był Shell:
http://grota.be/~michoo/smieci/algo_sort.png


--
Pozdrawiam
Michoo