Algorytmy sortujące - wstęp

Sortowanie danych jest jednym z podstawowych problemów programowania komputerów, z którym prędzej czy później spotka się każdy programista. Poniżej przedstawiamy tylko nieliczne dziedziny, w których występuje potrzeba sortowania danych:

• sport - wyniki uzyskane przez poszczególnych zawodników należy ułożyć w określonej kolejności, aby wyłonić zwycięzcę oraz podać lokatę każdego zawodnika.
• bank - spłaty kredytów należy ułożyć w odpowiedniej kolejności, aby wiadomo było kto i kiedy ma płacić odsetki do banku.
• grafika - wiele algorytmów graficznych wymaga porządkowania elementów, np. ścian obiektów ze względu na odległość od obserwatora. Uporządkowanie takie pozwala później określić, które ze ścian są zakrywane przez inne ściany dając w efekcie obraz trójwymiarowy.
• bazy danych - informacja przechowywana w bazie danych może wymagać różnego rodzaju uporządkowania, np. lista książek może być alfabetycznie porządkowana wg autorów lub tytułów, co znacznie ułatwia znalezienie określonej pozycji.

Artykuł ma na celu dokładne zapoznanie uczniów z podstawowymi algorytmami sortującymi, ich własnościami oraz umiejętnym doborem algorytmów sortujących dla danego zadania. Wbrew obiegowym opiniom nie ma "idealnego" i "uniwersalnego" algorytmu sortującego - jeden algorytm jest lepszy w jednej sytuacji, drugi w innej. Dlatego dokładna znajomość własności algorytmów sortujących pozwala na tworzenie naprawdę efektywnych aplikacji.

Z problemem sortowania powiązane są problemy wyszukiwania danych. Dlatego zapraszamy naszych czytelników do zapoznania się z artykułem o algorytmach wyszukujących.

