Sortowanie bąbelkowe - wersja nr 4
           Bubble Sort


Podrozdziały     Tematy pokrewne

 

Algorytm

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.

 

Obieg Zbiór Opis operacji
1
 0 1 2 3 5 4 7 9 
Pierwszy obieg, rozpoczynamy od pierwszej pozycji.
 0 1 2 3 5 4 7 9 
Elementy w dobrej kolejności. Zamiana miejsc nie występuje.
 0 1 2 3 5 4 7 9 
 0 1 2 3 5 4 7 9 
 0 1 2 3 5 4 7 9 
Elementy w złej kolejności. Zapamiętujemy pozycję wymiany. Jest to jednocześnie pierwsza i ostatnia wymiana elementów w tym obiegu sortującym.
 0 1 2 3 4 5 7 9 
Elementy w dobrej kolejności. Zamiana miejsc nie występuje.
 0 1 2 3 4 5 7 9 
 0 1 2 3 4 5 7 9 
Koniec pierwszego obiegu. Zbiór jest już uporządkowany, ale ponieważ była zamiana elementów, algorytm dla pewności musi wykonać jeszcze jeden obieg sortujący.
2
 0 1 2 3 4 5 7 9 
Sortowanie rozpoczynamy od pozycji o 1 mniejszej od tej, na której wystąpiła w poprzednim obiegu wymiana elementów. Elementy są w dobrej kolejności. Dalszych sprawdzeń nie wykonujemy - kończymy na pozycji o 1 mniejszej, niż pozycja ostatniej zamiany w poprzednim obiegu.
 0 1 2 3 4 5 7 9 
Koniec, zbiór jest posortowany

 

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

n - liczba elementów w sortowanym zbiorze, n N
d[ ] - zbiór n-elementowy, który będzie sortowany. Elementy zbioru mają indeksy od 1 do n.

Dane wyjściowe

d[ ] - posortowany zbiór n-elementowy. Elementy zbioru mają indeksy od 1 do n.

Zmienne pomocnicze

i - zmienna sterująca pętli, i N
pmin - dolna granica pozycji sortowanych elementów,  pmin N
pmax - górna granica pozycji sortowanych elementów,  pmax N
p - numer pozycji zamiany elementów,  p N

 

Lista kroków

K01: pmin ← 1;  pmaxn - 1
K02 p ← 0
K03: Dla i = pmin, ..., pmax: wykonuj K04...K07
K04:     Jeśli d[i] ≤ d[i + 1], to następny obieg pętli K03
K05:     d[i] ↔ d[i + 1]
K06:     Jeśli p = 0, to pmin ← i
K07:     pi
K08: Jeśli pmin > 1, to pminpmin - 1
K09: pmaxp - 1
K10: Jeśli p > 0, to idź do K02
K11: Zakończ

 

Schemat blokowy

flow

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

Zmienna pmin przechowuje numer pozycji, od której rozpoczyna się sortowanie zbioru. W pierwszym obiegu sortującym rozpoczynamy od pozycji nr 1. Zmienna pmax 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 pmin. 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 pmin. 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 pmax. Wtedy pętla wewnętrzna zakończy się.

Jeśli w pętli nr 2 była dokonana zamiana elementów, to pmin zawiera numer pozycji pierwszej zamiany. Jeśli nie jest to pierwsza pozycja w zbiorze, pmin 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.

 

Programy

Efekt uruchomienia programu
Sortowanie babelkowe
     WERSJA NR 4
----------------------
(C)2005 Jerzy Walaszek

Przed sortowaniem:

  18   5   9  51  20  65  75  32  84  98  77  42   0  30   5  44  97  77  31  12

Po sortowaniu:

   0   5   5   9  12  18  20  30  31  32  42  44  51  65  75  77  77  84  97  98

 

DevPascal
// Sortowanie Bąbelkowe - Wersja nr 4
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

program Bubble_Sort_4;

const N = 20; // Liczebność zbioru.

var
  d : array[1..N] of integer;

// Program główny
//---------------

