Generyczność i delegaci

            Omawiając algorytmy sortowania skupiłem się na jedynie jednym typie danych - mianowicie liczbach typu int. A co w przypadku gdy mamy do posortowania tablicę zawierającą ciąg znaków typu char? Nic prostszego, przeciążamy metodę odpowiedzialną za sortowanie. Podobnie postępujemy w przypadku innych typów danych aż w końcu nasz program nieprzyjemnie puchnie z powodu redundancji kodu. A co w przypadku własnych struktur danych które nie mają zaimplementowanych metod odpowiedzialnych za porównywanie czy zamianę wartości? Z pomocą przychodzą nam dwa mechanizmy: generyczność oraz delegaci.

Generyczność

            Jak wiemy, C# jest językiem programowania który cechuje się silną kontrolą typów. Oznacza to, że w gdy miejscu użycia wartości typu bool wstawimy np. int (tak jak to jest możliwe w instrukcji if w C/C++) kompilator powie nam parę niemiłych rzeczy o tym co zrobiliśmy. Więc aby zmaksymalizować wydajność, zapewnić zgodność typów i zmniejszyć redundancję kodu wprowadzono typy generyczne. Mechanizm ten pozwala na definiowanie metod bez podania typu danych jakimi będzie ona operować. Typ danych z jakimi procować będzie metoda jest ustalany na poziomie deklaracji metody. Przykład użycia tego mechanizmy znajduje się w kodzie poniżej:

void swap<T>(ref T a, ref T b)

        {

            T tmp = a;

            a = b;

            b = tmp;

        }

            Używając znaczników <> definiujemy typ generyczny. Duża litera T jest typem zmiennej, który w momencie deklaracji metody zostanie zastąpiony właściwym. Użycie takiej funkcji odbywa się poprzez wstawienie w znaczniki <> typu docelowego. Przykład:

int a = 2, b = 6;

swap<int>(ref a, ref b)

Delegaci

                Delegaci to swego rodzaju referencyjny typ danych który odnosi się do metod. Mówiąc krótko, delegat to odnośnik do metody i taki odnośnik możemy przekazać jako argument funkcji. Dzięki temu możemy z wnętrza funkcji wywołać daną metodę. Do delegata przypisać możemy dowolną metodę która pasuje do jego sygnatury. Deklaracja delegata wygląda następująco:

delegate void Swapper<T>(ref T a, ref T b);

            Deklarację zaczynamy, jak w wypadku każdej zmiennej, od słowa kluczowego: delegate. Następnie określamy sygnaturę delegata, która wygląda identycznie jak definiowanie funkcji: podajemy typ zwracanych danych, nazwę i w nawiasach argumenty. Przypisanie do delegata metody wygląda w następujący sposób:

 Swapper<int> swap = new Swapper<int>(fun);

Najpierw deklarujemy delegata o nazwie swap. Jak już wspomniałem, delegaci to typy referencyjne i dlatego posługujemy się tutaj słówkiem new a jako argument przekazujemy samą nazwę funkcji. Wywołanie funkcji poprzez delegata wygląda jak zwyczajne wywołanie:

swap(ref zmiennaA, ref zmiennaB);

Przykład użycia: szybkie sortowanie

            Listing poniżej zawiera deklarację szybkiego sortowania jakie napisaliśmy wcześniej oraz z użyciem delegatów i typów generycznych.

void qSort(int[] arr, int size);

delegate int Comparer<T>(ref T a, ref T b);

delegate void Swapper<T>(ref T a, ref T b);

void qSort<T>(T[] array, int size, Comparer<T> compare, Swapper<T> swap);

           

            Na pierwszy rzut oka może to wydawać się bardzo skomplikowane ale po kolei. Po cóż nam delegaci? Podczas sortowania często porównujemy i zamieniamy elementy - o ile w przypadku typów wbudowanych (np. int, double) nie stanowi to problemu, to dla typów zdefiniowanych przez użytkownika zaczynają się schody. Dlatego też będziemy potrzebować dwóch funkcji pomocniczych: jednej która będzie odpowiedzialna za porównywanie ze sobą elementów i drugiej, która zamieni je miejscami. 

Permutacje

                Permutacją pewnego n-elementowego zbioru jest każdy n-wyrazowy ciąg zawierający wszystkie elementy tego zbioru. Mówiąc krótko: permutacja to każde możliwe uporządkowanie wszystkich elementów zbioru. Od dobrego algorytmu generującego wszystkie możliwe kombinacje oczekujemy, że:

·         generacja permutacji będzie odbywała się w jakiejś sensownej kolejności

