Przejdź do treści

Sortowanie

Popularny (i bardzo naturalny) problem sortowania formułuje się w następujący sposób:

Dana jest tablica A[0..n-1] pewnych elementów, które możemy ze sobą porównywać – w najprostszej wersji, liczb całkowitych. Chcemy tak przestawić elementy, aby były one ustawione w kolejności niemalejącej.

Algorytmów sortowania jest bardzo wiele, różnią się one szybkością działania, prostotą implementacji oraz sytuacjami w jakich można je stosować. Omówimy szczegółowo dwa algorytmy i wspomnimy o kilku dalszych.

Sortowanie bąbelkowe

Jest to jeden z najprostszych do napisania algorytmów, ale bynajmniej nie najefektywniejszy. Opiera się na prostej zasadzie: jeśli dwa elementy są ustawione w złej kolejności (większy przed mniejszym), należy je zamienić miejscami. Przejdźmy tak przez całą tablicę:

for(int i = 0; i < n-1; i++)
    if (A[i] > A[i+1])
        swap(A[i], A[i+1]);

Jak łatwo sprawdzić (choćby dla trzyelementowej tablicy [3, 2, 1]) nie wystarczy to do posortowania wszystkich elementów. Zauważmy jednak, że największy element tablicy musi po takiej pętli trafić na koniec – od miejsca, na którym stoi, będzie już za każdym razem zamieniany z następnym. Jeśli teraz powtórzymy procedurę, na przedostatnie miejsce w tablicy trafi drugi w kolejności element. Wystarczy zatem powtórzyć powyższą pętlę \(n\) razy, aby mieć pewnośc, że na swoich miejscach znajdą się wszystkie elementy w tablicy:

for(int k = 0; k < n; k++)
    for(int i = 0; i < n - 1; i++)
        if (A[i] > A[i + 1])
            swap(A[i], A[i + 1]);

Można jeszcze zauważyć dwa szczegóły: po pierwsze, wystarczy \(n-1\) przebiegów – jeśli \(n-1\) elementów jest na swoich miejscach, ostatni nie ma innej możliwości. Po drugie, skoro po pierwszym "przebiegu" na końcu jest ostatni element, można już go nie sprawdzać w dalszych iteracjach. Drugą pętlę wystarczy wykonać do elementu \(n-2\), trzecią do \(n-3\), i tak dalej. Ostateczna wersja algorytmu wygląda zatem następująco:

for(int k = 0; k < n-1; k++)
    for(int i = 0; i < n - k - 1; i++)
        if (A[i] > A[i + 1])
            swap(A[i], A[i + 1]);

Spróbujmy określić złożoność obliczeniową tego algorytmu. Tradycyjnie przy algorytmach sortowania liczby się liczbę porównań (czyli instrukcji postaci if (x > y) ...), rzadziej liczbę przestawień elementów w tablicy. W tym wypadku porównań jest najwięcej w całym algorytmie: \(n-1\) w pierwszym obrocie pętli, \(n-2\) w drugim, ..., aż do jednego porównania w ostatnim obrocie. Całkowita złożoność wynosi zatem:

\[ n-1 + n-2 + \ldots + 1 = \frac{n(n-1)}{2}. \]

W zapisie poznanym na ostatnim wykładzie jest to funkcja \(\Theta(n^2)\). Sortowanie bąbelkowe jest więc algorytmem kwadratowym: doskonale nadaje się do posortowania 100, czy nawet 1000 liczb, ale już nie 100 000.

Sortowanie przez scalanie (MergeSort)

Omówiona w wykładzie 2 idea rekursji może pomóc również przy sortowaniu. Pamiętamy, że ideą rekursji jest wywołanie tego samego algorytmu, ale na odpowiednio mniejszych danych. Niech zatem A będzie tablicą, którą chcemy posortować. Podzielmy ją na pół (może być nieparzystej długości, więc połówki nie wyjdą jednakowe, to jednak nie ma znaczenia) i wyobraźmy sobie, że na obu połowach nastąpiło wywołanie rekurencyjne. W praktyce rozwiązujemy to w ten sposób, że tworzymy funkcję MergeSort() przyjmującą indeksy p i q – początek i koniec fragmentu, który ma być posortowany. Funkcja MergeSort(p, q) znajduje s – środek przedziału [p, q], a następnie wywołuje się rekurencyjnie jako MergeSort(p, s) i MergeSort(s+1, q).

