-
Data: 2012-10-13 11:39:21
Temat: Re: sortowanie
Od: Michoo <m...@v...pl> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]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
Następne wpisy z tego wątku
- 13.10.12 13:52 Michoo
- 13.10.12 14:14 bartekltg
- 13.10.12 14:16 PK
- 13.10.12 14:27 PK
- 13.10.12 14:46 Edek Pienkowski
- 13.10.12 14:49 Edek Pienkowski
- 13.10.12 15:13 bartekltg
- 13.10.12 15:13 PK
- 13.10.12 15:26 kenobi
- 13.10.12 15:32 Edek Pienkowski
- 13.10.12 15:36 Edek Pienkowski
- 13.10.12 15:39 bartekltg
- 13.10.12 15:53 kenobi
- 13.10.12 15:58 PK
- 13.10.12 15:58 identyfikator: 20040501
Najnowsze wątki z tej grupy
- Arch. Prog. Nieuprzywilejowanych w pełnej wer. na nowej s. WWW energokod.pl
- 7. Raport Totaliztyczny: Sprawa Qt Group wer. 424
- TCL - problem z escape ostatniego \ w nawiasach {}
- Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- testy-wyd-sort - Podsumowanie
- Tworzenie Programów Nieuprzywilejowanych Opartych Na Wtyczkach
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
Najnowsze wątki
- 2024-12-23 Riga => Specjalista ds. public relations <=
- 2024-12-23 Łódź => Specjalista ds. Sprzedaży <=
- 2024-12-23 Kraków => International Freight Forwarder <=
- 2024-12-23 Co nalezy do Cinkciarza, a co do Conotoxia ?
- 2024-12-23 Poznań => Key Account Manager <=
- 2024-12-23 Warszawa => Presales / Inżynier Wsparcia Technicznego IT <=
- 2024-12-23 Rzeszów => Spedytor Międzynarodowy <=
- 2024-12-23 Warszawa => Infrastructure Automation Engineer <=
- 2024-12-23 Białystok => Analityk w dziale Trade Development (doświadczenie z Po
- 2024-12-23 Warszawa => Site Reliability Engineer (SRE) <=
- 2024-12-23 Warszawa => DevOps Engineer <=
- 2024-12-23 Warszawa => Senior Account Manager <=
- 2024-12-23 Katowice => Regionalny Kierownik Sprzedaży (OZE) <=
- 2024-12-23 Katowice => Administrator IT - Wirtualizacja i Konteneryzacja <=
- 2024-12-23 Mińsk Mazowiecki => Spedytor Międzynarodowy <=