·         dobre działanie w przypadku multizbioru tzn. nie będą się powtarzały permutacje w przypadku gdy niektóre elementy będą się powtarzać

·         generacja permutacji odbywała się w możliwie najkrótszym czasie

                Algorytm będzie spełniał te wymagania gdy kolejne permutacje będą generowane w porządku leksykograficznym. Przykładem porządku leksykograficznego jest słownik - każde słowo jest zbudowane z n liter które mają określony, alfabetyczny porządek - a, b, c, d,e..., czyli słowo które zaczyna się na literę E wystąpi przed słowem na literę N. Jeżeli dwa słowa zaczynają się na tą samą literę - patrzymy na kolejną w ciągu i porównujemy te litery oceniając które słowo powinno być pierwsze.

                Aby zapewnić odpowiednią generację permutacji wejściowy ciąg elementów musi być posortowany niemalejąco - warunek ten zapewnia generację leksykograficzną (ciąg wejściowy z faktu takiego ustawienia jest uważany za najmniejszy - czyli w pierwszy) oraz poprawne działanie algorytmu. W każdym kroku algorytmu wybieramy możliwie najdalszy element bieżącej permutacji i "powiększamy" go. Powiększamy go poprzez zamianę miejsc z możliwie najmniejszym, większym elementem od niego. Jak w optymalny sposób znaleźć te elementy? Otóż każdą permutację analizować będziemy do końca i szukać będziemy elementu mniejszego od jego poprzednika. Jeżeli znaleźć takiego elementu się nie uda - oznacza to ciąg posortowany nierosnąco i koniec generacji. Znaleziony element możemy uznać za możliwie najdalszy ponieważ możemy go zamienić z chociażby elementem poprzednim oraz nie można go zamienić z żadnym większym elementem występującym dalej. Następnie zamieniamy miejscami wybrany element z najmniejszym elementem położonym dalej, który jest od niego większy. Na koniec musimy uzyskać resztę permutacji posortowaną niemalejąco - wystarczy odwrócić jej kolejność.

                Aby rozjaśnić nieco sposób generacji rozważmy następujący przykład:

Aktualna permutacja:

8842811321

Znajdujemy najdłuższy, rosnący ciąg elementów patrząc od końca:

8842811 321

Możliwie najdalszy element to 1 - jest to pierwszy element mniejszy od poprzednika:

8842811 321

Następnie znajdujemy pierwszy element większy od elementu najdalszego licząc od końca ciągu:

8842811 321

Zamieniamy te dwa elementy miejscami:

8842812 311

Odwracamy kolejność reszty ciągu:

8842812 113

I w ten oto sposób otrzymaliśmy kolejną permutację ciągu.

Implementacja

void permutation(int n, int[] arr)

        {

            int i = 0;

            while (true)

            {

                printArray(arr, n + 1);

                i = n - 1;

                while (arr[i] >= arr[i + 1]) i--;

                if (i == 0) break;

                int j = n;

                while (arr[i] >= arr[j]) j--;

                swap(arr, i, j);

                int r = n; int s = i + 1;

                while (r > s)

                {

                    swap(arr, r, s);

                    r--;

                    s++;

                }

            }

        }

                Argumenty wejściowe to: liczba elementów w tablicy oraz tablica z elementami posortowanymi niemalejąco. Zmienna pomocnicza i odpowiada za przechowywanie indeksu elementu najdalszego, natomiast zmienna j elementu do zamiany. Zgodnie z algorytmem najpierw wyszukiwany jest element najdalszy i sprawdzamy czy generacja dobiegła końca. Dalej poszukiwany jest zamiennik oraz następuje zamiana tych elementów. Ostatnia pętla zajmuje się odwróceniem kolejności reszty ciągu.

                Uwaga, ze względu na charakter tego algorytmu - musi on wyprodukować każdą możliwą kombinację z ciągu wejściowego - czas jego wykonania może być ekstremalnie długi. W tabeli poniżej znajduje się parę przykładowych czasów:

Długość ciągu	5	9	12	13
Czas	<<1ms	12ms	11s	148s

                Dla zainteresowanych: ciekawym sposobem generowania wszystkich sekwencji danego zbioru elementów jest algorytm Steinhaus–Johnson–Trotter'a.

Szybkie sortowanie