void MergeSort(int p, int q)
{
    int s = (p + q) / 2;
    MergeSort(p, s);
    MergeSort(s+1, q);
    // ....
}

Obie połowy tablicy są mniejszymi danymi niż tablica wejściowa. Siła rekursji polega na tym, że możemy teraz przyjąć, iż obie połowy będą po tym wywołaniu posortowane. Rekursja zadziała jednak pod dwoma warunkami: po pierwsze, musimy zapewnić, by nie wywoływała się w nieskończoność, lecz kończyła na pewnych najmniejszych przypadkach – najprościej zauważyć, że jednoelementowej tablicy (dla \(p = q\)) sortować już nie trzeba.

void MergeSort(int p, int q)
{
    if (p==q)
        return;
    int s = (p + q) / 2;
    MergeSort(p, s);
    MergeSort(s+1, q);
    // ....
}

Trudniejsza kwestia jest jednocześnie kluczowa dla algorytmu: musimy wynik rekursji – dwie posortowane połówki tablicy – zamienić na prawidłowe wyjście algorytmu, całą posortowaną tablicę. Faza ta zwana jest scalaniem i od niej algorytm bierze swoją nazwę.

Jak zamienić dwie posortowane kawałki tablicy w jeden? W tym celu zacznijmy od nieco prostszego zadania: mając dane dwie posortowane tablice X[0..a-1] oraz Y[0..b-1], należy złączyć ich elementy do jednej posortowanej tablicy Z[0...a+b-1].

Idea jest bardzo prosta: jaki element może trafić do komórki Z[0]? Musi to być najmniejszy element ze wszystkich, a zatem znajduje się albo pod X[0], albo pod Y[0]. Wystarczy więc wybrać mniejszy z tych dwóch elementów – na chwilę przyjmijmy, że to X[0]. Teraz o miano najmniejszego elementu, który trafi do Z[1], rywalizują X[1] oraz Y[0], i procedurę możemy powtórzyć, a potem postępować tak samo do wyczerpania elementów w tablicach X i Y. Formalnie: ustawiamy wskaźnik i tak, aby X[i] było pierwszym niewykorzystanym jeszcze elementem tablicy X(czyli na początku na 0), a wskaźnik j tak, aby Y[j] pierwszym niewykorzystanym elementem Y. Porównujemy ze sobą X[i] oraz Y[j] i mniejszy z tych dwóch elementów wpisujemy na pierwsze wolne miejsce w tablicy Z:

int i = 0;
int j = 0;

for(int k = 0; k < a + b; k++)
    if (X[i] < Y[j])          // Uwaga: ta instrukcja (na razie) jest błędna!
    {
        Z[k] = X[i];
        i++;
    }
    else
    {
        Z[k] = Y[j];
        j++;
    }

W powyższym kodzie jest jednak błąd: elementy z jednej tablicy (na przykład X) mogą wyczerpać się przed elementami z drugiej tablicy, czyli wskaźnik i osiągnie wartość a. Próba czytania z X[a] spowoduje najprawdopodobniej błąd wykonania programu, ponieważ taka komórka nie istnieje. Aby się przed tym zabezpieczyć, musimy przed porównaniem sprawdzić, czy i<a (jeśli nie, to bez porównywania bierzemy Y[j], a nie X[i]), oraz czy j<b (jeśli nie, bierzemy X[i] nie próbując porównywać z nieistniejącym Y[j]):

int i = 0;
int j = 0;

for(int k = 0; k < a + b; k++)
    if ( (j >= b) || ( (i < a) && (X[i] < Y[j]) ) )
    {
        Z[k] = X[i];
        i++;
    }
    else
    {
        Z[k] = Y[j];
        j++;
    }

