Sortowanie przez scalanie

Sama nazwa od razu nasuwa nam myśl, że będziemy coś łączyć... Ale my pracujemy na tablicy... Najpierw musimy ją podzielić. Cały algorytm opiera się na zasadzie dziel i zwyciężaj, ponieważ mniejszą tablice jest łatwiej posortować.
Dopóki tablica składa się z więcej niż jednego elementu, dzielimy ją na 2 połowy, oczywiste jest, że gdy tablica ma nieparzystą liczbę elementów to nie podzielimy środkowego elementu. Dlatego możemy go dodać np. do pierwszej połówki. Następnie rekurencyjnie powtarzamy dzielenie połówek na mniejsze części itd. Gdy każda część składa się tylko z 1 elementu scalamy posortowane części.
Scalanie polega na tym, że porównujemy pierwszy el. z części I z pierwszym el. z części II. Jeśli ten z części I był mniejszy to wstawiamy go do sklejonej tablicy na 1wszej pozycji... I następnie porównujemy 2gi el. z cz. I z pierwszym z części II. Tłumaczenie tego wygląda na trochę pogmatwane... Ale gdy spojrzycie na rysunek zasięgnięty z google to wyda się wam to łatwiejsze.

Sortowanie przez wybieranie - Delphi

Nie będziemy się już rozpisywali od podstaw. Podamy sam algorytm w Delphi. Deklarować zmienne pewnie już każdy umie. Oto kod:

for j := 1 to n - 1 do
    begin
        Min := j;

        for i := j + 1 to n do
            if Tab[i] < Tab[Min] then
                Min := i;

        Temp := Tab[Min];
        Tab[Min] := Tab[j];
        Tab[j] := Temp;
    end;

Gdyby coś było niezrozumiałe to proszę pisać.

Sortowanie przez wybieranie - C++

W poniższych przypadkach sortujemy w kolejności rosnącej. Tak jak poprzednio przekazujemy do funkcji 2 informacje:
*tab - wskaźnik na tablicę którą chcemy posortować
n - liczba elementów tablicy

void sort(int *tab, int n)
{
for(int i=0; i < n; i++) //Przeglądamy tablicę n razy
{
int min=i; //Element który będzie "pamiętał" numer
// najmniejszego elementu w tablicy
for(int j=i; j < n; j++) //Pętla porównująca
{
if(tab[min]>tab[j]) //Sprawdza czy el. o nr min jest
// mniejszy od el. o nr j
{
min = j; // Zapisuje numer najmniejszego el.
}
}
swap(tab[i], tab[min]); //Zamienia el. obecnie sprawdzany
// z el. o nr min.
}
}

Sortowanie przez wybieranie

Sortowanie przez wybieranie jest kolejną prostą metodą sortowania danych. Algorytm wyszukuje element, który ma znaleźć się na żądanej pozycji, następnie zamienia miejscami go z tym, który jest tam obecnie.
Przy sortowaniu elementów rosnąco wyglądałoby to tak:

1. Wyszukaj element o minimalnej wartości.
2. Zamień znaleziony element z tym na pozycji początkowej.

Przykład zasięgnięty z Wikipedii:

Posortowana zostanie tablica 8-elementowa [9,1,6,8,4,3,2,0]. W tablicy pogrubione zostaną te elementy wśród których wyszukuje się wartość minimalną.

Algorytm można nieco przyspieszyć, gdy tablica jest wypełniana z obu końców, tj. wyszukiwane jest równocześnie minimum i maksimum.

Sortowanie bąbelkowe - C++

Podane poniżej sortowanie przyjmuje 2 wartości.
*tab jest to wskaźnik na tablicę
n to ilość elementów w tablicy

void sortuj (int *tab, int n)
{
for (int j=0; j < n-1; j++)
{
for (int i=0; i < n-j-1; i++)
{
if (tab[i] > tab[i+1])
{
swap(tab[i], tab[i+1]);
}
}
}
}

Pierwsza pętla for jest odpowiedzialna za przejście przez tablicę n razy. (Tablica ma elementy ponumerowane od 0 do n-1). Druga pętla pilnuje by zostało wykonanych w każdym przejściu tablicy dokładnie n-j-1 porównań. (j to licznik przejść przez tablice) If sprawdza czy musimy zamieniać 2 sąsiadujące elementy czy może są już w dobrej kolejności. Swap to funkcja napisana w poprzednich notach zamieniająca 2 elementy.
Przykładowe użycie funkcji sortującej dla tablicy o nazwie array i liczbie elementów wynoszącej 10 wygląda następująco:

sortuj(array, 10);

Sortowanie bąbelkowe - Delphi