var
   i,p,pmin,pmax,x : integer;
begin
  writeln(' Sortowanie babelkowe ');
  writeln('     WERSJA  NR 4     ');
  writeln('----------------------');
  writeln('(C)2005 Jerzy Walaszek');
  writeln;

// Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi
// a następnie wyświetlamy jej zawartość

  randomize;
  for i := 1 to N do d[i] := random(100);
  writeln('Przed sortowaniem:'); writeln;
  for i := 1 to N do write(d[i] : 4);
  writeln;

// Sortujemy

  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;

// Wyświetlamy wynik sortowania

  writeln('Po sortowaniu:'); writeln;
  for i := 1 to N do write(d[i] : 4);
  writeln;
  writeln('Nacisnij Enter...');
  readln;
end.
Code::Blocks
// Sortowanie Bąbelkowe - Wersja nr 4
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

#include <cmath>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

const int N = 20; // Liczebność zbioru.

// Program główny
//---------------

int main()
{
  int d[N],i,p,pmin,pmax;
  
  cout << " Sortowanie babelkowe\n"
          "     WERSJA NR 4\n"
          "----------------------\n"
          "(C)2005 Jerzy Walaszek\n\n"
          "Przed sortowaniem:\n\n";

// Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi
// a następnie wyświetlamy jej zawartość

  srand((unsigned)time(NULL));

  for(i = 0; i < N; i++) d[i] = rand() % 100;
  for(i = 0; i < N; i++) cout << setw(4) << d[i];
  cout << endl;

// Sortujemy

  pmin = 0; pmax = N - 1;
  do
  {
    p = -1;
    for(i = pmin; i < pmax; i++)
      if(d[i] > d[i+1])
      {
        swap(d[i], d[i+1]);
        if(p < 0) pmin = i;
        p = i;
      }
    if(pmin) pmin--;
    pmax = p;
  } while(p >= 0);

// Wyświetlamy wynik sortowania

  cout << "Po sortowaniu:\n\n";
  for(i = 0; i < N; i++) cout << setw(4) << d[i];
  cout << endl;
  return 0;
}
Free Basic
' Sortowanie Bąbelkowe - Wersja nr 4
'--------------------------------------------------------
' (C)2012 mgr Jerzy Wałaszek
' I Liceum Ogólnokształcące
' im. K. Brodzińskiego
' w Tarnowie
'--------------------------------------------------------

  OPTION EXPLICIT

  CONST N = 20 ' Liczebność zbioru.

  DIM d(1 TO N) AS INTEGER
  DIM i AS INTEGER, p AS INTEGER, pmin AS INTEGER, pmax AS INTEGER

  PRINT " Sortowanie babelkowe "
  PRINT "     WERSJA  NR 4     "
  PRINT "----------------------"
  PRINT "(C)2005 Jerzy Walaszek"
  PRINT

' Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi
' a następnie wyświetlamy jej zawartość

  RANDOMIZE TIMER
  FOR i = 1 TO N: d(i) = INT(RND * 100): NEXT
  PRINT "Przed sortowaniem:"
  PRINT
  FOR i = 1 TO N: PRINT USING "####"; d(i);: NEXT
  PRINT

' Sortujemy

  pmin = 1: pmax = N - 1
  DO
    p = 0
    FOR i = pmin TO pmax
      IF d(i) > d(i+1) THEN
        SWAP d(i), d(i+1)
        IF p = 0 THEN pmin = i
        p = i
      END IF
    NEXT
    IF pmin > 1 THEN pmin = pmin - 1
    pmax = p - 1
  LOOP UNTIL p = 0

' Wyświetlamy wynik sortowania

  PRINT "Po sortowaniu:"
  PRINT
  FOR i = 1 TO N: PRINT USING "####"; d(i);: NEXT
  PRINT
  PRINT "Nacisnij Enter..."
  SLEEP
  END
