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

• Pascal (Lazarus)
• C++ (Code::Blocks)
• Basic (FreeBasic)
• JavaScript (skrypt zwykle w kodzie strony)
• Python (dodatek w 2026)

Wszystkie są darmowo dostępne w sieci 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ę ich efektywności. Pamiętaj, iż artykuł ten jest głównie przeznaczony dla zdolnego ucznia szkoły ponadpodstawowej i nie spełnia wymogów publikacji akademickiej.

Zbiór uporządkowany (ang. ordered set) to taki, w którym elementy występują w określonym porządku, czyli kolejności. Jeśli elementy są liczbami, to porządek może być:

• rosnący - każdy następny element zbioru jest większy od swojego poprzednika. W zbiorze nie ma elementów równych. Taki porządek nazywamy porządkiem mocnym.
  Np. {0 2 4 7 12 13 16 74 125 200 333 ...}
• malejący - każdy następny element jest mniejszy od swojego poprzednika. W zbiorze nie ma elementów równych - porządek mocny.
  Np. (100 96 64 32 15 10 8 4 2 -4 -9 -22 ... }
• niemalejący - każdy następny element jest równy lub większy od swojego poprzednika. Elementy o tych samych wartościach mogą występować wielokrotnie obok siebie. Taki porządek nazywamy porządkiem słabym.
  Np. { 1 1 1 3 4 4 5 8 12 12 12 33 40 ... }
• nierosnący - każdy następny element jest równy lub mniejszy od swojego poprzednika. Elementy o tych samych wartościach mogą się powtarzać - porządek słaby.
  Np. {100 95 75 75 40 23 12 12 12 7 6 4 2 2 1 1 1 ... }

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 - memory complexity). 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:

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(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ę.

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:

W artykule 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:

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.

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)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 (oryginał artykułu powstał dosyć dawno, w tym czasie dysponowałem takim właśnie sprzętem, program testowy działa również w nowszych systemach Windows) bez uruchomionych w tle procesów, z wyłączoną siecią oraz z wyłączonym oprogramowaniem antywirusowym. Parametry są następujące:

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(n²), to czas wykonania algorytmu dla n elementów jest w przybliżeniu proporcjonalny do kwadratu n, czyli:

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

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 n·logn, Do tego celu wykorzystamy prosty arkusz kalkulacyjny:

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 n·log(n) 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:

Przykład:

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.

Zapraszam do lektury
mgr Jerzy Wałaszek