Zasada działania tego sortowania została wytłumaczone w poprzedniej notce. Teraz postaramy się pokazać sposób użycia go w Delphi. Kod może wyglądać tak:

{pod wyrazem Implementation należy zadeklarować odpowiednie zmienne}
var
    i, j, LiczbaPol, Temp : Integer;

{teraz przechodzimy do algorytmu}

begin
{najpierw należy podać ilość pól w tablicy, u nas są to 4 pola - co widać w poprzednim przykładzie}
    LiczbaPol := 4; {ilość pól dla tablicy [1..4]}

{teraz sortowanie metodą bąbelkową}
for j := 0 to LiczbaPol - 2 do
    begin
        for i := 0 to LiczbaPol - 2 do
            begin
                if Tablica[i] > Tablica[i+1] then
                    begin
                        Temp := Tablica[i];
                        Tablica[i] := Tablica[i+1];
                        Tablica[i+1] := Temp;
                     end;
             end;
    end;


end;

{należy pamiętać, że w miejsce Tablicy należy wstawić nazwę tej, która ma być posortowana}

Mamy nadzieję, że w/w kod jest jasny i zrozumiały. W przypadku niejasności prosimy o pisanie w ShoutBoxie. Postaramy się rozwiać wszystkie wątpliwości.

Sortowanie bąbelkowe

Sama nazwa kojarzy nam się z bąbelkami powietrza zamkniętymi pod wodą. Logiczne jest, że im są one większe tym szybciej wypływają na powierzchnię. Na dość podobnej zasadzie działa sortowanie bąbelkowe, ponieważ "wypycha" ono największy składnik na koniec. W naszych kodach będziemy przedstawiać wszystko na tablicy liczb całkowitych. Ale oczywiście można to zrobić na innych. A do zamiany stosowany jest wcześniej opisany algorytm swap. Algorytm polega na tym, że przegląda w tablicy 2 sąsiednie elementy. Jeśli pierwszy jest większy od drugiego to zamienia je miejscami. (Ważna jest tutaj kolejność elementów.) Następnie porównuje drugi element i trzeci. I tak, aż do końca tablicy. Wtedy ostatni jej element jest największym. (Ale reszta jest nieposortowana.) Aby ją poukładać należy ponownie wywołać algorytm dla tej samej tablicy (można dla tablicy bez ostatniego elementu).

Nasza przykładowa tablica wygląda następująco:
6 7 4 1
1. Porównujemy pierwsze 2 elementy: 6 i 7... Są one w dobrej kolejności.
6 7 4 1
2. Przechodzimy do następnej pary "7 i 4". 7>4 więc zamieniamy je miejscami.
6 4 7 1
3. Dalej porównujemy 7 i 1. 7>1 więc zamieniamy. jak widać po tym kroku największa liczba jest już na końcu tablicy.
6 4 1 7
4. Zaczynamy przeglądać tablicę od początku. 6>4
4 6 1 7
5. Kolejna para 6>1. Znów zamiana. I kolejna 6<7
4 1 6 7
6. Zaczynamy od początku sortować po raz ostatni. 4>1 zamieniamy je miejscami. Reszta jest już poukładana dobrze więc nic w kolejnych krokach się nie robi. Czyli algorytm jest zakończony.
1 4 6 7

Sortowanie to musi zrobić n-1 obiegów (Gdzie n to liczba elementów w tablicy.) i w każdym obiegu wykonać max. n-1 porównań. Dlatego ma złożoność rzędu O(n²). Można oczywiście to uprościć gdyż po pierwszym przejściu ostatni element jest ustawiony poprawnie, co za tym idzie możemy w kolejnym przejściu nie sprawdzać ostatniego elementu z poprzednim, lecz nieznacznie to skróci czas wykonywania operacji dla tablic. A na małych tablicach będzie to wręcz niezauważalne.

Swap - C++

Wszystko zostało skomentowane wcześniej, więc nie będziemy się zagłębiać w szczegóły jak to działa, gdyż opis jest zarówno w poście "SWAP - Delphi" jak i "Na dobry początek - SWAP". W razie niejasności pisać to wytłumaczy się co i jak. Tak wygląda funkcja swap napisana w języku c++.

void swap( int& a, int& b )
{
         int temp = a;
         a = b;
         b = temp;
}

Wywołanie funkcji w programie wygląda następująco:

swap(a,b);

Aby wszystko pięknie działało na początku programu przed funkcją główną umieszczamy nagłówek:

void swap( int& a, int& b );

A na samym końcu kodu wklejamy funkcję swap.

SWAP - Delphi

Postaramy się pokazać wygląd algorytmu SWAP w Delphi firmy Borland (funkcja SWAP występuje w Delphi i zamienia miejscami starszy bajt z młodszym, ale nie oto nam chodzi). Otóż kod wyglądałby mniej więcej tak:

