Czy algorytm sortowania bąbelkowego można jeszcze ulepszyć? Tak, ale zaczynamy już osiągać kres jego możliwości, ponieważ ulepszenia polegają jedynie na redukcji operacji pustych. Wykorzystamy informację o miejscu wystąpienia zamiany elementów (czyli o miejscu wykonania operacji sortującej).

Jeśli w obiegu sortującym wystąpi pierwsza zamiana na pozycji i-tej, to w kolejnym obiegu będziemy rozpoczynali sortowanie od pozycji o jeden mniejszej (chyba że pozycja i-ta była pierwszą pozycją w zbiorze). Dlaczego? Odpowiedź jest prosta. Zamiana spowodowała, iż młodszy element znalazł się na pozycji i-tej. Ponieważ w obiegu sortującym młodszy element zawsze przesuwa się o 1 pozycję w kierunku początku zbioru, to nie ma sensu sprawdzanie pozycji od 1 do i-2, ponieważ w poprzednim obiegu zostały one już sprawdzone, nie wystąpiła na nich zamiana elementów, zatem elementy na pozycjach od 1 do i-2 są chwilowo w dobrej kolejności względem siebie. Nie mamy tylko pewności co do pozycji i-1-szej oraz i-tej, ponieważ ostatnia zamiana elementów umieściła na i-tej pozycji młodszy element, który być może należy wymienić z elementem na pozycji wcześniejszej, czyli i-1. W ten sposób określimy początkową pozycję, od której rozpoczniemy sortowanie elementów w następnym obiegu sortującym.

Ostatnia zamiana elementów wyznaczy pozycję końcową dla następnego obiegu. Wiemy, iż w każdym obiegu sortującym najstarszy element jest zawsze umieszczany na swojej docelowej pozycji. Jeśli ostatnia zamiana elementów wystąpiła na pozycji i-tej, to w następnym obiegu porównywanie elementów zakończymy na pozycji o 1 mniejszej - w ten sposób nie będziemy sprawdzać już najstarszego elementu z poprzedniego obiegu.

Sortowanie prowadzimy dotąd, aż w obiegu sortującym nie wystąpi ani jedna zamiana elementów.

Teoretycznie powinno to zoptymalizować algorytm, ponieważ są sortowane tylko niezbędne fragmenty zbioru - pomijamy obszary posortowane, które tworzą się na końcu i na początku zbioru. Oczywiście zysk nie będzie oszałamiający w przypadku zbioru nieuporządkowanego lub posortowanego odwrotnie (może się zdarzyć, iż ewentualne korzyści czasowe będą mniejsze od czasu wykonywania dodatkowych operacji). Jednakże dla zbiorów w dużym stopniu uporządkowanych możemy uzyskać całkiem rozsądny algorytm sortujący prawie w czasie liniowym O(n).

Przykład:

Według opisanej powyżej metody posortujmy zbiór { 0 1 2 3 5 4 7 9 }. W zbiorze tym są tylko dwa elementy nieuporządkowane - 5 i 4.

 0 1 2 3 5 4 7 9 

 0 1 2 3 5 4 7 9 

 0 1 2 3 5 4 7 9 

 0 1 2 3 5 4 7 9 

 0 1 2 3 5 4 7 9 

 0 1 2 3 4 5 7 9 

 0 1 2 3 4 5 7 9 

 0 1 2 3 4 5 7 9 

 0 1 2 3 4 5 7 9 

 0 1 2 3 4 5 7 9 

Chociaż podany przykład jest troszeczkę tendencyjny, to jednak pokazuje wyraźnie, iż zoptymalizowany algorytm sortowania bąbelkowego może bardzo szybko posortować zbiory prawie uporządkowane.

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Schemat blokowy

Tym razem wprowadzonych zmian do algorytmu sortowania bąbelkowego jest dużo, zatem opiszemy cały algorytm od początku.

