Autor: Tomasz Świstak

W poprzednim artykule pokazałem, jaka algorytmika stoi za rysowaniem linii na ekranie. Zaczęliśmy od znanego wszystkim wzoru na funkcję liniową, aby przejść do optymalnego algorytmu, który na pierwszy rzut oka nie ma z nim nic wspólnego. Tym razem chciałbym kontynuować tematykę grafiki komputerowej i pokazać, jaka algorytmika stoi tym razem za rysowaniem okręgów.

Korzystając na co dzień z komputera, jeżeli zastanawiamy się, jak on działa, to myślimy albo o tym, jakie algorytmy wykorzystują jakieś skomplikowane aplikacje, albo jakie rozwiązania użyto do ich stworzenia, albo, tak z innej strony, jak to wszystko działa na poziomie sprzętu. Jednak rzadziej się zastanawiamy nad rzeczami, które po prostu się dzieją, otaczają nas bez przerwy i nie są spektakularne, a jednak proces, jak to się dzieje, sam w sobie może być całkiem ciekawy. Dlatego dziś opowiedzmy sobie o tym, jaka algorytmika stoi za rysowaniem na ekranie, a dokładniej — rysowaniem linii (odcinków).

Z mojego poprzedniego artykułu wiemy już czym jest rekurencja, rekursja ogonowa oraz jak je stosujemy. Jednak temat rekurencji jest dość rozległy i warto opowiedzieć sobie o tym, jak rekurencji możemy się najzwyczajniej w świecie… pozbyć. Proces ten nazywamy derekursywacją i możemy podejść do tego na różne sposoby, których część tutaj opiszę.

Rekurencja — co to jest?

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.

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

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

Po sortowaniu bąbelkowym i sortowaniu przez wstawianie nadszedł czas na omówienie ostatniego z tak zwanych prostych podejść do sortowania. Tym razem elementów nie będziemy zamieniać czy wstawiać, tylko wybierać. A co to dokładnie oznacza? Więcej w artykule.

W poprzednim artykule z serii o sortowaniu pokazałem, jak można odtworzyć krok po kroku podstawowy algorytm sortowania przez zamianę — sortowanie bąbelkowe, a także wywodzące się z niego sortowanie koktajlowe i sortowanie grzebieniowe. Tym razem zróbmy inaczej — zamiast zamieniać, będziemy wstawiać.

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.