Algorytmy Sortujące - Sortowanie Bąbelkowe I

Algorytm sortowania bąbelkowego jest jednym z najstarszych algorytmów sortujących. Można go potraktować jako ulepszenie opisanego w poprzednim rozdziale algorytmu sortowania głupiego. 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(n²). Sortowanie odbywa się w miejscu.

Przykład:

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 3 2 1	Druga para też wymaga zamiany elementów
	4 3 5 2 1	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 2 1 5	Para wymaga wymiany
	3 2 4 1 5	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 5	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 5	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 głupiego, 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(n³) na O(n²).

Uwaga:

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.

do podrozdziału do strony

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

Lista kroków

K01:	Dla j = 1,2,...,n - 1: Wykonuj krok K02
K02:	Dla i = 1,2,...,n - 1: Jeśli d[i] > d[i + 1], to d[i] ↔ d[i + 1]
K03:	Zakończ

Schemat blokowy

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:

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 głupiego. 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 głupie - O(n³); Sortowanie bąbelkowe - O(n²).

do podrozdziału do strony

C++

//   Sortowanie Bąbelkowe I
//---------------------------
// (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;
  
  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;
}

Pascal

//   Sortowanie Bąbelkowe I
//---------------------------
// (C)2012 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;
  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;
  writeln('Nacisnij Enter...');
  readln;
end.

Basic

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

CONST N = 20 ' Liczebność zbioru.

DIM AS INTEGER d(1 TO N), i, j

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
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
PRINT "Nacisnij Enter..."
SLEEP
END

Python (dodatek)

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

import random

n = 20 # Liczebność zbioru.

# sortowany zbiór
d = [random.randrange(100) for i in range(n)]

print(" Sortowanie bąbelkowe ")
print("     WERSJA  NR 1     ")
print("----------------------")
print("(C)2026 Jerzy Walaszek")
print()

# Wyświetlamy zbiór
print("Przed sortowaniem:")
print()
for i in range(n):
    print("%4d" % (d[i]),end="")
print()
print()

# Sortujemy
for j in range(n-1):
    for i in range(n-1):
        if d[i] > d[i+1]:
            d[i],d[i+1] = d[i+1],d[i]

# Wyświetlamy wynik sortowania
print("Po sortowaniu:")
print()
for i in range(n):
    print("%4d" % (d[i]),end="")
print()
print()
input("Naciśnij Enter...")

Wynik:

 Sortowanie bąbelkowe 
     WERSJA  NR 1     
----------------------
(C)2026 Jerzy Walaszek

Przed sortowaniem:

  63   2   0  70  95   2  50  78  86  17   5  56  33  18  11  21   3  89  76  80

Po sortowaniu:

   0   2   2   3   5  11  17  18  21  33  50  56  63  70  76  78  80  86  89  95

Naciśnij Enter...

JavaScript

<html>
  <head>
  </head>
  <body>

<div style="overflow-x: auto;"
     align="center">
  <table
  border="0"
  cellpadding="4"
  style="border-collapse:
         collapse">
    <tr>
      <td nowrap>
        <form
        name="frm"
        style="text-align:
               center;
               background-color:
               #E7E7DA">
          <b>
          Sortowanie Bąbelkowe I
          </b><br/>
          &nbsp;&nbsp;(C)2026
          mgr Jerzy Wałaszek
          &nbsp;&nbsp;
          <hr/>
          <input
          onclick="main()"
          value="Sortuj"
          name="B1"
          type="button">
          <hr/>
          <div id="out">.</div>
        </form>
      </td>
    </tr>
  </table>
</div>

<script type="text/javascript"
language="javascript">

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

var N = 20;

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] + " ";
  t = "<div class='bl1'>" +
      t + "</div>";
  document.getElementById("out")
  .innerHTML = t;
}

</script>

  </body>
</html>

do podrozdziału do strony

Cechy Algorytmu Sortowania Bąbelkowego I
klasa złożoności obliczeniowej optymistyczna	O(n²)
klasa złożoności obliczeniowej typowa	O(n²)
klasa złożoności obliczeniowej pesymistyczna	O(n²)
Sortowanie w miejscu	TAK
Stabilność	TAK

do podrozdziału do strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Sortowanie bąbelkowe I
Bubble Sort

Algorytm

Uwaga:

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Schemat blokowy

Przykładowe programy

Podsumowanie

Sortowanie bąbelkowe IBubble Sort

Algorytm

Uwaga:

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Schemat blokowy

Przykładowe programy

Podsumowanie

Sortowanie bąbelkowe I
Bubble Sort