Zmienna p_min przechowuje numer pozycji, od której rozpoczyna się sortowanie zbioru. W pierwszym obiegu sortującym rozpoczynamy od pozycji nr 1. Zmienna p_max przechowuje numer ostatniej pozycji do sortowania. Pierwszy obieg sortujący kończymy na pozycji n-1, czyli na przedostatniej.

Pętla numer 1 wykonywana jest dotąd, aż w wewnętrznej pętli nr 2 nie wystąpi żadna zamiana elementów. Zmienna p pełni w tej wersji algorytmu nieco inną rolę niż poprzednio. Mianowicie będzie przechowywała numer pozycji, na której algorytm ostatnio dokonał wymiany elementów. Na początku wpisujemy do p wartość 0, która nie oznacza żadnej pozycji w zbiorze. Zatem jeśli ta wartość zostanie zachowana, uzyskamy pewność, iż zbiór jest posortowany, ponieważ nie dokonano wymiany elementów.

Wewnętrzną pętlę sortującą rozpoczynamy od pozycji p_min. W pętli sprawdzamy kolejność elementu i-tego z elementem następnym. Jeśli kolejność jest zła, wymieniamy miejscami te dwa elementy. Po wymianie sprawdzamy, czy jest to pierwsza wymiana - zmienna p ma wtedy wartość 0. Jeśli tak, to numer pozycji, na której dokonano wymiany umieszczamy w p_min. Numer ten zapamiętujemy również w zmiennej p. Zwróć uwagę, iż dzięki takiemu podejściu p zawsze będzie przechowywało numer pozycji ostatniej wymiany - jest to zasada zwana "ostatni zwycięża".

Po sprawdzeniu elementów przechodzimy do następnej pozycji zwiększając i o 1 i kontynuujemy pętlę, aż do przekroczenia pozycji p_max. Wtedy pętla wewnętrzna zakończy się.

Jeśli w pętli nr 2 była dokonana zamiana elementów, to p_min zawiera numer pozycji pierwszej zamiany. Jeśli nie jest to pierwsza pozycja w zbiorze, p_min zmniejszamy o 1, aby pętla sortująca rozpoczynała od pozycji poprzedniej w stosunku do pozycji pierwszej zamiany elementów.

Pozycję ostatnią zawsze ustalamy o 1 mniejszą od numeru pozycji końcowej zamiany elementów.

Na koniec sprawdzamy, czy faktycznie doszło do zamiany elementów. Jeśli tak, to p jest większe od 0, gdyż zawiera numer pozycji w zbiorze, na której algorytm wymienił miejscami elementy. W takim przypadku pętlę nr 1 rozpoczynamy od początku. W przeciwnym razie kończymy, zbiór jest uporządkowany

W celach badawczych testujemy czas wykonania algorytmu sortowania bąbelkowego 4 w środowisku opisanym we wstępie. Program testujący jest następujący:

// 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 = 'Sortowanie bąbelkowe - Bubble Sort 4';
  K1    = '--------------------------------------------------';
  K2    = '(C)2011/2012 I Liceum Ogolnoksztalcace  w Tarnowie';
  K3    = '------n---------tpo---------tod---------tpp---------tpk---------tnp';
  K4    = '-------------------------------------------------------------------';
  MAX_LN = 6; // 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;
var
  i,p,pmin,pmax : integer;
  x             : real;
begin
  QueryPerformanceCounter(addr(qpc1));
  pmin := 1; pmax := N - 1;
  repeat
    p := 0;
    for i := pmin to pmax do
      if d[i] > d[i+1] then
      begin
        x := d[i]; d[i] := d[i+1]; d[i+1] := x;
        if p = 0 then pmin := i;
        p := i;
      end;
    if pmin > 1 then dec(pmin);
    pmax := p - 1;
  until p = 0;
  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.

Otrzymane wyniki są następujące (dla komputera o innych parametrach wyniki mogą się różnić co do wartości czasów wykonania, dlatego w celach porównawczych proponuję uruchomić podany program na komputerze czytelnika):

