Login lub e-mail Hasło   

Algorytmy sortujące - sortowanie bąbelkowe

Odnośnik do oryginalnej publikacji: http://www.i-lo.tarnow.pl/edu/inf/alg/al(...)ex.html
Algorytm sortowania bąbelkowego jest jednym z najstarszych algorytmów sortujących. Można go potraktować jako ulepszenie opisanego w poprzednim rozdziale algorytmu sorto...
Wyświetlenia: 47.003 Zamieszczono 17/10/2006

 

Algorytm sortowania bąbelkowego jest jednym z najstarszych algorytmów sortujących. Można go potraktować jako ulepszenie opisanego w poprzednim rozdziale algorytmu sortowania naiwnego. Zasada działania opiera się na cyklicznym porównywaniu par sąsiadujących elementów i zamianie ich kolejności w przypadku niespełnienia kryterium porządkowego zbioru. Operację tę wykonujemy dotąd, aż cały zbiór zostanie posortowany.

Algorytm sortowania bąbelkowego przy porządkowaniu zbioru nieposortowanego ma klasę czasowej złożoności obliczeniowej równą O(n2). Sortowanie odbywa się w miejscu.


 

Jako przykład działania algorytmu sortowania bąbelkowego posortujemy przy jego pomocy 5-cio elementowy zbiór liczb {5 4 3 2 1}, który wstępnie jest posortowany w kierunku odwrotnym, co możemy uznać za przypadek najbardziej niekorzystny, ponieważ wymaga przestawienia wszystkich elementów.

Obieg Zbiór Opis operacji
1
 5 4 3 2 1 
Rozpoczynamy od pierwszej pary, która wymaga wymiany elementów
 4 5 2 1 
Druga para też wymaga zamiany elementów
 4 3 5 2 
Wymagana wymiana elementów
 4 3 2 5 1 
Ostatnia para również wymaga wymiany elementów
 4 3 2 1 5 
Stan po pierwszym obiegu. Zwróć uwagę, iż najstarszy element (5) znalazł się na końcu zbioru, a najmłodszy (1) przesunął się o jedną pozycję w lewo.
2
 4 3 2 1 5 
Para wymaga wymiany
 3 4 1 5 
Para wymaga wymiany
 3 2 4 1 
Para wymaga wymiany
 3 2 1 4 5 
Elementy są w dobrej kolejności, zamiana nie jest konieczna.
 3 2 1 4 5 
Stan po drugim obiegu. Zwróć uwagę, iż najmniejszy element (1) znów przesunął się o jedną pozycję w lewo. Z obserwacji tych można wywnioskować, iż po każdym obiegu najmniejszy element wędruje o jedną pozycję ku początkowi zbioru. Najstarszy element zajmuje natomiast swe miejsce końcowe.
3
 3 2 1 4 5 
Para wymaga wymiany
 2 3 1 4 5 
Para wymaga wymiany
 2 1 3 4 
Dobra kolejność
 2 1 3 4 5 
Dobra kolejność
 2 1 3 4 5 
Stan po trzecim obiegu. Wnioski te same.
4
 2 1 3 4 5 
Para wymaga wymiany
 1 2 3 4 5 
Dobra kolejność
 1 2 3 4 
Dobra kolejność
 1 2 3 4 5 
Dobra kolejność
 1 2 3 4 5 
Zbiór jest posortowany. Koniec

Posortowanie naszego zbioru wymaga 4 obiegów. Jest to oczywiste: w przypadku najbardziej niekorzystnym najmniejszy element znajduje się na samym końcu zbioru wejściowego. Każdy obieg przesuwa go o jedną pozycję w kierunku początku zbioru. Takich przesunięć należy wykonać n - 1 (n - ilość elementów w zbiorze).

Algorytm sortowania bąbelkowego, w przeciwieństwie do algorytmu sortowania naiwnego, nie przerywa porównywania par elementów po napotkaniu pary nie spełniającej założonego porządku. Po zamianie kolejności elementów sprawdzana jest kolejna para elementów sortowanego zbioru. Dzięki temu podejściu rośnie efektywność algorytmu oraz zmienia się klasa czasowej złożoności obliczeniowej z O(n3) na O(n2).

   
   
   