Omawiane tematy są ilustrowane licznymi przykładami prostych programów, które uczeń może pobrać z naszej witryny, przeanalizować oraz uruchomić na swoim komputerze.

		Przykłady w języku Pascal zostały przetestowane w środowisku DevPascal - środowisko IDE firmy Bloodshed Software, które można zupełnie darmowo pobrać z Internetu. Aby uruchomić nasze przykłady, należy w środowisku DevPascal utworzyć aplikację konsoli, a następnie zaznaczyć na stronie WWW odpowiedni fragment obejmujący tekst programu, skopiować go do schowka Windows, wkleić do edytora DevPascala, skompilować i uruchomić. Dochodzą do nas sygnały, iż nie potraficie zainstalować poprawnie środowiska DevPascal. Dlatego podajemy poniżej dokładną procedurę instalacji: Pobierz z Internetu plik instalacyjny pakietu DevPascal na swój dysk twardy. Możesz skorzystać z witryny producenta lub w razie problemów z naszej kopii (która jednakże może być starszą wersją oprogramowania). Uruchom pobrany program i zainstaluj pakiet zgodnie z propozycją instalatora do katalogu c:\Dev-Pas\. Po instalacji wejdź do katalogu c:\Dev-Pas\ i zmień nazwę zawartego tam katalogu Icons na Icon. Następnie utwórz wewnątrz katalogu c:\Dev-Pas\ katalog Prj. Każdy nowy projekt umieszczaj w Prj w osobnym katalogu, np. p001, p002 itd. Dzięki temu unikniesz bałaganu na dysku i szybko odszukasz wszystkie pliki należące do projektu. Unikaj w nazwach katalogów znaku spacji - to ważne, w przeciwnym razie kompilator może nie odnaleźć potrzebnych mu plików i program wynikowy nie zostanie utworzony. Teraz jesteś gotowy do rozpoczęcia pracy ze środowiskiem DevPascal. Środowisko to jest tylko edytorem programów, które pracuje w środowisku graficznym Windows. Kompilacji dokonuje natomiast dołączony do niego kompilator FreePascal, który znajduje się w katalogu bin. Dlatego możesz również wejść do tego katalogu i uruchomić wewnętrzny edytor FreePascala o nazwie fp.exe. Jednakże nie polecamy tego rozwiązania - DevPascal jest wygodniejszy. Procedura tworzenia nowego projektu konsoli jest następująca: Uruchom edytor DevPascala. Z menu File wybierz opcję New. Z okienka dialogowego wybierz typ projektu - Console Application. Nadaj nazwę swojemu projektowi - w miarę możliwości bez spacji i bez polskich znaków, np. PR001, a następnie zapisz go na dysku w specjalnie do tego celu utworzonym katalogu projektowym wewnątrz wcześniej przygotowanego katalogu c:\Dev-Pas\Prj\. W nazwach katalogów unikaj spacji i polskich znaków. Po zapisaniu pliku projektu na dysku zostaje utworzony plik tekstu programu. Zapisz ten plik na dysku w tym samym katalogu, co plik projektu nadając mu nazwę np. PGR001 lub dowolną inną (unikaj spacji i polskich znaków). Wpisz w edytorze odpowiedni tekst programu. Skompiluj go. Jeśli nie ma błędów, uruchom program wynikowy. Nie zapisuj z poziomu DevPascala żadnych plików na dyskietce. Jeśli musisz utworzyć kopie, to zrób to poza środowiskiem DevPascala. Unikniesz wtedy różnych dziwnych sytuacji, z którymi borykają się nasi nieuważni uczniowie - autor stosuje te zasady od kilku lat i nie napotkał jeszcze żadnych problemów z pakietem DevPascal, o których informują go czytelnicy serwisu. Jedyna rada jest następująca: BACZ CO CZYNISZ, GDZIE CZYNISZ I JAK TO CZYNISZ! W razie problemów proszę skontaktować się z autorem artykułu.

		Przykłady w języku C++ uruchomiono w środowisku DevC++, które również jest dziełem firmy Bloodshed Software - zachęcamy do pobrania z Internetu tego darmowego oprogramowania. Aby uruchomić przykłady, należy w środowisku DevC++ utworzyć projekt aplikacji konsoli, a następnie zaznaczyć na stronie WWW odpowiedni fragment obejmujący tekst programu, skopiować go do schowka Windows, wkleić do edytora DevC++, skompilować i uruchomić. W razie problemów proszę skontaktować się z autorem artykułu. Jeśli masz kłopoty z pobraniem DevC++ z witryny firmowej, to spróbuj tutaj.

		Przykłady w języku Basic uruchomiono w środowisku FreeBasic - darmowy kompilator, który można ściągnąć z sieci Internet ze strony twórców tegoż programu lub też z naszego serwera. (istnieje również wersja dla systemu Linux). Ten pierwszy sposób jest lepszy, ponieważ otrzymujesz najnowszą wersję. Podane przykłady kopiujesz z naszych stron poprzez schowek do edytora FreeBasica, kompilujesz i uruchamiasz. Instalacja FreeBasica jest bardzo prosta: Pobrane archiwum zip rozpakuj do dowolnego katalogu (najlepiej do katalogu głównego na dysku C:/). Powstanie katalog FreeBasic. Wejdź do katalogu FreeBasic i uruchom plik install.bat, który zainstaluje wszystkie biblioteki. Kompilator jest gotowy. Jeśli dystrybucję pobrałeś z naszego serwera, to zawiera ona już edytor programów FBIDE.EXE i jest pakietem instalacyjnym, który automatycznie rozpakuje i zainstaluje wszystkie niezbędne pliki (Free Basic Integrated Developement Environment). Jeśli dystrybucję pobrałeś ze strony producenta, to posiadasz tylko kompilator FBC.EXE. Musisz zatem dodatkowo zainstalować edytor programów, aby wygodnie pracować z tym pakietem. Edytor poszukaj na sieci. Masz duży wybór.

		Przykłady w języku JavaScript można uruchomić nawet przy pomocy ogólnie dostępnego Notatnika z systemu Windows. Jednakże nie polecamy tego sposobu - my korzystaliśmy z programu Microsoft Frontpage. Aby uruchomić przykłady, należy zaznaczyć na stronie WWW fragment obejmujący tekst programu wraz z odpowiednim kodem HTML, skopiować go do schowka Windows, wkleić do notatnika lub edytora kodu html w programie FrontPage i zapisać na dysku pod dowolną nazwą z rozszerzeniem htm lub html (np. index.html). Tak utworzony plik możemy w dalszej kolejności uruchomić w dowolnej przeglądarce internetowej - najlepiej Internet Explorer. W razie problemów proszę skontaktować się z autorem artykułu.