JavaScript
<html>
  <head>
  </head>
  <body>
    <form style="BORDER-RIGHT: #ff9933 1px outset;
                 PADDING-RIGHT: 4px; BORDER-TOP: #ff9933 1px outset;
                 PADDING-LEFT: 4px; PADDING-BOTTOM: 1px;
                 BORDER-LEFT: #ff9933 1px outset; PADDING-TOP: 1px;
                 BORDER-BOTTOM: #ff9933 1px outset;
                 BACKGROUND-COLOR: #ffcc66" name="frmbubblesort">
      <h3 style="text-align: center">Sortowanie Bąbelkowe - wersja nr 4</h3>
      <p style="TEXT-ALIGN: center">
        (C)2012 mgr Jerzy Wałaszek - I LO w Tarnowie
      </p>
      <hr>
      <p style="TEXT-ALIGN: center">
        <input onclick="main()" type="button" value="Sortuj" name="B1">
      </p>
      <p id="t_out" style="TEXT-ALIGN: center">...</p>
    </form>

<script language=javascript>

// Sortowanie Bąbelkowe - wersja nr 4
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

var N = 20; // Liczebność zbioru.

function main()
{
  var d = new Array(N);
  var i,p,pmin,pmax,x,t;

  // Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi

  for(i = 0; i < N; i++) d[i] = Math.floor(Math.random() * 100);
  t = "Przed sortowaniem:<BR><BR>";
  for(i = 0; i < N; i++) t += d[i] + " ";
  t += "<BR><BR>";

  // Sortujemy

  pmin = 0; pmax = N - 1;
  do
  {
    p = -1;
    for(i = pmin; i < pmax; i++)
      if(d[i] > d[i+1])
      {
        x = d[i]; d[i] = d[i+1]; d[i+1] = x;
        if(p < 0) pmin = i;
        p = i;
      };
    if(pmin) pmin--;
    pmax = p;
  } while(p >= 0);

  // Wyświetlamy wynik sortowania

  t += "Po sortowaniu:<BR><BR>";
  for(i = 0; i < N; i++) t += d[i] + " ";
  document.getElementById("t_out").innerHTML = t;
}

</script> 

  </body>
</html>

 

Tutaj możesz przetestować działanie prezentowanego skryptu:

Sortowanie Bąbelkowe - wersja nr 4

(C)2012 mgr Jerzy Wałaszek - I LO w Tarnowie


...

 

Einstein
DLA
GENIUSZA

Badania algorytmów sortowania

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

 

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 = '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):

 

Zawartość pliku wygenerowanego przez program
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

Objaśnienia oznaczeń (wszystkie czasy podano w sekundach):

n -  ilość elementów w sortowanym zbiorze
tpo -  czas sortowania zbioru posortowanego
tod -  czas sortowania zbioru posortowanego malejąco
tpp -  czas sortowania zbioru posortowanego z losowym elementem na początku
tpk -  czas sortowania zbioru posortowanego z losowym elementem na końcu
tnp -  czas sortowania zbioru z losowym rozkładem elementów

(Arkusz kalkulacyjny Excel do wyznaczania klasy czasowej złożoności obliczeniowej)

(Arkusz kalkulacyjny Excel do wyznaczania wzrostu prędkości sortowania)

Podsumowanie

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 O(n)
klasa złożoności obliczeniowej typowa O(n2)
klasa złożoności obliczeniowej pesymistyczna O(n2)
Sortowanie w miejscu TAK
Stabilność TAK

 

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

Własności algorytmu
Algorytm tpo tod tpp tpk tnp
Sortowanie bąbelkowe
wersja nr 4
O(n) O(n2) O(n) O(n) O(n2)
tpo << tod
tpp    5 tpk
3
tnp ≈   3 tod
5
  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(n2) 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(n2).
  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

≈   1
≈   1
≈   1
≈   0,08n
≈   1
brak brak brak dobrze brak
  1. 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ą.

Zadania dla ambitnych

  1. Uzasadnij powód zmiany klasy czasowej złożoności obliczeniowej z O(n2) 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?

Zobacz również na: Wersję 1 | Wersję 2 | Wersję 3 | Dwukierunkowe sortowanie bąbelkowe

 



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.