Algorytmy

Algorytm

inform. dokładny przepis wykonania w określonym porządku skończonej liczby operacji, pozwalający na rozwiązanie każdego zadania danego typu,
mat, reguła przekształcania wyrażeń matematycznych poprzez powtarzanie tych samych działań na kolejno otrzymywanych wynikach działań poprzednich.
Zapis algorytmów
opis słowny (np. przepisy kulinarne w książce kucharskiej)
schemat blokowy (sieć działań, flow chart, flow diagram)
język programowania wysokiego poziomu, np. Pascal lub C

Opis słowny - polega na logicznym i zrozumiałym dla odbiorcy przedstawieniu kolejnych czynności (akcji), jakie należy wykonać, aby osiągnąć zamierzony efekt. Przykładami takiego opisu algorytmu mogą być: przepis kulinarny, recepta wykonania leku, metoda rozwiązania zadania.
Schemat blokowy - jest jedną z najpopularniejszych form przedstawiania algorytmu.
Rodzaje sieci działań:
Proste (sekwencyjne) - nie używa się w nich bloków warunkowych. W takiej sieci działań kolejność realizacji poszczególnych operacji jest ściśle określona i żadna z nich nie może być pominięta ani powtórzona.
z rozwidleniem - zawiera w sobie wybór jednej z kilku możliwych dróg realizacji danego zadania. Istnieje w nim przynajmniej jeden blok warunkowy.
z pętlą, często w trakcie realizacji danego zadania konieczne jest powtórzenie niektórych operacji różniących się jedynie zestawem danych. Pętla obejmuje tą część bloków, która ma być powtarzana.
złożone - będące kombinacją powyższych sieci.
Algorytmy sortowania
Mając do czynienia z rozmaitymi zbiorami danych, często stajemy przed koniecznością posortowania tychże danych. Posortować, czyli inaczej tak poprzemieszczać poszczególne elementy zbioru danych, aby te znalazły się w określonym porządku, np. rosnącym.
Sortowanie umożliwia przede wszystkim łatwiejszy dostęp do danych - uporządkowane dane przegląda się szybciej, gdyż znany jest porządek ułożenia tych danych. Również wtedy zastosować można bardzo szybkie, binarne algorytmy wyszukiwania danych, pozwalające stwierdzić, czy konkretne dane w ogóle znajdują się w zbiorze; w którym miejscu owe dane się znajdują; czy też pozwalają na dopisanie nowych danych w taki sposób, aby nie zaburzyć porządku ułożenia istniejących już danych.
Głównym czynnikiem determinującym wydajność algorytmu jest jego koszt, czyli ilość operacji wzajemnej zmiany położenia dwóch elementów oraz ilość operacji porównania. Dla poszczególnych algorytmów jest on różny, zależny od złożoności danych, ich porządku oraz oczywiście od ilości danych. Koszt może być logarytmiczny lub kwadratowy.
Sortowanie bąbelkowe
Sortowanie bąbelkowe jest najprostszym, ze znanych algorytmów sortowania. Swoją nazwę zawdzięcza temu, że w przypadku pionowego przedstawienia zbioru danych, element najmniejszy (przy sortowaniu w porządku rosnącym) niejako wypływa do góry. Działanie tego algorytmu opiera się na porównywaniu każdego elementu z elementem następującym po nim i w przypadku stwierdzenia nieprawidłowej relacji pomiędzy tymi elementami następuje zamiana ich kolejności. Wynika to z założenia, że nieposortowany ciąg zawiera, co najmniej dwa elementy znajdujące się na nieodpowiednich miejscach. Kolejnym krokiem jest sprawdzenie, czy poczyniona przez algorytm zmiana kolejności dwóch elementów nie wpłynęła na prawidłowość relacji pozostałych elementów. Jeżeli zaburzyła tą prawidłowość, zbiór danych jest ponownie przeszukiwany w tym samym kierunku. Algorytm kończy swoje działanie w przypadku stwierdzenia, że wszystkie elementy znajdują się w prawidłowej relacji, czyli że nie została wykonana jakakolwiek zamiana kolejności elementów. Pesymistyczny koszt takiego algorytmu wynosi n 2 , gdzie n oznacza ilość elementów do posortowania. Bubblesort jest bardzo wydajny, jeżeli używamy go do zbioru danych o bardzo małej ilości elementów, lub też zbiór danych jest prawie posortowany (wymaga bardzo małej ilości zmian).
Sortowanie pęcherzykowe (shaker sort)
Sortowanie pęcherzykowe jest mutacją sortowania bąbelkowego. Jedyna istotna różnica pomiędzy tymi algorytmami jest taka, że algorytm bubblesort zawsze rozpoczyna szukanie od początku danych, zaś shakersort naprzemiennie od początku i od końca. W pewnych przypadkach daje ten zabieg pewną oszczędność czasu, jednak tak samo jak w przypadku bubblesort, koszt może wynieść nawet n 2 gdzie n oznacza ilość elementów do posortowania.
Sortowanie przez wstawianie (insertion sort)
Sortowanie przez wstawianie jest również prostym algorytmem sortowania. Jego działanie polega na sprawdzaniu kolejnych elementów pod względem poprawności zajmowania przez nich miejsca w zbiorze. Jeżeli dany element nie znajduje się na właściwym miejscu (np. mniejszy element po elemencie większym w przypadku sortowania rosnącego), szukane jest miejsce odpowiednie dla niego, po czym następuje przesunięcie zawartości całego zbioru, w celu zwolnienia dla danego elementu, właściwego miejsca. Algorytm ten jest przydatny przy sortowaniu danych sukcesywnie napływających. Podobnie jak w przypadku algorytmów bubblesort i shakersort pesymistyczny koszt działania tego algorytmu wynosi (n 2 -n)/2 , gdzie n oznacza ilość elementów do posortowania.
Sortowanie przez wybieranie (selection sort)
Sortowanie przez wybieranie jest już bardziej wydajnym algorytmem sortowania. Idea jego działania polega na wybieraniu z podzbioru danych zbioru elementu najmniejszego (w przypadku sortowania rosnącego) i zamianie jego położenia z początkowym elementem podzbioru. Następnie zakres poszukiwania zostaje zawężony do podzbioru danych znajdujących się po posortowanych już elementach. W pierwszym przeszukiwaniu tym podzbiorem jest naturalnie cały zbiór. Koszt tego algorytmu jest zauważalnie mniejszy od algorytmów bubblesort, shakersort i insertionsort. Wynosi on w pesymistycznym wypadku (n 2 -n)/2, gdzie n oznacza ilość elementów do posortowania. Zaletami algorytmu sortowania przez wybieranie jest optymalna ilość przestawień (n-1); prostota implementacji oraz zadowalająca szybkość dla małych wartości n.