Ponieważ dostaję dużo listów od nieuważnych czytelników, wyjaśniam, iż prezentowane programy są jedynie przykładami realizacji opisywanych algorytmów w wybranych językach programowania. W żadnym razie nie są one celem artykułu. Celem są ALGORYTMY. Znając algorytm można napisać dobry program w dowolnym języku programowania. Dla uzasadnienia mojej postawy przytoczę znany cytat profesora Donalda Knutha (jednego z największych współczesnych autorytetów w dziedzinie informatyki):

"Languages come and go, but algorithms stand the test of time" Donald Knuth

"Języki programowania pojawiają się i odchodzą, lecz algorytmy wytrzymują próbę czasu" Donald Knuth

Zbiór posortowany to taki, w którym kolejne elementy są poukładane w pewnym porządku (kolejności). Porządek ten możemy określić za pomocą relacji lub (albo dowolnej innej relacji porządkowej, która jednoznacznie wyznacza kolejność elementów w zbiorze). Równość jest konieczna w przypadku, gdy elementy zbioru mogą przyjmować takie same wartości. Na przykład zbiór liczb:

D = { 1, 3, 3, 5, 7, 7, 8, 9 }

jest posortowany rosnąco, ponieważ pomiędzy każdymi dwoma kolejnymi elementami zachodzi relacja:

element poprzedni jest mniejszy lub równy od elementu następnego

Odwrotnie, zbiór:

D = { 9, 8, 6, 6, 4, 2, 1, 1, 0 }

jest posortowany malejąco, ponieważ pomiędzy każdymi dwoma kolejnymi elementami zachodzi relacja:

element poprzedni jest większy lub równy od elementu następnego.

Oczywiście zbiór wcale nie musi składać się z liczb (chociaż tak naprawdę każdy rodzaj danych komputerowych w końcu sprowadza się do liczb, gdyż wewnętrznie jest reprezentowany przez kody binarne). W takim przypadku należy określić dla każdego elementu tzw. klucz (ang. key), wg którego dokonywane jest sortowanie. Ponieważ klucz jest liczbą, zatem obowiązują dla niego podane wyżej zasady kolejności elementów. Na przykład dla tekstów kluczem mogą być kody poszczególnych znaków. Większość języków programowania posiada operatory porównywania ciągu znaków (problemem może być sortowanie wg zasad języka polskiego - nie wystarczy wtedy porównywać kodów znakowych, ponieważ kody polskich literek ą, Ą, ć, Ć itd. są zwykle większe od kodów liter alfabetu łacińskiego, ale i ten problem daje się z powodzeniem rozwiązać przez odpowiedni dobór kluczy).

Przez sortowanie będziemy rozumieć taką zmianę kolejności elementów zbioru nieuporządkowanego (permutację), aby w wyniku spełniały one założony porządek.

Kolejnym zagadnieniem, które powinniśmy omówić we wstępie, jest tzw. czasowa złożoność obliczeniowa (ang. computational complexity) algorytmu sortującego (istnieje również złożoność pamięciowa). Określa ona statystycznie czas wykonywania algorytmu w zależności od liczby danych wejściowych. Czasowa złożoność obliczeniowa wyrażana jest liczbą tzw. operacji dominujących, czyli takich, które mają bezpośredni wpływ na czas wykonywania algorytmu. Dzięki takiemu podejściu uniezależniamy czasową złożoność obliczeniową od szybkości komputera, na którym dany algorytm jest realizowany. Złożoność obliczeniową charakteryzujemy przy pomocy tzw. notacji O (omikron). Oto odpowiednie przykłady:

O(n)	Algorytm o liniowej zależności czasu wykonania od ilości danych. Dwukrotny wzrost liczby przetwarzanych danych powoduje dwukrotny wzrost czasu wykonania. Tego typu złożoność powstaje, gdy dla każdego elementu należy wykonać stałą liczbę operacji.
O(n2)	Algorytm, w którym czas wykonania rośnie z kwadratem liczby przetwarzanych elementów. Dwukrotny wzrost liczby danych powoduje czterokrotny wzrost czasu wykonania. Tego typu złożoność powstaje, gdy dla każdego elementu należy wykonać ilość operacji proporcjonalną do liczby wszystkich elementów.
O(n log  n)	Dobre algorytmy sortujące mają taką właśnie złożoność obliczeniową. Czas wykonania przyrasta dużo wolniej od wzrostu kwadratowego. Tego typu złożoność powstaje, gdy zadanie dla n elementów można rozłożyć na dwa zadania zawierające po połowie elementów.
O(n!) O(an)	Bardzo pesymistyczne algorytmy, czas wykonania rośnie szybko ze wzrostem liczby elementów wejściowych, czyli znalezienie rozwiązania może zająć najszybszym komputerom całe wieki lub tysiąclecia. Takich algorytmów należy unikać jak ognia !