Teraz procedura działa poprawnie. Jesteśmy więc gotowi, aby wrócić do pierwotnego problemu: dana jest tablica A[0..n-1], sortujemy jej fragment A[p..q], przy czym fragmenty A[p..s] oraz A[s+1..q] są już posortowane. Do tego będziemy potrzebować drugiej, pomocniczej tablicy B, aby na chwilę wpisać tam elementy we właściwej kolejności. Przepiszmy poprzednią procedurę, przy czym rolę tablicy X przejmuje fragment A[p..s], zaś rolę tablicy Y fragment A[s+1..q].

void MergeSort(int p, int q)
{
    if (p==q)
        return;
    int s = (p + q) / 2;
    MergeSort(p, s);
    MergeSort(s+1, q);

    int i = p;
    int j = s+1;
    for (int k = p; k <= q; k++)
        if (j>q || ( i<=s && A[i] < A[j] ) )
        {
           B[k] = A[i];
           i++;
        } else
        {
           B[k] = A[j];
           j++;
        }
     for(int k = p ; k <= q; k++)
          A[k] = B[k];

}

Złożoność

To, ile algorytm MergeSort wykona operacji, wydaje się na pierwszy rzut oka nieoczywiste. Policzmy, ile razy liczby zostaną przepisane do tablicy B – pozostałych operacji jest w algorytmie mniej–więcej tyle samo (na każde przepisanie do B przypada jedno "powrotne" przypisanie do A, ta każde trzy operacje porównania).

MergeSort(0, n-1) wykona \(n\) takich operacji (cała tablica A zostanie przepisana do B). Ale oprócz tego, nastąpią dwa wywołania rekurencyjne: MergeSort(0, s) i MergeSort(s+1, n-1), gdzie s = (n-1)/2. Oba łącznie przepiszą całą tablicę A, a więc oba łącznie również wykonają n operacji. Te dwa wywołania spowodują kolejne cztery wywołania, każde na fragmencie tablicy długości około n/4. Znowu, łącznie w tych czterech wywołaniach będzie \(n\) operacji. Widzimy zatem, że sortowanie przez scalanie wykonuje \(n\) operacji za każdy "poziom" rekursji. Poziomów zaś będzie tyle, ile razy zdołamy podzielić tablicę (początkowej długości \(n\)) na połowę, zanim jej długość nie spadnie do 1. A wiemy już, że ta liczba równa jest \(\log n\).

Wiemy zatem, że algorytm sortowania przez scalanie działa w złożoności obliczeniowej \(O(n \log n)\). A zatem jest szybki: nadaje się do sortowania nawet tablic rozmiaru kilku milionów elementów.

Liczenie inwersji

W jednym z zadań do dzisiejszej lekcji dana jest tablica \(A[0...n-1]\), w której trzeba policzyć inwersje: takie pary \((i, j)\), dla których \(i < j\) oraz \(A[i] > A[j]\) – innymi słowy, takie pary, w których większa liczba stoi przed mniejszą. Nie można tego zrobić "naiwnie", sprawdzając wszystkie pary: jest ich \(\frac{n(n-1)}{2}\), czyli \(\Theta(n^2)\).

Wyobraźmy sobie, że sortujemy tę tablicę za pomocą sortowania przez scalanie. Elementy zmieniają swoje miejsca w fazie scalania – spróbujmy uchwycić moment, kiedy mniejszy element "mija" większy stojący przed nim. Dzieje się tak wtedy, gdy porównujemy elementy z dwóch połówek tablicy \(A[i] < A[j])\) i "wygrywa" element z drugiej połówki (czyli mniejsze jest liczba \(A[j]\)). Mija on wtedy pewną liczbę elementów większych, które stały przed nim, w wyniku czego likwidowana jest pewna liczba inwersji. Trzeba zatem je w tym momencie policzyć. Dokładną interpretację – i implementację – tego pomysłu pozostawiamy Czytelnikowi.

Inne algorytmy sortujące