Algorytm sortowania bąbelkowego jest uważany za bardzo zły algorytm sortujący. Można go stosować tylko dla niewielkiej liczby elementów w sortowanym zbiorze (do około 5000). Przy większych zbiorach czas sortowania może być zbyt długi.

 
       

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, j - zmienne sterujące pętli, i, j N

krok 1: Dla j = 1,2,...,n - 1: wykonuj krok 2
krok 2:     Dla i = 1,2,...,n - 1: jeśli d[i] > d[i + 1], to zamień d[i] d[i + 1]
krok 3: Zakończ algorytm

Sortowanie wykonywane jest w dwóch zagnieżdżonych pętlach. Pętla zewnętrzna nr 1 kontrolowana jest przez zmienną j. Wykonuje się ona n - 1 razy. Wewnątrz pętli nr 1 umieszczona jest pętla nr 2 sterowana przez zmienną i. Wykonuje się również n - 1 razy. W efekcie algorytm wykonuje w sumie:

T1(n) = (n - 1)2 = n2 - 2n + 1

obiegów pętli wewnętrznej, po których zakończeniu zbiór zostanie posortowany.

Sortowanie odbywa się wewnątrz pętli nr 2. Kolejno porównywany jest i-ty element z elementem następnym. Jeśli elementy te są w złej kolejności, to zostają zamienione miejscami. W tym miejscu jest najważniejsza różnica pomiędzy algorytmem sortowania bąbelkowego a algorytmem sortowania naiwnego. Ten drugi w momencie napotkania elementów o złej kolejności zamienia je miejscami i rozpoczyna cały proces sortowania od początku. Algorytm sortowania bąbelkowego wymienia miejscami źle ułożone elementy sortowanego zbioru i przechodzi do następnej pary zwiększając indeks i o 1. Dzięki takiemu podejściu rośnie efektywność, co odzwierciedla klasa czasowej złożoności obliczeniowej:
Sortowanie naiwne - O(n3); Sortowanie bąbelkowe - O(n2)


   
   
   

Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.

 
       
Efekt uruchomienia programu

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

program Bubble_Sort_1;

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

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

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

var
i,j,x : integer;
begin
writeln(' Sortowanie babelkowe ');
writeln(' WERSJA NR 1 ');
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

for j := 1 to N - 1 do
for
i := 1 to N - 1 do
if
d[i] > d[i+1] then // Porządek rosnący
begin

x := d[i]; d[i] := d[i+1]; d[i+1] := x;
end;

// Wyświetlamy wynik sortowania

writeln('Po sortowaniu:'); writeln;
for i := 1 to N do write(d[i] : 4);
writeln;
writeln('Nacisnij Enter...');
readln;
end.

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

#include <cmath>
#include <iostream>
#include <iomanip>

using namespace std;

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

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

int main()
{
int d[N],i,j;

cout << " Sortowanie babelkowe\n"
" WERSJA NR 1\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

for(j = 0; j < N - 1; j++)
for(i = 0; i < N - 1; i++)
if(d[i] > d[i + 1]) swap(d[i], d[i + 1]);

// Wyświetlamy wynik sortowania

cout << "Po sortowaniu:\n\n";
for(i = 0; i < N; i++) cout << setw(4) << d[i];
cout << endl;
system("PAUSE"); return 0;
}

' Sortowanie Bąbelkowe - Wersja nr 1
'-------------------------------------------------
' (C)2005 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, i AS INTEGER, j AS INTEGER

PRINT
" Sortowanie babelkowe "
PRINT " WERSJA NR 1 "
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

FOR j = 1 TO N - 1
FOR i = 1 TO N - 1
IF d(i) > d(i+1) THEN SWAP d(i), d(i+1)
NEXT
NEXT


' Wyświetlamy wynik sortowania

PRINT "Po sortowaniu:"
PRINT
FOR
i = 1 TO N: PRINT USING "####"; d(i);: NEXT
PRINT
PRINT
"Nacisnij Enter..."
SLEEP
END

<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 1</h3>
<p style=
"TEXT-ALIGN: center">
(C)2005 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 1
//-------------------------------------------------
// (C)2005 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,j,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

for(j = 0; j < N - 1; j++)
for(i = 0; i < N - 1; i++)
if(d[i] > d[i + 1])
{
x = d[i]; d[i] = d[i + 1]; d[i + 1] = x;
};

// 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>
 

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

 