var
    a, b, c : Byte; {użyliśmy typu Byte (zakres 0 do 255), ponieważ liczby na których będziemy operowali są dosyć małe. W zależności od zapotrzebowania deklarujemy typ, który nam odpowiada}

begin
    a := 2;
    b := 5;
{przypisaliśmy zmiennym wartości; zmienna c jest pomocniczą (domyślnie ma wartość 0)}

    c := a; {przypisaliśmy wartość a do zmiennej c; c = a = 2}
    a := b; {teraz a = 5, czyli nasze b}
    b := c; {b przyjmuje wartość c, czyli 2}
{teraz a = 5, b =2}

    ShowMessage('a = ' + FloatToStr(a) + ' b = ' + FloatToStr(b)); {ta komenda wyświetli komunikat pokazując wartości naszych liczb}
end;

Wystarczy wkleić powyższy kod pod napisem Procedure, aby przekonać się o działaniu algorytmu. SWAP jest wstępem do algorytmu losowania, który omówimy za jakiś czas. Postaramy się również napisać przykładowe programy działające według podanych na blogu kodach.

Na dobry początek - SWAP.

Pierwszym algorytmem, który omówimy będzie SWAP. Brzmi nieco tajemniczo, ale nie ma się czym przejmować. To bardzo prosty i popularny algorytm. Jak działa? To proste - SWAP zamienia miejscami dwa elementy. No tak, zamienia miejscami, ale po co? Otóż algorytm ten jest wykorzystywany m. in. przy sortowaniu danych. Wygląda mniej więcej tak:

Swap(zmienna1, zmienna2)

Jak działa? Otóż tworzy w pamięci trzecią zmienną (pomocniczą). Wartość zmienniej1 przypisuje nowej zmiennej, natomiast wartość zmienniej2 przypisuje zmienniej1. Następnie wartość zmiennej3 przypisuje zmienniej2. Wiem, wiem, brzmi skomplikowanie, ale wcale takie nie jest. Postaramy się to pokazać:

Mamy dwie zmiennie: a = 2 i b = 5.
Algorytm tworzy zmienną pomocniczą: c = 0.
Teraz następuje przypisanie: c = a. {c przyjmuje wartość a, czyli teraz c = 2}
Następnie: a = b. {a przyjmuje wartość b, czyli teraz a = 5}
No i finalnie: b = c. {b przyjmuje wartość c, czyli wcześniejszego a; b = 2}
Efekt: Obie zmienne zamieniły się wartościami. {a = 5, b = 2}

Algorytm prosty i jednocześnie bardzo przydatny. W kolejnych notkach postaramy się pokazać zastosowanie SWAP-a w różnych językach programowania.

Czym są algorytmy?

Z szeroko pojętymi algorytmami każdy z nas spotykał się w swoim życiu już od najmłodszych lat. Nie wierzysz? A robiłeś sobie kiedyś kanapki? "Przepis" jak zrobić te kanapki to właśnie algorytm.

1. Weź kromkę chleba.
2. Posmaruj ją masłem.
3. Połóż na to np. ser/wędlinę.

Z innymi algorytmami spotykaliśmy się już w wieku 6-7 lat. Było nim dodawanie. Naprawdę! A algorytm ten wygląda następująco (dodamy tu 3+2):

1. Masz zaciśniętą rękę.
2. Licząc prostujesz palce.
3. Policz na palcach do 3.
4. Od miejsca w którym skończyłeś liczyć policz jeszcze do 2.
5. Policz od początku ile masz palców wyprostowanych.

Jak widzisz, od zawsze mamy do czynienia z algorytmami. Spytaj się np. mechanika jak On wymienia olej w samochodach. Zależnie od marki samochodu algorytm wymiany oleju silnikowego nieznacznie się zmienia.
Jak widzisz Algorytmy są to przepisy jak coś wykonać. Aby mogły one funkcjonować, muszą składać się ze skończonej liczby instrukcji/kroków. Wyobraźmy sobie powyższy algorytm na robienie kanapki, gdy po kroku 2-gim dodamy krok "wróć do kroku 1".

1. Weź kromkę chleba.
2. Posmaruj ją masłem.
3. Wróć do kroku 1.
4. Połóż na to np. ser/wędlinę.

Teraz nigdy nie dojdziemy do kroku 4-tego. Ponieważ będziemy wiecznie wracać do kroku 1. Dlatego w/w przykład już nie jest algorytmem.

Na tym blogu postaramy się w łatwy i zrozumiały sposób przedstawiać algorytmy informatyczne, a może czasem też matematyczne. Zaczynając od tych najprostszych.