Nazwa: Sortowanie bąbelkowe - Bubble Sort 4
--------------------------------------------------
(C)2011/2012 I Liceum Ogolnoksztalcace  w Tarnowie

------n---------tpo---------tod---------tpp---------tpk---------tnp
   1000    0.000007    0.028411    0.000040    0.000026    0.019901
   2000    0.000013    0.120219    0.000080    0.000060    0.072574
   4000    0.000025    0.476896    0.000156    0.000094    0.286498
   8000    0.000051    1.906012    0.000222    0.000141    1.150969
  16000    0.000114    7.639477    0.000657    0.000420    4.593252
  32000    0.000280   30.786192    0.001275    0.000788   18.598717
-------------------------------------------------------------------
Koniec

(Arkusz kalkulacyjny Excel do wyznaczania klasy czasowej złożoności obliczeniowej)
(Arkusz kalkulacyjny Excel do wyznaczania wzrostu prędkości sortowania)

Analizując wyniki obliczeń w arkuszu kalkulacyjnym otrzymanych czasów sortowania dla algorytmu sortowania bąbelkowego 4 wyciągamy następujące wnioski:

Cechy Algorytmu Sortowania Bąbelkowego wersja nr 4
klasa złożoności obliczeniowej optymistyczna
klasa złożoności obliczeniowej typowa
klasa złożoności obliczeniowej pesymistyczna
Sortowanie w miejscu	TAK
Stabilność	TAK

Klasy złożoności obliczeniowej szacujemy następująco:

• optymistyczna - dla zbiorów uporządkowanych (z niewielką liczbą elementów nie na swoich miejscach) - na podstawie czasów t_po, t_pp, t_pk
• typowa - dla zbiorów o losowym rozkładzie elementów - na podstawie czasu t_np
• pesymistyczna - dla zbiorów posortowanych odwrotnie - na podstawie czasu t_od.
  

Własności algorytmu
Algorytm	tpo	tod	tpp	tpk	tnp
Sortowanie bąbelkowe wersja nr 4

1. Wprowadzona zmiana wpłynęła na zmianę klasy czasowej złożoności obliczeniowej przy sortowaniu zbioru uporządkowanego z losowym elementem na końcu z O(n²) na O(n).
2. Nie zmieniła się natomiast klasa czasowej złożoności obliczeniowej przy sortowaniu zbioru uporządkowanego odwrotnie i przy sortowaniu zbioru nieuporządkowanego. Dlatego w przypadku ogólnym klasa czasowej złożoności obliczeniowej wynosi O(n²).
3. Z wyników testu wyciągamy wniosek, iż ta wersja algorytmu sortowania bąbelkowego jest najlepszą ze wszystkich przedstawionych tutaj wersji. Dlatego dalsze algorytmy sortujące będziemy porównywali do wyników zoptymalizowanego algorytmu sortowania bąbelkowego.
   

Wzrost prędkości sortowania
Algorytmy	tpo	tod	tpp	tpk	tnp
Sortowanie bąbelkowe 3 Sortowanie bąbelkowe 4
	brak	brak	brak	dobrze	brak

3. Analizując wzrost prędkości algorytmu sortowania bąbelkowego w wersji 4 w stosunku do wersji 3 zauważamy, iż wprowadzona zmiana nie zwiększyła w istotny sposób prędkości działania algorytmu w przypadku ogólnym. Zysk jest tylko przy sortowaniu zbiorów w dużym stopniu uporządkowanych. W takich przypadkach zoptymalizowany algorytm sortowania bąbelkowego posiada liniową czasową złożoność obliczeniową.

1. Uzasadnij powód zmiany klasy czasowej złożoności obliczeniowej z O(n²) na O(n) w tej wersji algorytmu dla przypadku sortowania zbiorów w znacznym stopniu uporządkowanych.
2. Dlaczego w pozostałych przypadkach wzrost prędkości działania algorytmu jest niewielki?