// 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 = 'Sortowanie bąbelkowe - Bubble Sort 1';
K1 = '-------------------------------------------';
K2 = '(C)2005 mgr J.Wałaszek I LO w Tarnowie';
K3 = '------n---------tpo---------tod---------tpp---------tpk---------tnp';
K4 = '-------------------------------------------------------------------';
MAX_LN = 5; // 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,j : integer;
x : real;
begin
QueryPerformanceCounter(addr(qpc1));
for j := 1 to n - 1 do
for
i := 1 to n - 1 do
if
d[i] > d[i+1] then // Porządek rosnący
begin

x := d[i]; d[i] := d[i+1]; d[i+1] := x;
end;
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 1
-------------------------------------------
(C)2005 mgr J.Wałaszek I LO w Tarnowie

------n---------tpo---------tod---------tpp---------tpk---------tnp
1000 0.007080 0.033954 0.008131 0.009170 0.021347
2000 0.025329 0.145372 0.025706 0.027021 0.086866
4000 0.096382 0.541764 0.102081 0.102371 0.347644
8000 0.414819 2.194081 0.418721 0.414379 1.401096
16000 1.672559 8.789338 1.679220 1.675513 5.628816
-------------------------------------------------------------------
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)

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

Cechy Algorytmu Sortowania Bąbelkowego
wersja nr 1
klasa złożoności obliczeniowej optymistyczna O(n2)
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:

  • optymistyczna - dla zbiorów uporządkowanych (z niewielką liczbą elementów nie na swoich miejscach) - na podstawie czasów tpo, tpp, tpk
  • typowa - dla zbiorów o losowym rozkładzie elementów - na podstawie czasu tnp
  • pesymistyczna - dla zbiorów posortowanych odwrotnie - na podstawie czasu tod.
Własności algorytmu
Algorytm tpo tod tpp tpk tnp
Sortowanie bąbelkowe
wersja nr 1
O(n2) O(n2) O(n2) O(n2) O(n2)
tpo   1 tod
5
tpo=tpp=tpk
tnp   2 tod
3
  1. Wszystkie badane przez nas czasy sortowania są proporcjonalne do kwadratu liczby elementów zbioru. Klasa czasowej złożoności obliczeniowej wynosi O(n2).
  2. Czasy sortowania tpo, tpp oraz tpk są praktycznie takie same.
  3. Czas sortowania zbioru nieuporządkowanego jest krótszy od czasu sortowania zbioru uporządkowanego odwrotnie.
Wzrost prędkości sortowania
Algorytmy tpo tod tpp tpk tnp
Sortowanie naiwne

Sortowanie bąbelkowe 1

  1
n
źle
  n
33
dobrze
  1
6
źle
  1
4
źle
  n
33
dobrze
  1. Porównując wzrost prędkości algorytmu sortowania bąbelkowego w stosunku do algorytmu sortowania naiwnego zauważamy, iż korzyść następuje w przypadku sortowania zbioru uporządkowanego odwrotnie oraz zbioru nieuporządkowanego. Wzrost prędkości jest proporcjonalny liniowo do liczby elementów w sortowanym zbiorze. W pozostałych przypadkach algorytm naiwny jest dużo szybszy od tej wersji algorytmu sortującego.

  1. Uzasadnij, iż wszystkie czasy dla tej wersji algorytmu są proporcjonalne do kwadratu liczby sortowanych elementów.

  2. Dlaczego czasy tpo, tpp oraz tpk są takie same?

  3. Uzasadnij wyniki otrzymane przy badaniu wzrostu prędkości algorytmu sortowania bąbelkowego w stosunku do algorytmu sortowania naiwnego.

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

Podobne artykuły


8
komentarze: 79 | wyświetlenia: 1153
111
komentarze: 32 | wyświetlenia: 60728
54
komentarze: 56 | wyświetlenia: 32590
54
komentarze: 68 | wyświetlenia: 31293
50
komentarze: 27 | wyświetlenia: 63526
49
komentarze: 18 | wyświetlenia: 64978
39
komentarze: 50 | wyświetlenia: 23278
39
komentarze: 30 | wyświetlenia: 28846
37
komentarze: 9 | wyświetlenia: 28520
36
komentarze: 37 | wyświetlenia: 23499
34
komentarze: 21 | wyświetlenia: 26317
32
komentarze: 12 | wyświetlenia: 26675
 
Autor
Artykuł




Brak wiadomości


Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska