Algorytmy Sortujące - Sortowanie Bąbelkowe

Podany w poprzednim rozdziale algorytm sortowania bąbelkowego można zoptymalizować pod względem czasu wykonania. Jeśli przyjrzymy się dokładnie obiegom wykonywanym w tym algorytmie, to zauważymy bardzo istotną rzecz:

Po wykonaniu pełnego obiegu w algorytmie sortowania bąbelkowego najstarszy element wyznaczony przez przyjęty porządek zostaje umieszczony na swoim właściwym miejscu - na końcu zbioru.

Wniosek ten jest oczywisty. W każdej kolejnej parze porównywanych elementów element starszy przechodzi na drugą pozycję. W kolejnej parze jest on na pierwszej pozycji, a skoro jest najstarszym, to po porównaniu znów przejdzie na pozycję drugą itd. - jest jakby ciągnięty na koniec zbioru (jak bąbelek powietrza wypływający na powierzchnię wody).

Przykład:

Wykonamy jeden obieg sortujący dla zbioru pięcioelementowego

{ 9 3 1 7 0 }

Elementem najstarszym jest pierwszy element - liczba 9.

Obieg	Zbiór	Opis operacji
1	9 3 1 7 0	Para wymaga przestawienia elementów. Element najstarszy przejdzie na drugą pozycję w parze.
	3 9 1 7 0	Konieczne przestawienie elementów. Element najstarszy znów trafi na pozycję drugą w parze.
	3 1 9 7 0	Konieczne przestawienie elementów.
	3 1 7 9 0	Ostatnia para również wymaga przestawienia elementów.
	3 1 7 0 9	Koniec obiegu. Najstarszy element znalazł się na końcu zbioru.

Co z tego wynika dla nas? Otóż po każdym obiegu na końcu zbioru tworzy się podzbiór uporządkowanych najstarszych elementów. Zatem w kolejnych obiegach możemy pomijać sprawdzanie ostatnich elementów – liczebność zbioru do posortowania z każdym obiegiem maleje o 1.

Przykład:

Dokończmy sortowania podanego powyżej zbioru uwzględniając podane przez nas fakty. Po pierwszym obiegu na końcu zbioru mamy umieszczony element najstarszy. W drugim obiegu będziemy zatem sortować zbiór 4 elementowy, w trzecim obiegu 3 elementowy i w obiegu ostatnim, czwartym - zbiór 2 elementowy.

Obieg	Zbiór	Opis operacji
2	3 1 7 0 9	Para wymaga przestawienia elementów.
	1 3 7 0 9	Dobra kolejność
	1 3 7 0 9	Konieczne przestawienie elementów.
	1 3 0 7 9	Koniec obiegu. Na końcu zbioru mamy 2 elementy uporządkowane.
3	1 3 0 7 9	Dobra kolejność
	1 3 0 7 9	Konieczne przestawienie elementów.
	1 0 3 7 9	Koniec obiegu. Na końcu zbioru mamy 3 elementy uporządkowane.
4	1 0 3 7 9	Konieczne przestawienie elementów.
4	0 1 3 7 9	Koniec ostatniego obiegu - zbiór jest posortowany.

W porównaniu do tabelki z poprzedniego rozdziału nawet wzrokowo możemy zauważyć istotne zmniejszenie ilości niezbędnych operacji.

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 = n - 1, n - 2, ..., 1: Wykonuj krok K02
K02:	Dla i = 1, 2, ..., j: jeśli d[i] > d[i + 1], to d[i] ↔ d[i + 1]
K03:	Zakończ

Schemat blokowy

Zmiany w stosunku do poprzedniej wersji zaznaczyliśmy na schemacie blokowym innym kolorem elementów. Są one następujące:

pętla zewnętrzna nr 1 zlicza obiegi wstecz, tzn. pierwszy obieg ma numer n-1. Dzięki takiemu podejściu w zmiennej j mamy zawsze numer ostatniego elementu, do którego ma dojść pętla wewnętrzna nr 2. Ta zmiana wymaga również odwrotnej iteracji zmiennej j.
pętla wewnętrzna sprawdza w warunku kontynuacji, czy wykonała j obiegów, a nie jak poprzednio n-1 obiegów. Dzięki temu po każdym obiegu pętli nr 1 (zewnętrznej) pętla nr 2 będzie wykonywać o jeden obieg mniej.

Pozostała część algorytmu nie jest zmieniona - w pętli wewnętrznej nr 2 sprawdzamy, czy element d[i] jest w złej kolejności z elementem d[i+1]. Sprawdzany warunek spowoduje posortowanie zbioru rosnąco. Przy sortowaniu malejącym zmieniamy relację większości na relację mniejszości. Jeśli warunek jest spełniony, zamieniamy miejscami element d[i] z elementem d[i+1], po czym kontynuujemy pętlę nr 2 zwiększając o 1 indeks i. Po każdym zakończeniu pętli nr 2 indeks j jest zmniejszany o 1.

Ilość obiegów pętli wewnętrznej wynosi:

Otrzymane wyrażenie ma wciąż kwadratową klasę złożoności obliczeniowej, jednakże T₂(n) < T₁(n) dla n > 1. Osiągnęliśmy zatem większą efektywność działania dzięki wprowadzonym zmianom.

do podrozdziału do strony

C++

// Sortowanie Bąbelkowe - Wersja nr 2
//-----------------------------------
// (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 2\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 << endl;

// Sortujemy

  for(j = N - 1; j > 0; j--)
    for(i = 0; i < j; 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 << endl;
  system("pause");
  return 0;
}

Pascal

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

program Bubble_Sort_2;

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 2     ');
  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 := N - 1 downto 1 do
    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;
      end;
  writeln;

// 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 - Wersja nr 2
'-----------------------------------
' (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 2     "
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 = N - 1 TO 1 STEP -1
  FOR i = 1 TO j
    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 - Wersja nr 2
#-----------------------------------
# (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 2     ")
print("----------------------")
print("(C)2005 Jerzy Wałaszek")
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 reversed(range(n)):
    for i in range(j):
        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 2     
----------------------
(C)2005 Jerzy Wałaszek

Przed sortowaniem:

  13  59  72  21  70  82  94  14  89  24  54  26  18  95  34  29  59  75  54  39

Po sortowaniu:

  13  14  18  21  24  26  29  34  39  54  54  59  59  70  72  75  82  89  94  95

Naciśnij Enter...

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 2</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 2
//-----------------------------------
// 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 = N - 1; j > 0; j--)
    for(i = 0; i < j; 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>

do podrozdziału do strony

Cechy Algorytmu Sortowania Bąbelkowego wersja nr 2
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

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 - wersja nr 2
Bubble Sort

Algorytm

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Schemat blokowy

Przykładowe programy

Sortowanie Bąbelkowe - wersja nr 2

Podsumowanie

Sortowanie bąbelkowe - wersja nr 2 Bubble Sort

Algorytm

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Schemat blokowy

Przykładowe programy

Sortowanie Bąbelkowe - wersja nr 2

Podsumowanie

Sortowanie bąbelkowe - wersja nr 2
Bubble Sort