Dzisiaj przedstawiony zostanie kolejny algorytm sortowania, konkurencyjne rozwiązanie względem sortowania przez scalanie. Szybkie sortowanie (ang. quick sort) zostało obmyślone przez Tony'ego Hoare i jest uważane za najlepsze w swojej dziedzinie. Podobnie jak sortowanie przez scalanie przeciętna złożoność obliczeniowa tego algorytmu to O(n*log(n)). Odpowiednia implementacja tego algorytmu pozwala zużyć znacznie mniej pamięci niż scalanie: O(log(n) zamiast O(n).

                Algorytm ten również działa na zasadzie "dziel i rządź" - z ciągu elementów wejściowych wybierany jest                 element osiowy (ang. pivot) względem którego będzie się odbywał podział. Polega ono na przeniesieniu wszystkich elementów mniejszych od osi na lewo od niej a większych na prawo. Po takim przetasowaniu element osiowy znajduje się na odpowiedniej dla niego pozycji w ciągu wyjściowym. Następnie, zgodnie z regułą "dziel i rządź" ta sama czynność jest wykonywania na dwóch częściach ciągu wejściowego aż do uzyskania posortowania elementów. Przykład działania znajduje się na obrazku poniżej:

From Wikipedia, the free encyclopedia

               

                Implementacja:

Najlepszym sposobem implementacji algorytmów działających na zasadzie dziel i rządź jest rekurencja. Główna pętla prezentuje się następująco:

void quickSort(int[] arr, int p, int q)

        {

            if (q <= p)

                return;

            int pivotIndex = p + (q - p) / 2;

            if (arr[p] > arr[q])

            {

                if(arr[q] > arr[pivotIndex])

                {

                    pivotIndex = q;

                }

                else if(arr[p] > arr[pivotIndex])

                {

                    pivotIndex = p;

                }

            }

            else

            {

                if(arr[p] > arr[pivotIndex])

                {

                    pivotIndex = p;

                }

                else if (arr[q] < arr[pivotIndex])

                {

                    pivotIndex = q;

                }

            }

            pivotIndex = distribute(arr, p, q, pivotIndex);

            quickSort(arr, p, pivotIndex - 1);

            quickSort(arr, pivotIndex + 1, q);

        }

                Argumenty wejściowe funkcji to: tablica z elementami do posortowania, indeks pierwszego elementu tablicy oraz indeks ostatniego elementu. Najpierw sprawdzamy czy możemy dalej dzielić tablicę - jeśli nie, przerywamy rekursję i "wracamy wyżej". Dalej wybierany jest element osiowy - jest on wartością środkową trzech elementów: pierwszego, środkowego i ostatniego. Ten sposób wyboru elementu pivot zwiększa szanse na najbardziej optymalne działanie algorytmu. Dzielenie ciągu następuje poprzez wywołanie funkcji distribute, którą omówimy zaraz a następnie funkcja wywołuje samą siebie aby posortować dalszą część tablicy.

                Sposób implementacji funkcji decyduje o ilości zasobów jaką zużywać będzie sortowanie, omówiony tutaj sposób nie potrzebuje żadnych dodatkowych tablic, gdyż operuje on tylko na tablicy wejściowej.

                int distribute(int[] arr, int p, int q, int pivot)

        {

            int pivotValue = arr[pivot];

            int store = p;

            swap(arr, pivot, q);

            for (int i = p; i < q; i++)

            {

                if (arr[i] < pivotValue)

                {

                    swap(arr, i, store);

                    store++;

                }

            }

            swap(arr, store, q);

            return store;

        }

                Argumenty wejściowe to: tablica na której będą odbywać się operacje, pozycja początku, końca tablicy oraz indeks elementu osiowego. Następnie elementy zostają poprzestawiane zgodnie z regułą: mniejsze na lewo i zostaje zwrócona pozycja środka tego podziału która w późniejszych wywołaniach posłuży jako wskaźnik końca lub początku nowej tablicy.

            Podsumowanie

                Sortowanie szybkie jest niewątpliwie demonem szybkości i oszczędności zasobów ale jest również niezwykle podatne sposób ułożenia danych wejściowych. Quick sort sprawdza się najlepiej gdy dane są czysto losowe schody zaczynają się gdy są one częściowo lub całkowicie posortowane - złożoność obliczeniowa sięga w tych przypadkach nawet O(n²) czyli równie wolno co proste algorytmy pokroju sortowania bąbelkowego. Również wybór elementu osiowego nie jest bez znaczenia: najlepiej gdy ten element jest medianą wszystkich wartości w tablicy, im bliżej wartości minimalnej bądź maksymalnej tym gorzej.

