Krótki wstęp.
Sortowanie jest podstawowym, ale bardzo ważnym zagadnieniem w informatyce. Sortowaniu podlegają nie tylko tablice, ale często ogromne ilości danych w bazach danych, czy struktury danych dynamiczne, takie jak kolejki czy listy wiązane. Dlatego bardzo ważnym problemem jest jak sortować najefektywniej, aby zużyć jak najmniej dodatkowej pamięci, a przede wszystkim czasu.
Istnieje bardzo wiele bardzo różnych algorytmów, które realizują sortowanie. Wśród nich wymienia się takie, które działają w miejscu, czyli nie potrzebują dodatkowej pamięci (zawsze, co najwyżej kilka elementów ciągu, który mamy posortować wymaga "wyjęcia" z tablicy), a także takie, dzięki którym szybko sortuje się elementy, gdzie często powtarza się pewien klucz sortowania.
Jednak największym problemem, na jaki natrafia się przy projektowaniu algorytmów sortowania jest złożoność czasowa. Algorytmy sortujące, które wykorzystują w swoim działaniu porównania, nie mogą (zostało to udowodnione) działać szybciej niż ze złożonością czasową O(nlgn). Na szczęście w niektórych zastosowaniach można używać algorytmów zliczających, które nie wykonują porównań. Dzięki temu można sortować niektóre ciągi ze złożonością liniową, czyli O(n). Przykładami algorytmów, które ni wykonują porównań przy sortowaniu, są sortowania kubełkowe, przez zliczanie i pozycyjne.
Kiedy nie zależy nam na liniowej złożoności to najlepiej sprawdzającym się w praktyce algorytmem sortowania jest algorytm QuickSort. Jest on najszybszy wśród algorytmów używających porównań, poza tym dzięki swojej strukturze rekurencyjnej jest bardzo zwięzły i prosty w napisaniu.
Rozpoczniemy od algorytmów wykorzystujących porównania.
Sortowanie bąbelkowe, bubble sort
Sortowanie bąbelkowe jest jednym z najprostszych algorytmów sortowania. Polega na przejrzeniu elementów do posortowania i zamienianiu miejscami elementów, które znajdują się obok siebie. Przypomina to trochę klasyfikację niektórych elementów jako "lżejsze", które wypływają na powierzchnię, podczas gdy inne, "cięższe" pozostają niżej. Złożoność czasowa algorytmu sortowania bąbelkowego wynosi O(n2). Bardzo dużą zaletą sortowania bąbelkowego jest to, że jest stabilne, czyli w każdym momencie jego działania elementy już ustawione na swoich miejscach tam pozostają. Przy sortowaniu tablic takie sortowanie jest dość optymalne, ponieważ nie zabiera niemal żadnej dodatkowej pamięci, a narzut związany z przesuwaniem "bąbelków" jest minimalny.
Przejdźmy do przykładu.
procedure SortowanieBabelkowe (var A: Tablica; n: Integer);
var i: Integer; j: Integer; tmp: ElementTablicy;
begin
for i:=n downto 2 do
for j:=1 to i-1 do
if A[j]>A[j+1] then
begin
tmp := A[j];
A[j] := A[j+1];
A[j+1] := tmp;
end;
end;
Jak widać, procedura sortująca, która używa sortowania bąbelkowego jest bardzo prosta. Przeanalizujmy jej działanie.
Procedura jako parametry otrzymuje tablicę przez referencję. Przekazanie przez wartość (bez słowa kluczowego var) mijałoby się z celem, ponieważ po zakończeniu działania procedury kopia tablicy zginęłaby i nie otrzymalibyśmy posortowanej tablicy. Potrzebne nam są trzy pomocnicze zmienne (to jest cała dodatkowa pamięć!). Dwie z nich to zmienne typu liczbowego, które będą służyć jako liczniki dwóch pętli. Oprócz tego potrzebna jest zmienna, w której tymczasowo będzie przechowywana wartość pola tablicy. Jej typ powinien być zatem taki sam jak typ elementów tablicy.
Teraz jedyne co nam pozostaje to przejrzeć tablicę. Dla wygody robimy to od tyłu. Najpierw przeglądamy podtablicę o rozmiarze n, potem w każdym przebiegu zewnętrznej pętli przeglądamy tablicę o jeden mniejszą. Kiedy podczas przeglądania podtablicy napotkamy sytuację, w której zaburzony zostaje porządek sąsiadujących elementów, zamieniamy sąsiadujące miejscami. Tym sposobem w jednym przebiegu pętli wewnętrznej "przepychamy" jeden bąbelek na jego miejsce.
Zmienna pomocnicza tmp jest potrzebna przy zamianie miejscami wartości A[j] i A[j+1].
Algorytm sortowania bąbelkowego można ulepszyć. Może się bowiem zdarzyć, że niektóre przebiegi pętli wewnętrznej nie są potrzebne, ponieważ część bąbelków już jest na swoim miejscu. W tym celu wprowadza się dodatkową zmienną zwaną kresem, która mówi, na którym miejscu nastąpiła zamiana. Następny przebieg pętli będzie dotyczył tego kresu.
Sortowanie przez prosty wybór, selection sort
Sortowanie przez prosty wybór jest jednym z najbardziej intuicyjnych algorytmów sortujących. W każdym kroku algorytmu zapamiętuje się kolejną pozycję i wstawia na nią element najmniejszy w jeszcze nie posortowanym ciągu, zamieniając miejscami.
Oto kod algorytmu:
procedure SortowaniePrzezProstyWybor (var A: Tablica; n: Integer);
var i:Integer; j:Integer; pozycjaMinimum:Integer; tmp:ElementTablicy;
begin
for i:=1 to n-1 do
begin
pozycjaMinimum := i;
for j:=i+1 to n do
if A[j] tmp := A[i]; A[i] := A[pozycjaMinimum]; A[pozycjaMimimum] := tmp; end; end; Jak działa powyższy algorytm? Za każdym przebiegiem zewnętrznej pętli ustawia się na swoim miejscu jeden element. Za każdym razem zapamiętuje się pozycję elementu, który w jeszcze nie posortowanym ciągu jest najmniejszy. Następnie zamienia się miejscami ten element z kolejnym, który zaburza porządek. Sortowanie przez prosty wybór jest niestabilne. Przykładem może być ciąg cyfr 1 2 3 5 6 7 4. W kolejnych przebiegach pętli algorytmu względny porządek cyfr 5 6 7 będzie zaburzony. Kolejne pętle będą wyglądały następująco: 1 2 3 5 6 7 4 1 2 3 4 6 7 5 1 2 3 4 5 7 6 1 2 3 4 5 6 7 Sortowanie przez proste wstawianie, insertion sort Sortowanie przez proste wstawianie jest najbardziej efektywne i najczęściej stosowane dla małych ciągów. Z trzech przedstawionych prostych algorytmów ten jest najlepszy. Jest to także algorytm często stosowany w normalnym życiu, chociażby przy układaniu na ręce kart przy grze w brydża. procedure SortowaniePrzezProsteWstawianie (var A: Tablica; n: Integer); var i: Integer; j: Integer; tmp: ElementTablicy; begin for i:=2 to n do begin j := i-1; tmp := A[i]; while (j>=1) and (tmp < A[j]) do begin A[j+1]:=A[j]; Dec(j); end; A[j+1] := tmp; end; Przeanalizujmy ten algorytm. Za każdym przebiegiem pętli zewnętrznej zapamiętujemy wartość elementu, który chcemy umieścić na jego miejscu w ciągu. Następnie przeglądamy już uporządkowaną część ciągu dopóty, dopóki nie natrafimy na coś mniejszego od naszego elementu, albo nie dojdziemy do początku. Za każdym razem przesuwamy elementy w tył, robiąc "dziurę" w miejscu, w którym trzeba umieścić nasz element. Sortowanie przez proste wstawianie jest stabilne. Sortowanie kubełkowe, bucket sort Sortowanie kubełkowe jest bardzo szybkie, jednak nie jest sortowaniem "w miejscu". Jak większość algorytmów tego typu również sortowanie kubełkowe potrzebuje wiedzieć, jaki jest zakres sortowanych wartości. Najczęściej dokonuje się takiego sortowania dla liczb równo rozłożonych w jakimś przedziale, na przykład od zera do jeden, lub od zera do sto. Taki przedział dzieli się na tak zwane kubełki, czyli mniej więcej równe podprzedziały. Liczby do posortowania wrzuca się do odpowiadającego im kubełka, a następnie sortuje się każdy kubełek osobno, najczęściej używając do tego którejś z wcześniej opisanych prostych metod sortowania. Następnie scala się kubełki i wypisuje cały posortowany ciąg. Aby reprezentować kubełki w komputerze najczęściej stosuje się struktury danych, tak zwane listy wiązane. Są to struktury dynamiczne, tworzone zawsze dopiero podczas działania programu, ponieważ rzadko wiadomo, ile liczb trafi do którego kubełka. Sortowanie przez zliczanie, counting sort Sortowanie przez zliczanie jest przede wszystkim bardzo szybkie, ponieważ jego złożoność czasowa wynosi zaledwie O(n). Niestety, nie nadaje się do wielu zastosowań. Ideą sortowania przez zliczanie jest to, by wartości w sortowanym ciągu jak najczęściej się powtarzały. Dla przykładu, gdybyśmy musieli posortować kilka tysięcy osób zgodnie z ich wiekiem, wiedząc, że najstarszy z nich ma 100 lat, sortowanie przez zliczanie jest nieocenione. Dzięki niemu nie musimy nawet przechowywać wszystkich osób, tylko wczytywać po jednej. Dzięki temu program zajmuje bardzo mało pamięci, tylko tyle, ile potrzeba na dodatkową strukturę danych dla sortowania przez zliczanie. W naszym przykładzie będzie to tablica o 100 elementach typu liczbowego. Na początku należy ją wyzerować. Za każdym razem kiedy wczytamy wiek jakiejś osoby, dokonujemy dodania jedynki do odpowiedniej pozycji: Tablica[wiek] := Tablica[wiek]+1. Po wczytaniu wszystkich danych wystarczy wypisać liczbę 1 tyle razy, ile wynosi Tablica[1], liczbę 2 tyle razy, ile wynosi wartość Tablica[2] i tak dalej. Sortowanie pozycyjne, radix sort Sortowanie pozycyjne jest wykorzystywane, kiedy potrzebne jest sortowanie względem różnych kryteriów. Na przykład kiedy sortujemy alfabetycznie dane osób i chcemy, by były posortowane względem nazwisk, ale jeśli zdarzą się osoby o tym samym nazwisku, to by alfabetycznie były też posortowane ich imiona. Każda pozycja w rekordzie z danymi musi być sortowana którymś z prostych lub logarytmicznych sortowań, jednak warunkiem koniecznym jest, by sortowanie to było stabilne. Często potrzebujemy posortować daty. Do tego celu sortowanie pozycyjne nadaje się bardzo dobrze. Zawsze sortujemy pozycje od najmniej znaczącej, czyli najpierw według dni, potem miesięcy, a na końcu lat. Dzięki temu otrzymamy daty dokładnie posortowane. Sortowanie szybkie, quicksort Na początku wspomniane było, iż dolnym oszacowaniem złożoności dla algorytmów sortujących z wykorzystaniem porównań jest równe nlgn. Tymczasem wszystkie proste sortowania miały złożoność n2. Czy zatem oszacowanie to jest wyssane z palca? Oczywiście nie. Istnieją algorytmy, które mają taką średnią złożoność. Do nich zalicza się przede wszystkim najbardziej znany i najczęściej implementowany algorytm sortowania QuickSort. Jest to algorytm, który opiera się na technice programowania "dziel i zwyciężaj". W każdym kroku algorytmu ciąg, który ma być posortowany jest dzielony na pół. Podział ten jest dokonywany tak, że zawsze po prawej stronie są elementy mniejsze niż po lewej. Nie są absolutnie posortowane, jednak ten warunek spełniają. Za każdym razem algorytm zajmuje się mniejszą podtablicą i kiedy dochodzi do tablicy o rozmiarze dwa, ją porządkuje. Potem algorytm zabiera się za następną małą część tablicy. Oto kod algorytmu QuickSort, wykorzystujący rekurencję: procedure QuickSort (var A: Tablica; p: Integer; l: Integer); var i: Integer; j: Integer; tmp: ElementTablicy; x: ElementTablicy; begin i := p; j := l; x := A[(l+p) div 2]; while i begin while A[i] while A[j]>x do Dec(j); tmp := A[i]; A[i] := A[j]; A[j] := tmp; end; if j
if l
end; Procedura przyjmuje jako parametry tablicę oraz jej początek i koniec. Następnie zapamiętuje początek (p) i koniec (l). Wartość x jest wartością rozdzielającą, wybraną na chybił trafił, jako wartość środkowego elementu. Najlepiej byłoby, gdyby ta wartość rzeczywiście była wartością środkową, wówczas algorytm działa najszybciej. Istnieją metody, które zapewniają taki właśnie "dobry" wybór elementu dzielącego. Następnie algorytm dzieli tablicę tak, by na lewo od elementu łączącego znajdowały się elementy mniejsze, a na prawo większe od niego. Kolejnym krokiem jest wywołanie rekurencyjne algorytmu dla obu "połówek" tabeli, gdzie algorytm robi to samo. Tym sposobem sortuje cały ciąg.
