świstak.codes

O programowaniu, informatyce i matematyce przystępnym językiem

Sortowanie

Algorytmy-żarty, czyli o sortowaniu cz. 9

Świat algorytmów nie obraca się tylko wokół tworzenia i szukania optymalnych rozwiązań przydatnych problemów. Informatycy to wbrew pozorom też ludzie i lubią sobie czasem pożartować. Choćby w swoim stylu, tworząc zupełnie nikomu nieprzydatne algorytmy, które nie mają większego sensu, niekoniecznie działają tak, jak należy, czy rozwiązują totalnie nieistotne problemy. Dlatego tym razem zróbmy sobie przegląd takich algorytmicznych żartów, które mogłyby rozwiązać jeden z bardziej klasycznych problemów i jednocześnie szeroko omówiony na moim blogu — sortowanie.

Czytaj więcej

Sortowanie, cz. 7 — inne podejścia

W ciągu sześciu ostatnich artykułów o sortowaniu opisałem najbardziej znane podejścia do sortowania oraz kilka wywodzących się od nich. Algorytmów sortowania jest jednak bardzo wiele i nie byłem w stanie omówić wszystkich tych, które planowałem. W tym artykule opisuję trzy algorytmy, które miały znaleźć się wcześniej na blogu, jednak z różnych powodów odłożyłem je na później — sortowanie odd-even, gnoma oraz drzewiaste.

Czytaj więcej

Sortowanie, cz. 6 — teraz bez porównywania!

Przez ostatnie cztery artykuły poświęcone sortowaniu omawialiśmy sobie różne sposoby, w jaki sposób porównywać elementy, a następnie zamieniać, by odbyło się to z jak najmniejszą liczbą porównań, co też przekładać się miało na jak najszybszy czas wykonania algorytmu. Porównywanie elementów wydaje się być czymś całkowicie naturalnym, bo przecież jak możemy ustalić kolejność bez tego? Ano, można. I w tym artykule pokażę, jak to można zrobić.

Czytaj więcej

Sortowanie, cz. 5 — „dziel i zwyciężaj”

W poprzednich częściach serii opisywałem, w jaki sposób tworzyć algorytmy sortowania bazujące na tym, jak na co dzień sortujemy, oraz jak podejścia te można optymalizować. Jednak, jak mogłeś się przekonać, nie są to najszybsze rozwiązania, dlatego teraz przejdziemy do omawiania tych mniej oczywistych podejść do sortowania, które okazują się być wydajniejsze. Omówimy algorytmy, które bazują na metodzie „dziel i zwyciężaj”.

Czytaj więcej

Sortowanie, cz. 2 — sortowanie bąbelkowe

W poprzedniej, pierwszej części serii o sortowaniu opisałem teoretyczną część tego zagadnienia. Najwyższy czas przejść do praktyki. Nauczmy się najprostszego z algorytmów sortowania opartego o zamianę elementów — sortowania bąbelkowego, znanego też pod angielską nazwą bubble sort lub jako sortowanie przez zamianę. Jednak to nie wszystko. Będziemy go także krok po kroku optymalizować na tyle, na ile jest to w jego przypadku możliwe.

Czytaj więcej

Sortowanie, cz. 1 — wprowadzenie teoretyczne

Sortowanie — najpopularniejszy z podstawowych tematów informatyki i programowania. Podstawa każdego kursu, książki, serii wykładów itd., poświęconych algorytmice. Tak więc i tutaj nie mogło tego zabraknąć. Jednak nie będę tutaj rozpisywać kodu i omawiać, co się dzieje krok po kroku. Zamiast patrzeć na surowe implementacje, spróbujemy zrozumieć mechanizmy i jaki kryje się za nimi sens. Na samym początku jednak przybliżmy sobie teorię.

Czytaj więcej