Zapis O( ) określamy mianem klasy złożoności obliczeniowej algorytmu. Klasa czasowej złożoności obliczeniowej umożliwia porównywanie wydajności różnych algorytmów sortujących. Z reguły proste algorytmy posiadają wysoką złożoność obliczeniową - długo dochodzą do wyniku końcowego. Algorytmy bardziej skomplikowane posiadają mniejszą złożoność obliczeniową - szybko dochodzą do rozwiązania. Złożoność obliczeniowa wszystkich algorytmów sortujących została dokładnie oszacowana - my również dokonujemy tego w niniejszym opracowaniu.

Załóżmy, iż mamy program sortujący dane zbudowany na bazie algorytmu sortującego o klasie złożoności obliczeniowej O(n²). Sto elementów jest sortowane w czasie 1 sekundy. Ile czasu zajmie posortowanie za pomocą tego programu zbioru o tysiącu elementach? Odpowiedź brzmi - 100 sekund. Ponieważ ilość danych wzrosła 10 razy, to czas obliczeń wzrósł 10², czyli 100 razy.  Poniżej przedstawiamy odpowiednią tabelkę.

Lp.	n	Czas obliczeń
1.	100	= 1 sekunda
2.	1.000	= 100 sekund = 1 minuta 40 sekund
3.	10.000	= 10.000 sekund = 2 godziny 46 minut 40 sekund
4.	100.000	= 1.000.000 sekund = 11 dni 13 godzin 46 minut 40 sekund
5.	1.000.000	= 100.000.000 sekund = 3 lata 2 miesiące 9 godzin 46 minut 40 sekund
6.	10.000.000	= 1 x 1010 sekund = 317 lat 1 miesiąc 4 dni 17 godzin 46 minut 40 sekund

Widzimy więc, iż algorytm ten spisuje się dobrze tylko przy niewielkiej liczbie elementów. Gdy liczba sortowanych elementów jest duża, czas oczekiwania na rozwiązanie może być nie do zaakceptowania. Dlatego właśnie informatycy poświęcili tak dużo swojego wysiłku na opracowanie odpowiednio szybkich algorytmów sortujących (te najszybsze mają klasę złożoności O(n log n) ).

Oprócz złożoności czasowej rozważa się również złożoność pamięciową. Określa ona ilość zasobów komputera, których wymaga dany algorytm w zależności od liczby danych wejściowych. Tutaj także ma zastosowanie notacja omikron. Przy określaniu złożoności algorytmu należy wziąć pod uwagę oba typy złożoności obliczeniowej.

Ze względu na złożoność pamięciową algorytmy sortujące dzielimy na dwie podstawowe grupy:

• Algorytmy sortujące w miejscu (ang. in place) - wymagają stałej liczby dodatkowych struktur danych, która nie zależy od liczby elementów sortowanego zbioru danych (ani od ich wartości). Dodatkowa złożoność pamięciowa jest zatem klasy O(1). Sortowanie odbywa się wewnątrz zbioru. Ma to bardzo istotne znaczenie w przypadku dużych zbiorów danych, gdyż mogłoby się okazać, iż posortowanie ich nie jest możliwe z uwagi na brak pamięci w systemie. Większość opisanych tu algorytmów sortuje w miejscu, co jest ich bardzo dużą zaletą.
• Algorytmy nie sortujące w miejscu - wymagają zarezerwowania w pamięci dodatkowych obszarów, których wielkość jest uzależniona od liczby sortowanych elementów lub od ich wartości. Tego typu algorytmy są zwykle bardzo szybkie w działaniu, jednakże okupione to jest dodatkowymi wymaganiami na pamięć. Zatem w pewnych sytuacjach może się okazać, iż taki algorytm nie będzie w stanie posortować dużego zbioru danych, ponieważ system komputerowy nie posiada wystarczającej ilości pamięci RAM.

