3. Algorytmy sortowania
Algorytm jest przepisem opisującym krok po kroku rozwiązanie problemu lub osiągnięcie jakiegoś celu. Algorytmika natomiast jest dziedziną zajmującą się algorytmami i ich właściwościami. Samo słowo algorytm wywodzi się od nazwiska arabskiego matematyka i astronoma - Muhammad ibn Musa al Chuwarizmi. Ten matematyk żył na przełomie VIII i IX wieku, jest on uznawany za prekursora metod obliczeniowych w matematyce.
Pojęcie algorytmu najłatwiej przedstawić za pomocą przykładu. Algorytm jest pewnego rodzaju przepisem (takim jak przepis na ciasto czy zapiekankę ziemniaczaną), ponieważ tak samo jak przepis, jest ciągiem czynności, których wynikiem jest na przykład rozwiązanie jakiegoś problemu informatycznego, czy matematycznego.
Algorytm możemy zapisać jako listę kroków, które mają być wykonywane do momentu zakończenia algorytmu. W tym tutorialu przykładem do zapisu algorytmów będzie zagadnienie rozkładu liczby na czynniki pierwsze (i wypisywaniu ich na standardowe wyjście). Wykorzystamy go przy każdym ze sposobów zapisu algorytmów, aby móc porównać te zapisy między sobą. Niech zmienna a będzie przechowywać wartość liczby, dla której będziemy szukać czynników pierwszych. W tym przypadku możemy zaproponować taką oto listę kroków:
1. Przypisz danej „i” wartoś 2 i idź do kroku nr 2.
2. Jeżeli „a” jest większe, bądź równe liczbie 2 przejdź do kroku nr 3.
3. Jeżeli „a” jest podzielne przez „i” przejdź do kroku nr 4.
4. Wypisz „i”, a potem idź do kroku nr 5.
5. Przypisz „a” wartość równą ilorazowi „a” przez „i”, a potem wróć do kroku nr 3.
6. Jeżeli „a” nie jest podzielne przez „i” to dodaj 1 do „i” i wróć do kroku nr 2.
7. Jeżeli „a” jest mniejsze od 2 to wypisz 1 i zakończ algorytm.
Przykładem graficznej prezentacji algorytmu jest schemat blokowy. Diagram składa się z figur geometrycznych (romby - bloki warunkowe, prostokąty - bloki wykonawcze, równoległoboki - bloki wejścia/wyjścia, owale - bloki startowe i końcowe) i strzałek, które są opisane przy pomocy elementów wybranego języka programowania.
Teraz przejdziemy do moim zdaniem najwygodniejszej reprezentacji algorytmu, czyli pseudokodu. Jego znakiem rozpoznawczym jest struktura typowa dla języków programowania, to znaczy znalazło się w nim miejsce dla pętli, jak i instrukcji warunkowych, za to nie musimy sobie zaprzątac głowy szczegółami składniowymi, czy też inicjalizacją danych. Pseudokod powinien być uniwersalny, tak aby było można przełożyć go na praktycznie każdy język programowania. Pseudokod dla naszego przykładu będzie prezentował się następująco:
i←2
dopóki a>=2
dopóki reszta z dzielenia „a” przez „i” równa się 0
wypisz „i”
a←a/i
i←i+1
wypisz 1
Sokoro już znamy różne sposoby zapisów algorytmów możemy przejść do kilku podstawowych zagadnień związanych z przeszukiwaniem tablic.
Załóżmy że mamy daną zmienną tab - tablicę n-elementową - i chcemy w niej odnaleźć element minimalny (bądź maksymalny). Niech będzie to tablica a o indeksach od 0 do n-1, to znaczy, że kolejne jej elementy możemy oznaczyć następująco: tab[0], tab[1], tab[2], ..., tab[n-1].
By odnaleźć element minimalny podejmiemy następujące kroki:
1. Stworzymy zmienną wynik i zainicjujemy ją pierwszą wartością z tablicy, czyli ```tab[0]```.
2. Następnie przejdziemy po kolejnych elementach tablicy (rozpoczynając od drugiego, ale pamiętaj, że tablicę numerowaliśmy od 0!) i jeżeli dany element tablicy jest mniejszy od naszego wyniku, to zaktualizujemy jego wartość przypisując do niego ten element.
3 Po przejściu po wszystkich elementach otrzymamy w wyniku element najmniejszy w tablicy.
Powyższy przepis zrealizujemy teraz za pomocą języka C, dla uproszczenia zakładając, że n=10.
#include <stdio.h>
int main(){
int n = 10;
int tab[] = {1,5,0,9,11,41,7,2,9,23};
int wynik = tab[0];
int i;
for(i=1;i<n;i++){
if(tab[i] < wynik){
wynik = tab[i];
}
}
printf("Element maksymalny tej tablicy wynosi: %d", wynik);
return 1;
}Podobnie zadanie będzie wyglądać dla zagadnienia poszukiwania elementu maksymalnego z tą różnicą, że w instrukcji warunkowej zmienimy operator porównania z < na >. Pozostało nam uzupełnić kod o fragment pozwalający na znalezienie pozycji elementu minimalnego.
#include <stdio.h>
int main(){
int n = 10;
int tab[] = {1,5,0,9,11,41,7,2,9,23};
int poz = 0; % na samym poczatku zakladamy, ze minimum znajduje sie w miejscu pierwszego elementu w tablicy
int wynik = tab[poz];
int i;
for(i=1;i<n;i++){
if(tab[i] < wynik){
wynik = tab[i];
poz = i; % znaleziono element mniejszy od dotychczasowego minimum, musimy zaktualizowac wartosc zmiennej przechowujacej pozycje elementu minimalnego
}
}
printf("Element maksymalny tej tablicy wynosi %d i znajduje sie na pozycji %d", wynik, poz);
return 1;
}Idea algorytmu sortowania przez wybór (dla sortowania rosnącego) polega na znalezieniu elementu najmniejszego i zamianą jego pozycji z elementem znajdującym się na pierwszej pozycji. Następnie szukamy w podzbiorze tablicy od elementu drugiego do ostatniego elementu najmniejszego i wymieniamy go z elementem na pierwszej pozycji tego podzbioru. Procedurę kontynuujemy dla pozostałych elementów aż cała tablica będzie posortowana. Algorytm sortowania przez wybór posiada klasę czasowej złożoności obliczeniowej równą O(n2). Sortowanie odbywa się w miejscu.
Zasada działania algorytmu sortowania bąbelkowego opiera się na cyklicznym porównywaniu par sąsiadujących elementów i zamianie ich kolejności w przypadku niespełnienia kryterium porządkowego zbioru. Operację tę wykonujemy aż cały zbiór zostanie posortowany. Algorytm sortowania bąbelkowego przy porządkowaniu zbioru nieposortowanego ma klasę czasowej złożoności obliczeniowej równą O(n2). Sortowanie odbywa się w miejscu.
Podstawową operacją algorytmu jest scalanie dwóch zbiorów uporządkowanych w jeden zbiór również uporządkowany. Operację scalania realizujemy wykorzystując pomocniczy zbiór, w którym będziemy tymczasowo odkładać scalane elementy dwóch zbiorów. Ogólna zasada jest następująca:
1.Przygotuj pusty zbiór tymczasowy
2.Dopóki żaden ze scalanych zbiorów nie jest pusty, porównuj ze sobą pierwsze elementy każdego z nich i w zbiorze tymczasowym umieszczaj mniejszy z elementów usuwając go jednocześnie ze scalanego zbioru.
3.W zbiorze tymczasowym umieść zawartość tego scalanego zbioru, który zawiera jeszcze elementy.
4.Zawartość zbioru tymczasowego przepisz do zbioru wynikowego i zakończ algorytm.
Sortowania przez scalanie jest algorytmem rekurencyjnym o czasowej złożoności obliczeniowej równą O(nlog(n)). Potrzebujemy w tym przypadku dodatkowej tablicy do posortowania elementów.
Ten algorytm należy do jednego z najszybszych algorytmów sortujących dane. Sortowanie szybkie wykorzystuje strategię dziel i rządź. Załóżmy, że chcemy posortować podtablicę tab[p..r], zakładając na początku, że nasza tablica to tab[0..n-1].
1. Dzielimy tablicę poprzez wybranie elementu rozdzielającego w podtablicy```tab[p..r]```. Przestawiamy elementy w podtablicy ```tab[p..r]```, tak aby wszystkie elementy w podtablicy ```tab[p..r]```, które są mniejsze lub równe elementowi rozdzielającemu były na lewo od niego, a wszystkie pozostałe elementy w podtablicy były od niego na prawo. Tę procedurę nazywamy partycjonowaniem. W tym momencie, nie jest istotne, w jakim porządku względem siebie znajdują się zarówno elementy na lewo od elementu rozdzielającego, jak i na prawo. Dbamy jedynie o to, aby każdy z elementów znajdował się w pewnym miejscu po odpowiedniej stronie elementu rozdzielającego. Z powodów praktycznych zawsze wybieramy najbardziej prawy element w podtablicy ```tab[r]``` jako element rozdzielający. Więc, na przykład, jeśli podtablica składa się z elementów [9, 7, 5, 11, 12, 2, 14, 3, 10, 6], wybieramy 6 jako element rozdzielający. Po partycjonowaniu, podtablica może wyglądać następująco: [5, 2, 3, 6, 12, 7, 14, 9, 10, 11]. Przyjmijmy, że ```q``` jest indeksem elementu rozdzielającego.
2. Zwyciężaj rekurencyjnie sortując podtablice ```tab[p..q-1]``` (wszystkie elementy na lewo od elementu rozdzielającego, o wartości mniejszej bądź równej wartości elementu rozdzielającego) i ```tab[q+1..r]``` (wszystkie elementy na prawo od piwotu, o wartości większej niż element rozdzielający).
3. Połącz nie robiąc nic. Skończyliśmy kiedy krok dzielenia posortował rekurencyjnie. Dlaczego? Wszystkie elementy na lewo od piwotu w tablicy ```tab[p..q-1]``` są mniejsze lub równe piwotowi i są posortowane oraz wszystkie elementy na prawo od piwotu w ```tab[q+1..r]``` są większe niż piwot i są posortowane. Elementy w ```tab[p..r]``` są posortowane!
Sortowania szybkie jest algorytmem rekurencyjnym o czasowej złożoności obliczeniowej równą O(nlog(n)). Sortowanie odbywa się w miejscu.