Sortowanie przez scalanie

         Pewnego wykładu profesor prowadzący zajęcia z informatyki powiedział: "każdy szanujący się informatyk powinien posiadać w swym portfolio porządny algorytm do sortowania”. Przez porządny, rozumiemy taki który, w najkrótszym możliwym czasie i przy użyciu najmniejszej ilości zasobów wyprodukuje na wyjściu poukładany ciąg elementów.

         Do tej grupy algorytmów zalicza się sortowanie przez scalanie (ang. merge sort). Bazuje ono na zasadzie "dziel i rządź" - czyli na podzieleniu problemu na mniejsze części, co znacznie ułatwia ich rozwiązywanie.

         Sortowanie przez scalanie polega na sukcesywnym połowieniu szeregu danych wejściowych do momentu pozostania z jednym elementem w zbiorze. Taki zbiór, ze względu na jego liczebność, bez wahania możemy nazwać posortowanym. Następnym krokiem jest scalenie takich jednoelementowych zbiorów w jeden, większy. Zgodnie z tą regułą "cofamy się", aż wszystkie takie podzbiory scalimy w całość, uzyskując posortowany ciąg wejściowy.

         Ceną, jaką musimy zapłacić za prostotę i szybkość jest dodatkowa pamięć którą zużywa algorytm. Pamięć ta jest używana jako tymczasowy bufor przy scalaniu poszczególnych fragmentów ciągu elementów.

         Działanie algorytmu przedstawione jest na rysunku poniżej, co znacznie ułatwia zrozumienie sposobu jego działania.

        

Implementacja

         Najelegantszy, a zarazem najbardziej czytelny sposób implementacji tego algorytmu uzyskamy za pomocą rekurencji - czyli funkcji wywołującej samą siebie. Główna pętla programu prezentuje się w następujący sposób:

void mergeSort(int[] arr, int p, int q)

{

 if (p >= q)

 {

    return;

 }

 int r = (p + q) / 2;

 mergeSort(arr, p, r);

 mergeSort(arr, r + 1, q);

 merge(arr, p, r, q);

}

         Gdzie argumenty funkcji oznaczają odpowiednio: tablicę elementów które mają zostać posortowane, indeks elementu pierwszego ciągu, indeks ostatniego elementu ciągu. Funkcja wyznacza środek ciągu r i następnie wywołuje samą siebie dzieląc wirtualnie tablicę na mniejsze. Instrukcja warunkowa if czuwa nad ilością elementów i jeżeli w ciągu znajduje się jeden element zakańcza ona rekursywne wywołania.

         Najważniejszą częścią jest implementacja funkcji scalania, która znajduje się na listingu poniżej:

void merge(int[] a, int p, int r, int q)

        {

            int[] tmp = new int[q - p + 1];

            int i = p, j = r + 1, k = 0;

            while (i < r+1 && j < q+1)

            {

                if (a[i] <= a[j])

                {

                    tmp[k] = a[i];

                    i++;

                }

                else

                {

                    tmp[k] = a[j];

                    j++;

                }

                k++;

            }

            if (i >= r+1)

            {

                while (j < q+1)

                {

                    tmp[k] = a[j];

                    j++;

                    k++;

                }

            }

            else

            {

                while (i < r+1)

                {

                    tmp[k] = a[i];

                    i++;

                    k++;

                }

            }

            k = 0;

            for (i = p; i < q+1; i++)

            {

                a[i] = tmp[k];

                k++;

            }

        }

    }

         Argumenty tej funkcji to: tablica z sortowanymi elementami, indeks pierwszego elementu pierwszej (lewej) tablicy, koniec pierwszej (lewej) tablicy oraz koniec drugiej (prawej) tablicy. Tablica prawa zaczyna się od elementu o indeksie r+1. Działanie funkcji przedstawia się następująco: najpierw jest tworzony bufor w którym będą przetrzymywane elementy oraz inicjowane są indeksy do elementów. Pierwsza pętla scala prawą i lewą część ciągu aż do momentu osiągnięcia końca jednego z nich. Instrukcja if(i >= r+1) ocenia który z ciągów już w całości przepisano a który jeszcze trzeba przepisać do bufora. Po skończeniu scalania bufor jest przepisywany do tablicy wejściowej.

        

            Podsumowanie

                Niewątpliwą zaletą sortowania przez scalanie jest jego szybkość i łatwość w implementacji. Złożoność obliczeniowa tego algorytmu to N*log(N) gdzie N oznacza liczbę elementów i jest ona niezależna od danych wejściowych tzn. niezależnie jaki ciąg danych pojawi się na wejściu czas obliczeń będzie zawsze równy N*log(N). Inaczej jest w przypadku konkurencyjnego rozwiązania - sortowania szybkiego którego złożoność waha się od N*log(N) do N².