Wstęp


Podrozdziały
Uwagi na temat języków programowania
Porządek w zbiorze
Kryterium uporządkowania zbioru
Czasowa złożoność obliczeniowa
Badania algorytmów sortujących

 

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:

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.

 

Uwagi na temat języków programowania

Prezentowane w artykule algorytmy wzbogaciliśmy o proste przykłady programów utworzonych w poniższych środowiskach programowania::

Dev-Pascal

Code::Blocks (C++)

FreeBasic

JavaScript

Wszystkie są darmowo dostępne poprzez sieć Internet. Programy nie są celem artykułu, lecz jedynie dodatkiem do niego. Podstawą jest zawsze algorytm, który w artykule zostaje dokładnie omówiony. Dlatego programy dokładnie odzwierciedlają dany algorytm i nie stosujemy w nich różnych "sztuczek", które mają na celu poprawę efektywności.

 

Porządek w zbiorze

Zbiór posortowany to taki zbiór, 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.

 

Czasowa złożoność obliczeniowa

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.


Przykład:

Załóżmy, iż mamy program sortujący dane zbudowany na bazie algorytmu sortującego o klasie złożoności obliczeniowej O(n2). 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ł 102, 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 dzieli się również na dwie grupy:

Einstein
DLA
GENIUSZA

Badania algorytmów sortowania

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 zawierające 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:

 

DevPascal
...

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...');
    ...

 

DevPascal
// Program testujący czas sortowania dla
// danego algorytmu sortującego
//--------------------------------------
// (C)2012 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.Walaszek 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!!!).

 

Przykład:

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

 

t(n) cn2

n  - liczba przetwarzanych elementów
t(n)  - czas przetwarzania n-elementów w algorytmie
c  - stała proporcjonalności pomiędzy t(n) a n2

 

Jeśli podzielimy otrzymane czasy działania algorytmu przez n2, 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(n2), 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, n2, n3 i n·logn, Do tego celu wykorzystamy prosty arkusz kalkulacyjny:

 

    mnożnik: 1,00E+03 1,00E+06 1,00E+12 1,00E+04
Lp n t(n) O(n)? O(n2)? O(n3)? O(nlogn)?
1 1000 1,057523 1,06 1,06 1057,52 1,06
2 2000 4,117282 2,06 1,03 514,66 1,88
3 4000 15,921192 3,98 1,00 248,77 3,33
4 8000 61,238923 7,65 0,96 119,61 5,90
5 16000 258,838272 16,18 1,01 63,19 11,58
6 32000 1032,526252 32,27 1,01 31,51 21,56
7 64000 4120,517722 64,38 1,01 15,72 40,33
8 128000 16452,586878 128,54 1,00 7,85 75,76
    Średnio: 32,014 1,009 257,353 20,175

(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, n2, n3 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(n2). Zatem algorytm wykazuje klasę czasowej złożoności obliczeniowej O(n2).

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:

 

Przykład:

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

pic

Wynika z tego, iż algorytm A2 jest w tym konkretnym przypadku 11/4 razy szybszy w stosunku do algorytmu A1.

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

Zapraszam do lektury
mgr Jerzy Wałaszek

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

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