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:
>>> On 12.10.2012 18:28, Roman W wrote:
>>>> W dniu piątek, 12 października 2012 17:26:27 UTC+1 użytkownik
>>>> identyfikator: 20040501 napisał:
>>>>> sory za lameriadę, jaki algorytm sotrujący jest najprostszy w
>>>>> implementacji?
>>>>>
>>>>> nie musi być szybki...
>>>>
>>>> Bubble sort?
>>> Nie wiem sąd się wziął ten mit - sortowanie przez wybór (selection sort)
>>> jest znacznie prostsze w implementacji i bardziej intuicyjne.
>>
>> 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. (A przydała mi się więcej
> razy niż Cormen.)

Przecież chwalę. Patrząc na tę dyskusję brak bąbelków
można uznać jedynie za zaletę;)
Sam kupilem tą książkę jeszcze przed studiami,
trochę przez przypadek, a potem byłem z tego powodu
bardzo szczęśliwy;)


> Nie wiedzieć czemu w edukacji stosuje się bąble do nauczania na samym
> poczatku, mimo, że zasada działania jest świetnym przykładem "jak nie
> projektować algorytmów". A potem licealiści/studenci na pytanie o
> najprostszy algorytm sortowania odpowiadają "bąbelki"...

Przytargane z wiki:
http://www.cs.duke.edu/~ola/papers/bubble.pdf

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

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

Jeśli sortowalibyśmy listę, problem w ogóle znika.

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

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

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


> No i na jego
> podstawie powstało sortowanie Shella, które jest naprawdę ciekawym
> (aczkolwiek niepraktycznym) rozwiązaniem.

Wyścigi, kto znajdzie lepszą sekwencję długości skoków chyba
nadal trwają;)

pzdr
bartekltg