Więcej informacji na temat klas złożoności obliczeniowej znajdziesz w artykule o liczbach pierwszych.

Algorytmy sortujące dzieli się również na dwie grupy:

• Algorytmy stabilne - zachowują kolejność elementów równych. Oznacza to, iż elementy o tych samych wartościach będą występowały w tej samej kolejności w zbiorze posortowanym, co w zbiorze nieposortowanym. Czasami ma to znaczenie, gdy sortujemy rekordy bazy danych i nie chcemy, aby rekordy o tym samym kluczu zmieniały względem siebie położenie.
• Algorytmy niestabilne - kolejność wynikowa elementów równych jest nieokreślona (zwykle nie zostaje zachowana).

W opracowaniu zbadamy prezentowane algorytmy sortujące pod kątem czasu sortowania. Otrzymane wyniki pozwolą nam wyciągnąć różne ciekawe wnioski oraz porównać efektywność opisywanych algorytmów przy sortowaniu tych samych zbiorów.

Każdy algorytm (z wyjątkiem Bogo Sort, co stanie się oczywiste dla każdego, kto się z nim zapozna) będzie sortował kolejno identyczne zbiory o liczebności 1000, 2000, 4000, 8000, 16000 elementów (dla algorytmów szybkich zmierzymy jeszcze czasy sortowań zbiorów o 32000, 64000 i 128000 elementów). Elementy zbioru będą liczbami rzeczywistymi.

W danej turze sortowania wyznaczymy następujące czasy:

tpo	-	czas sortowania zbioru posortowanego. Nie, to nie jest pomyłka. Pomiar tego czasu da nam odpowiedź, czy algorytm wykorzystuje fakt posortowania zbioru.
tod	-	czas sortowania zbioru uporządkowanego odwrotnie. To zwykle jest ciężki orzech do zgryzienia dla algorytmów, które w typowych warunkach radzą sobie całkiem sprawnie. Tego typu sytuacja występuje przy zmianie kierunku uporządkowania zbioru, który wcześniej został już posortowany.
tpp	-	czas sortowania zbioru uporządkowanego, w którym pierwszy element przyjmuje wartość losową. Wykonamy dziesięć sortowań dla każdego zbioru uśredniając wynik. Tego typu sytuacja występuje przy dodawaniu nowego elementu na początku zbioru już uporządkowanego.
tpk	-	czas posortowania zbioru uporządkowanego, w którym ostatni element przyjmuje wartość losową. Wykonamy dziesięć sortowań uśredniając wynik. Tego typu sytuacja występuje przy dodawaniu nowego elementu na końcu zbioru uporządkowanego.
tnp	-	czas posortowania zbioru z losowym rozkładem elementów. Wykonamy dziesięć sortowań uśredniając wynik. Ten czas poinformuje nas, jak dany algorytm radzi sobie w typowych warunkach.

Poniżej przedstawiamy program, który będzie stosowany do badań. Zastosowane w nim rozwiązania mogą się przydać również przy pomiarze czasu działania innych algorytmów.

Do pomiaru czasu wykorzystujemy dwie funkcje biblioteki Win32API operujące na tzw. sprzętowym liczniku wydajności. Licznik ten zlicza takty procesora i jest 64-bitowy. Jeśli komputer nie posiada takiego licznika, to funkcje zwracają wartość logiczną false.

QueryPerformanceFrequency(adres zmiennej 64-bitowej) - funkcja umieszcza w podanej zmiennej całkowitej 64-bitowej ilość taktów procesora na 1 sekundę.

QueryPerformanceCounter(adres zmiennej 64-bitowej) - funkcja umieszcza w podanej zmiennej całkowitej 64-bitowej stan licznika taktów procesora.

Zasada pomiaru czasu jest następująca:

...
uses Windows;

var
  qpf       : int64;    // ilość taktów procesora na sekundę
  qpc1,qpc2 : int64;    // stany liczników 64-bitowych
  tqpc      : int64;    // czas operacji odczytu czasu
  t         : extended; // czas w sekundach 
...
  if QueryPerformanceFrequency(addr(qpf)) then
  begin

  // kalibrujemy czas operacji pomiaru czasu

    QueryPerformanceCounter(addr(qpc1));
    QueryPerformanceCounter(addr(qpc2));
    tqpc := qpc2 - qpc1;
