Autor artykułu: mgr Jerzy Wałaszek, Wersja 4.1
©2011 mgr Jerzy Wałaszek
I LO w Tarnowie
|
Wyjście Spis treści Poprzedni Następny
Autor artykułu: mgr Jerzy Wałaszek, Wersja 4.1 |
©2011 mgr Jerzy Wałaszek
|
| Podrozdziały | Tematy pokrewne | ||
Algorytm sortowania bąbelkowego wykonuje dwa rodzaje operacji:
- test bez zamiany miejsc elementów
- test ze zamianą miejsc elementów.
Pierwsza z tych operacji nie sortuje zbioru, jest więc operacją pustą. Druga operacja dokonuje faktycznej zmiany porządku elementów, jest zatem operacją sortującą.
Ze względu na przyjęty sposób sortowania algorytm bąbelkowy zawsze musi wykonać tyle samo operacji sortujących. Tego nie możemy zmienić. Jednakże możemy wpłynąć na eliminację operacji pustych. W ten sposób usprawnimy działanie algorytmu.
Jeśli dokładnie przyjrzałeś się wersjom 1 i 2, które prezentowaliśmy w poprzednich rozdziałach, to powinieneś dokonać następujących spostrzeżeń:
Możliwa jest dalsza redukcja operacji pustych, jeśli będziemy sprawdzać, czy w pętli wewnętrznej były przestawiane elementy (czyli czy wykonano operacje sortujące). Jeśli nie, to zbiór jest już posortowany (dlaczego?) i możemy zakończyć pracę algorytmu.
Teraz rośnie trudność wyznaczenia czasowej złożoności
obliczeniowej, ponieważ ilość faktycznie wykonywanych operacji porównań i
przestawień zależy od rozkładu elementów w sortowanym zbiorze. Zadanie komplikuje
dodatkowo fakt, iż operacja pusta jest zwykle wykonywana kilkakrotnie szybciej od
operacji sortującej. Na pewno można powiedzieć, iż dla zbioru posortowanego algorytm
wykona tylko
Przykład:
Posortujmy zbiór
| Obieg | Zbiór | Opis operacji |
|---|---|---|
| 1 |
3 1 0 7 9 |
Konieczne przestawienie elementów |
1 3 0 7 9
|
Konieczne przestawienie elementów | |
1 0 3 7 9
|
Elementy w dobrej kolejności | |
1 0 3 7 9
|
Elementy w dobrej kolejności | |
1 0 3 7 9
|
Koniec pierwszego obiegu. Ponieważ były przestawienia elementów, sortowanie kontynuujemy | |
| 2 |
1 0 3 7 9 |
Konieczne przestawienie elementów |
0 1 3 7 9 |
Elementy w dobrej kolejności | |
0 1 3 7 9 |
Elementy w dobrej kolejności | |
0 1 3 7 9
|
Koniec drugiego obiegu. Było przestawienie elementów, zatem sortowanie kontynuujemy | |
| 3 |
0 1 3 7 9 |
Elementy w dobrej kolejności |
0 1 3 7 9 |
Elementy w dobrej kolejności | |
0 1 3 7 9
|
Koniec trzeciego obiegu. Nie było przestawień elementów, kończymy sortowanie. Wykonaliśmy o 1 obieg sortujący mniej. |
| 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. |
| d[ ] | - posortowany zbiór n-elementowy. Elementy zbioru mają indeksy od 1 do n. |
| i, j | - zmienne sterujące pętli, i, j Î N |
| p | - znacznik zamiany miejsc elementów w zbiorze. p
N |
| K01: | Dla j = n - 1, n - 2, ..., 1: wykonuj K02...K04 |
| K02: | p ← 1 |
| K03: | Dla i = 1, 2, ..., j: jeśli d[i] > d[i + 1], to d[i] ↔ d[i + 1]; p ← 0 |
| K04: | Jeśli p = 1, to zakończ |
| K05: | Zakończ |
Wprowadzona do algorytmu sortowania bąbelkowego modyfikacja ma na celu wykrycie posortowania zbioru. Zmiany zaznaczyliśmy blokami o odmiennym kolorze.
Zbiór będzie posortowany, jeśli po wykonaniu wewnętrznego obiegu sortującego nie wystąpi ani jedno przestawienie elementów porządkowanego zbioru.
Przed wejściem do pętli sortującej nr 2 ustawiamy zmienną pomocniczą p. Jeśli w pętli zajdzie potrzeba przestawienia elementów, to zmienna p jest zerowana. Po wykonaniu pętli sortującej sprawdzamy, czy zmienna p jest ustawiona. Jeśli tak, to przestawienie elementów nie wystąpiło, zatem kończymy algorytm. W przeciwnym razie wykonujemy kolejny obieg pętli nr 1.
| Uwaga techniczna:
Zmienna p powinna być typu liczbowego integer,
a nie boolean (chociaż tak może wydawać się właściwiej). Jednakże musimy
pamiętać, iż procesory Pentium są zoptymalizowane na liczby |
| Efekt uruchomienia programu |
|---|
|
Sortowanie babelkowe WERSJA NR 3 ---------------------- (C)2005 Jerzy Walaszek Przed sortowaniem: 31 17 26 0 42 61 24 89 56 72 92 66 91 13 74 88 10 90 68 25 Po sortowaniu: 0 10 13 17 24 25 26 31 42 56 61 66 68 72 74 88 89 90 91 92 |
| DevPascal |
// Sortowanie Bąbelkowe - Wersja nr 3
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------
program Bubble_Sort_3;
const N = 20; // Liczebność zbioru.
var
d : array[1..N] of integer;
// Program główny
//---------------
var
i,j,p,x : integer;
begin
writeln(' Sortowanie babelkowe ');
writeln(' WERSJA NR 3 ');
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 := N - 1 downto 1 do
begin
p := 1;
for i := 1 to j do
if d[i] > d[i+1] then
begin
x := d[i]; d[i] := d[i+1]; d[i+1] := x;
p := 0;
end;
if p = 1 then break;
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.
|
|---|---|
| Code::Blocks |
// Sortowanie Bąbelkowe - Wersja nr 3
//--------------------------------------------------------
// (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,j,p;
cout << " Sortowanie babelkowe\n"
" WERSJA NR 3\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 = N - 1; j > 0; j--)
{
p = 1;
for(i = 0; i < j; i++)
if(d[i] > d[i + 1])
{
swap(d[i], d[i + 1]);
p = 0;
}
if(p) break;
}
// 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 3
'--------------------------------------------------------
' (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, i AS INTEGER, j AS INTEGER, p AS INTEGER
PRINT " Sortowanie babelkowe "
PRINT " WERSJA NR 3 "
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 = N - 1 TO 1 STEP -1
p = 1
FOR i = 1 TO j
IF d(i) > d(i+1) THEN
SWAP d(i), d(i+1)
p = 0
END IF
NEXT
IF p = 1 THEN EXIT FOR
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
|
| 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 3</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 3
//--------------------------------------------------------
// (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,j,p,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 = N - 1; j > 0; j--)
{
p = 1;
for(i = 0; i < j; i++)
if(d[i] > d[i + 1])
{
x = d[i]; d[i] = d[i + 1]; d[i + 1] = x;
p = 0;
}
if(p) break;
}
// 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:
|
|
W celach badawczych testujemy czas wykonania algorytmu sortowania bąbelkowego 3 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 3';
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,j,p : integer;
x : real;
begin
QueryPerformanceCounter(addr(qpc1));
for j := n - 1 downto 1 do
begin
p := 1;
for i := 1 to j do
if d[i] > d[i+1] then
begin
x := d[i]; d[i] := d[i+1]; d[i+1] := x;
p := 0;
end;
if p = 1 then break;
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 3 Objaśnienia oznaczeń (wszystkie czasy podano w sekundach):
|
(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 3 wyciągamy następujące wnioski:
| Cechy Algorytmu Sortowania Bąbelkowego wersja nr 3 |
|
|---|---|
| klasa złożoności obliczeniowej optymistyczna | O(n) -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:
| Własności algorytmu | ||||||||
|---|---|---|---|---|---|---|---|---|
| Algorytm | tpo | tod | tpp | tpk | tnp | |||
| Sortowanie
bąbelkowe wersja nr 3 |
O(n) | O(n2) | O(n) | O(n2) | O(n2) | |||
| tpo << tod | tpp << tpk |
|
||||||
| Wzrost prędkości sortowania | ||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Algorytmy | tpo | tod | tpp | tpk | tnp | |||||||||||||
| Sortowanie
bąbelkowe 2 Sortowanie bąbelkowe 3 |
|
|
|
|
|
|||||||||||||
| dobrze | brak | dobrze | dobrze | brak | ||||||||||||||
Zobacz również na: Wersję 1 | Wersję 2 | Wersję 4 | Dwukierunkowe sortowanie bąbelkowe
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 |