Algorytm MergeSort jest szybki i elegancki, ale ma jedną zasadniczą wadę: wymaga drugiej, pomocniczej tablicy, czyli tyle samo dodatkowej pamięci, niż potrzeba na zapisanie dane. Sortowanie bąbelkowe nie ma tej wady – o tym algorytmie mówimy, że sortuje elementy w miejscu, czyli oprócz tablicy z danymi używa tylko kilku (stałej liczby, niezależnej od danych) dodatkowych komórek pamięci. Powstaje naturalne pytanie: czy istnieje algorytm, który miałby jednocześnie szybkość działania MergeSorta (czyli złożość \(n \log n\)) oraz własność sortowania w miejscu? Odpowiedź brzmi: istnieje, i to więcej niż jeden. Przykładem takiego algorytmu jest sortowanie przez kopcowanie (HeapSort), jednak najczęściej używanym algorytmem jest tak zwane sortowanie szybkie, z angielska QuickSort.

Algorytm sortowania szybkiego również działa na zasadzie rekurencyjnej. Najpierw jednak wybiera pewien element tablicy, na przykład losując go, albo biorąc po prostu pierwszy element. Niech element ten nazywa się \(x\). Teraz QuickSort za pomocą jednego przejścia przestawia elementy tablicy tak, aby elementy mniejsze od \(x\) trafiły na lewą stronę, większe – na prawą. Po tej fazie mamy wyznaczony podział tablicy na elementy "małe" i "duże". Jeśli teraz wywołamy się rekurencyjnie osobno na połówce "małej", a osobno na "dużej", to po zakończeniu rekurencji obie połówki będą posortowane, a to znaczy, że cała tablica będzie posortowana – wszystkie "małe" elementy i tak musiały stać przed "dużymi".

QuickSort miałby identyczny czas działania jak MergeSort, gdyby za każdym razem udawało się wylosować element \(x\) dzielący tablicę dokładnie na pół. To się jednak prawie nigdy nie uda – im bardziej nierówne będą części tablicy, tym większy czas działania algorytmu. Można jednak pokazać, że QuickSort z bardzo, bardzo dużym prawdopodobieństwem działa w złożoności \(O(n \log n)\). Mówi się – nie będziemy jednak wchodzić w szczegóły – że średnia złożoność sortowania szybkiego to \(O(n \log n)\).

Implementacja sortowania w C++ (patrz następny rozdział) jest oparta właśnie o QuickSort. Ten algorytm okazuje się być w praktyce najszybszy ze znanych metod sortowania, stąd jego nazwa.

Dodatek: sortowanie w C++

Aby posortować w języku C++ tablicę liczb całkowitych A[0..n-1], wystarczy napisać:

sort(A, A + n);

Należy przy tym zwrócić uwagę, że mimo iż ostatnim elementem tablicy jest A[n-1], musimy napisać A+n, a nie A+n-1.

W drugim z podanych zadań trzeba posortować elementy, które nie są liczbami – w tym wypadku rekordy złożone z nazwiska osoby i pewnej liczby. Jeśli takie rekordy trzymamy jako strukturę:

struct osoba
{
    string nazwisko;
    int liczba;
};

to trzeba w jakiś sposób podpowiedzieć programowi porządek, według którego ma sortować. Przyjmijmy, że chcemy uporządkować osoby według posiadanej przez nie liczby. W tym celu piszemy funkcję porownaj(osoba a, osoba b), która będzie zwracać true dokładnie wtedy, gdy osoba a jest mniejsza (powinna się znaleźć wczesniej w tablicy) od osoby b.

bool porownaj(osoba a, osoba b)
{
    if (a.liczba < b.liczba)
        return true;
    else
        return false;
}

Teraz wystarczy napisać:

sort(A, A + n, porownaj)

aby posortować tablicę osób A[0..n-1], używając funkcji porownaj do wyznaczania kolejności elementów. Warto pamiętać, aby taka funkcja zachowywała się podobnie do operatora mniejszości (<): w szczególności nie zwracała true dla dwóch równych elementów, oraz nie zwracała true w obie strony ( a<b oraz b<a). Źle napisane funkcje porównujące powodują trudne do znalezienia błędy.

Z przyczyn technicznych do tej lekcji będzie tylko jedno zadanie. Postaramy się dodać drugie z zadań do jednej z późniejszych lekcji.

Zadania

Inwersje