...
  // wykonujemy pomiar czasu
    QueryPerformanceCounter(addr(qpc1));

  // tutaj jest kod, którego czas pracy mierzymy

    QueryPerformanceCounter(addr(qpc2));
    t := (qpc2 - qpc1 - tqpc) / qpf; // czas w sekundach
...
  end
  else
    writeln('Na tym komputerze program testowy nie pracuje...');
...

 

// Program testujący czas sortowania dla
// danego algorytmu sortującego
//--------------------------------------
// (C)2005 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// w Tarnowie
//--------------------------------------

program TestCzasuSortowania;

uses Windows;

const
  NAZWA = 'Tutaj podajemy nazwe algorytmu';
  K1    = '----------------------------------------';
  K2    = '(C)2005 mgr J.Wałaszek   I LO w Tarnowie';
  K3    = '------n---------tpo---------tod---------tpp---------tpk---------tnp';
  K4    = '-------------------------------------------------------------------';
  MAX_LN = 8; // określa ostatnie LN
  LN : array[1..8] of integer = (1000,2000,4000,8000,16000,32000,64000,128000);

var
  d         : array[1..128000] of real; // sortowana tablica
  n         : integer;                  // liczba elementów
  qpf,tqpc  : int64;                    // dane dla pomiaru czasu
  qpc1,qpc2 : int64;

// Tutaj umieszczamy procedurę sortującą tablicę d
//------------------------------------------------
function Sort : extended;
begin
  QueryPerformanceCounter(addr(qpc1));

  QueryPerformanceCounter(addr(qpc2));
  Sort := (qpc2 - qpc1 - tqpc) / qpf;
end;

// Program główny
//---------------
var
  i,j,k               : integer;
  tpo,tod,tpp,tpk,tnp : extended;
  f                   : Text;
begin
  if QueryPerformanceFrequency(addr(qpf)) then
  begin
    QueryPerformanceCounter(addr(qpc1));
    QueryPerformanceCounter(addr(qpc2));
    tqpc := qpc2 - qpc1;

    assignfile(f,'wyniki.txt'); rewrite(f);

// Wydruk na ekran

    writeln('Nazwa: ',NAZWA);
    writeln(K1);
    writeln(K2);
    writeln;
    writeln(K3);

// Wydruk do pliku

    writeln(f,'Nazwa: ',NAZWA);
    writeln(f,K1);
    writeln(f,K2);
    writeln(f,'');
    writeln(f,K3);
    for i := 1 to MAX_LN do
    begin
      n := LN[i];

// Czas sortowania zbioru posortowanego

      for j := 1 to n do d[j] := j;
      tpo := Sort;

// Czas sortowania zbioru posortowanego odwrotnie

      for j := 1 to n do d[j] := n - j;
      tod := Sort;

// Czas sortowania zbioru posortowanego
// z przypadkowym elementem na początku - średnia z 10 obiegów

      tpp := 0;
      for j := 1 to 10 do
      begin
        for k := 1 to n do d[k] := k;
        d[1] := random * n + 1;
        tpp += Sort;
      end;
      tpp /= 10;

// Czas sortowania zbioru posortowanego
// z przypadkowym elementem na końcu - średnia z 10 obiegów

      tpk := 0;
      for j := 1 to 10 do
      begin
        for k := 1 to n do d[k] := k;
        d[n] := random * n + 1;
        tpk += Sort;
      end;
      tpk /= 10;

// Czas sortowania zbioru nieuporządkowanego - średnia z 10 obiegów

      tnp := 0;
      for j := 1 to 10 do
      begin
        for k := 1 to n do d[k] := random;
        tnp += Sort;
      end;
      tnp /= 10;

      writeln(n:7,tpo:12:6,tod:12:6,tpp:12:6,tpk:12:6,tnp:12:6);
      writeln(f,n:7,tpo:12:6,tod:12:6,tpp:12:6,tpk:12:6,tnp:12:6);
    end;
    writeln(K4);
    writeln(f,K4);
    writeln(f,'Koniec');
    closefile(f);
    writeln;
    writeln('Koniec. Wyniki w pliku WYNIKI.TXT');
  end
  else writeln('Na tym komputerze program testowy nie pracuje !');
  writeln;
  write('Nacisnij klawisz ENTER...'); readln;
end.

Bardzo duże znaczenie dla otrzymanych wyników ma środowisko, w którym program testowy będzie pracował. Aby usunąć obce wpływy mogące zakłócić wyniki, komputer pracuje w czystym systemie Windows XP z SP2 bez uruchomionych w tle procesów, z wyłączoną siecią oraz z wyłączonym oprogramowaniem antywirusowym. Parametry są następujące:

Środowisko pracy programu testującego
Element	Stan
Procesor	Intel Pentium Celeron 1,7GHz
RAM	512MB
System	Windows XP Professional SP 2
Sieć	Wyłączona
Inne programy	Wyłączone

Wynikiem działania programu będą odpowiednie czasy sortowania zbiorów, które zależą od użytego do doświadczeń sprzętu komputerowego - na twoim komputerze na pewno uzyskasz inne czasy. Co zatem będziemy badać?

Otóż dla każdego czasu określimy klasę czasowej złożoności obliczeniowej. Wg definicji (podanej w artykule o liczbach pierwszych) klasa czasowej złożoności obliczeniowej jest funkcją liczby elementów przetwarzanych przez algorytm o jak najprostszej postaci, do której jest proporcjonalny czas wykonania algorytmu (nie jest to definicja formalna!!!).

Jeśli pewien algorytm posiada czasową złożoność obliczeniową klasy O(n²), to czas wykonania algorytmu dla n elementów jest w przybliżeniu proporcjonalny do kwadratu n, czyli:

t(n) cn²

Jeśli podzielimy otrzymane czasy działania algorytmu przez n², to otrzymamy:

t(n)	c
n2

Co z tego wynika? To proste - jeśli dany algorytm ma rzeczywiście klasę złożoności obliczeniowej O(n²), to otrzymany iloraz jest w przybliżeniu taki sam dla wszystkich zmierzonych czasów. Wartość liczbowa stałej c jest dla nas zupełnie nieistotna (zależy ona od parametrów komputera, na którym uruchomiliśmy nasz program testowy). Ważne jest jedynie, aby dla kolejnych ilorazów miała ona taką samą wartość (z pewnym przybliżeniem, co jest chyba oczywiste).

Aby zatem określić klasę złożoności obliczeniowej, otrzymane w wyniku wykonania programu testowego czasy będziemy kolejno dzielić przez: n, n², n³ i nlogn, Do tego celu wykorzystamy prosty arkusz kalkulacyjny:

(Kliknij tutaj, aby pobrać plik arkusza Excel.)

Najpierw w kolumnie t(n) umieszczamy otrzymane czasy sortowania dla poszczególnych wartości n. W przykładzie kolumna zawiera już dane oznakowane kolorem fioletowym. Podane czasy arkusz podzieli w kolejnych kolumnach przez wielkości n, n², n³ i nlogn pobrane z kolumny n. Ponieważ wyniki są zwykle bardzo małe, a nas interesuje nie ich wartość liczbowa tylko to, czy są stałe w pewnych granicach czy też nie, arkusz wymnaża ilorazy przez podane u góry kolumny mnożniki tak dobrane, aby wyniki w kolumnie były dobrze czytelne (najlepiej większe od 1). Teraz wystarczy sprawdzić, w której kolumnie wyliczone ilorazy przyjmują w przybliżeniu stałą wartość. W przykładzie jest to kolumna O(n²). Zatem algorytm wykazuje klasę czasowej złożoności obliczeniowej O(n²).

Drugą badaną dziedziną będzie efektywność opisywanych algorytmów. Ponieważ wszystkie z nich posortują identyczne zbiory danych i wykonają się w tych samych warunkach oraz na tym samym sprzęcie komputerowym, to otrzymane czasy pozwolą nam zorientować się, który z algorytmów robi to najlepiej i policzyć względny wzrost prędkości działania:

Jeśli algorytm A₁ sortuje dany plik w czasie t₁ = 32 [s] a algorytm A₂ wykonuje to samo zadanie w czasie t₂ = 24 [s], to względny wzrost prędkości algorytmu A₂ w stosunku do A₁ wyraża się wzorem:

 

Wynika z tego, iż algorytm A₂ jest w tym konkretnym przypadku 1¹/₄ razy szybszy w stosunku do algorytmu A₁.

 

Na końcu artykułu przeprowadzimy podsumowanie otrzymanych wyników i wyciągniemy z nich odpowiednie wnioski.

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Źródło: mgr Jerzy Wałaszek