Serwis Edukacyjny
Nauczycieli
w I-LO w Tarnowie
obrazek Materiały głownie dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2026 mgr Jerzy Wałaszek

Dwukierunkowe sortowanie bąbelkowe
  Bidirectional Bubble Sort
 Cocktail Sort

SPIS TREŚCI
Podrozdziały

Algorytm

Dwukierunkowe sortowanie bąbelkowe oparte jest na spostrzeżeniu, iż każdy obieg wewnętrznej pętli sortującej umieszcza na właściwym miejscu element najstarszy, a elementy młodsze przesuwa o 1 pozycję w kierunku początku zbioru. Jeśli pętla ta zostanie wykonana w kierunku odwrotnym, to wtedy najmłodszy element znajdzie się na swoim właściwym miejscu, a elementy starszy przesuną się o jedną pozycję w kierunku końca zbioru. Połączmy te dwie pętle sortując wewnętrznie naprzemiennie w kierunku normalnym i odwrotnym, a otrzymamy algorytm dwukierunkowego sortowania bąbelkowego.

Wykonanie pętli sortującej w normalnym kierunku ustali maksymalną pozycję w zbiorze, od której powinna rozpocząć sortowanie pętla odwrotna. Ta z kolei ustali minimalną pozycję w zbiorze, od której powinna rozpocząć sortowanie pętla normalna w następnym obiegu pętli zewnętrznej. Sortowanie możemy zakończyć, jeśli nie wystąpiła potrzeba zamiany elementów w żadnej z tych dwóch pętli.


do podrozdziału  do strony 

Opis algorytmu

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

Operacja sortująca

K01: Jeśli d[i] ≤ d[i + 1],
to zakończ operację sortującą
K02: d[i] ↔ d[i + 1]
K03: p ← i
K04: Zakończ operację sortującą

Algorytm główny

K01: pmin ← 1; pmax ← n - 1
K02: p ← 0
K03:     Dla i = pmin, pmin + 1, ..., pmax:
    wykonuj operację sortującą
K04:     Jeśli p = 0,
    to zakończ
K05:     pmax ← p - 1;   p ← 0
K06:     Dla i = pmax, pmax - 1, ..., pmin:
    wykonuj operację sortującą
K07:     pmin ← p + 1
K08:     Jeśli p > 0,
    to idź do kroku K02
K09: Zakończ

Schemat blokowy

obrazek

W algorytmie wydzieliliśmy powtarzający się fragment operacji i nazwaliśmy go operacją sortującą. Porównuje ona dwa kolejne elementy zbioru i zamienia je miejscami, jeśli są w złej kolejności. Po zamianie do zmiennej p trafia indeks pierwszego z elementów pary. Podany warunek sprawdza uporządkowanie rosnące. Jeśli chcemy posortować zbiór malejąco, relację większości należy zastąpić relacją mniejszości.

W algorytmie występują trzy pętle. Pętla nr 1 jest pętlą warunkową i obejmuje dwie pętle wewnętrzne nr 2 i nr 3. Pętla ta wykonywana jest dotąd, aż w sortowanym zbiorze nie wystąpi w trakcie sortowania ani jedna zamiana miejsc elementów.

Pętla nr 2 jest pętlą sortującą w górę. Pętla nr 3 sortuje w dół.

Na początku algorytmu ustalamy dwie granice sortowania:

Granice te określają indeksy elementów zbioru, które będą przeglądały pętle sortujące nr 2 i nr 3. Początkowo granice są tak ustawione, iż obejmują cały sortowany zbiór.

Na początku pętli nr 1 zerujemy zmienną p. Zmienna ta będzie zapamiętywać pozycję ostatniej zamiany elementów. Jeśli po przejściu pętli sortującej nr 2 lub nr 3 zmienna p wciąż zawiera wartość 0, to nie wystąpiła żadna zamiana elementów. Zbiór jest wtedy uporządkowany i kończymy algorytm.

Pierwszą pętlę sortującą wykonujemy kolejno dla indeksów od pmin do pmax. Po zakończeniu pętli sprawdzamy, czy p jest równe 0. Jeśli tak, kończymy algorytm. W przeciwnym razie p zawiera pozycję ostatniej zamiany elementów. Ponieważ pętla nr 2 ustala pozycję najstarszego elementu, to elementy o indeksach od p do n są już właściwie uporządkowane. Dlatego dla kolejnego obiegu pętli przyjmujemy pmax o 1 mniejsze niż p.

Przed rozpoczęciem drugiej pętli zerujemy p. Jest to dosyć ważne. Załóżmy, iż zbiór został już uporządkowany w poprzedniej pętli nr 2, lecz wystąpiła tam zamiana elementów. Jeśli nie wyzerujemy p, to następna pętla sortująca nie zmieni zawartości tej zmiennej i p zachowa wartość większą od 0. Zatem pętla główna nr 1 nie zakończy się i algorytm wykona niepotrzebnie jeszcze jeden pusty obieg. Niby nic, a jednak...

Pętla nr 3 sortuje w kierunku odwrotnym od pmax do pmin. Po jej zakończeniu p zawiera indeks ostatniej zamiany elementów. Podobnie jak poprzednio zbiór jest uporządkowany od elementu nr 1 do p. Zatem dla kolejnych obiegów przyjmujemy pmin o 1 większe od p. Jeśli p jest równe 0, kończymy algorytm. W przeciwnym razie kontynuujemy pętlę nr 1.


do podrozdziału  do strony 

Przykładowe programy

C++
// Dwukierunkowe Sortowanie Bąbelkowe
//-----------------------------------
// (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,pmin,pmax,p;

  cout << "Dwukierunkowe Sortowanie babelkowe\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

  pmin = 0; pmax = N - 2;
  do
  {
    p = -1;
    for(i = pmin; i <= pmax; i++)
      if(d[i] > d[i + 1])
      {
        swap(d[i], d[i + 1]);
        p = i;
      }
    if(p < 0) break;
    pmax = p - 1;
    p = -1;
    for(i = pmax; i >= pmin; i--)
      if(d[i] > d[i + 1])
      {
        swap(d[i], d[i + 1]);
        p = i;
      }
    pmin = p + 1;
  } 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 << endl;
  system("pause");
  return 0;
}
Pascal
// Dwukierunkowe Sortowanie Bąbelkowe
//-----------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie

program Bidirectional_Bubble_Sort;

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

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

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

var
  i,p,pmin,pmax,x: integer;
begin
  writeln('Dwukierunkowe sortowanie babelkowe');
  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

  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;
        p := i;
      end;
    if p = 0 then break;
    pmax := p - 1;
    p := 0;
    for i := pmax downto pmin do
      if d[i] > d[i + 1] then
      begin
        x := d[i]; d[i] := d[i+1]; d[i+1] := x;
        p := i;
      end;
    pmin := 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;
  writeln('Nacisnij Enter...');
  readln;
end.
Basic
' Dwukierunkowe Sortowanie Bąbelkowe
'-----------------------------------
' (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,p,pmin,pmax

PRINT "Dwukierunkowe sortowanie babelkowe"
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

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)
      p = i
    END IF
  NEXT
  IF p = 0 THEN EXIT DO
  pmax = p - 1
  p = 0
  FOR i = pmax TO pmin STEP -1
    IF d(i) > d(i + 1) THEN
      SWAP d(i), d(i + 1)
      p = i
    END IF
  NEXT  
  pmin = 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
PRINT "Nacisnij Enter...";
SLEEP
END
Python (dodatek)
# Sortowanie Bąbelkowe - wersja nr 3
#--------------------------------------------------------
# (C)2012 mgr Jerzy Wałaszek
# I Liceum Ogólnokształcące
# im. K. Brodzińskiego
# w Tarnowie
#--------------------------------------------------------

import random

n = 20 # Liczebność zbioru.

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

d = [random.randrange(100) for i in range(n)]

print("Dwukierunkowe sortowanie bąbelkowe")
print("----------------------------------")
print("(C)2026 Jerzy Wałaszek")
print()

# wyświetlamy zawartość tablicy

print("Przed sortowaniem:")
print()
for i in range(n):
    print("%4d" % (d[i]),end="")
print()
print()

# Sortujemy

pmin = 0
pmax = n - 2
p = 0
while p >= 0:
    p = -1
    for i in range(pmin,pmax+1):
        if d[i] > d[i+1]:
            d[i],d[i+1] = d[i+1],d[i]
            p = i
    if p < 0: break
    pmax = p - 1
    p = -1
    for i in reversed(range(pmin,pmax+1)):
        if d[i] > d[i+1]:
            d[i],d[i+1] = d[i+1],d[i]
            p = i
    pmin = p + 1

# 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: 
Dwukierunkowe sortowanie bąbelkowe 
----------------------------------
(C)2026 Jerzy Wałaszek

Przed sortowaniem:

  29  56  89  26  32  89  64  50  73  84  12  62   0  62  76  75  54  77  34  83

Po sortowaniu:

   0  12  26  29  32  34  50  54  56  62  62  64  73  75  76  77  83  84  89  89

Naciśnij Enter...
JavaScript
<html>
  <head>
  </head>
  <body>

<div style="overflow-x: auto; overflow-y: hidden;"
     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>&nbsp;&nbsp;
          Dwukierunnkowe
          Sortowanie
          Bąbelkowe
          &nbsp;&nbsp;</b><br/>
          (C)2026 mgr
          Jerzy Wałaszek
          <hr/>
          <input
          onclick="main()"
          value="Sortuj"
          name="B1"
          type="button">
          <hr/>
          <div id="out">.</div>
        </form>
      </td>
    </tr>
  </table>
</div>

<script language="javascript">

// Dwukierunkowe Sortowanie
// Bąbelkowe
//---------------------------
// (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,pmin,pmax,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
  pmin = 0;
  pmax = N - 2;
  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;
        p = i;
      }
    if(p < 0) break;
    pmax = p - 1;
    p = -1;
    for(i = pmax;
        i >= pmin;
        i--)
      if(d[i] > d[i + 1])
      {
        x = d[i];
        d[i] = d[i + 1];
        d[i + 1] = x;
        p = i;
      }
    pmin = p + 1;
  } while(p >= 0);

  // Wyświetlamy wynik
  // sortowania
  t += "Po sortowaniu:" +
       "<br/><br/>";
  for(i = 0; i < N; i++)
    t += d[i] + " ";
  document.getElementById("out")
  .innerHTML = t;
}

</script>

  </body>
</html>
   Dwukierunnkowe Sortowanie Bąbelkowe   
(C)2026 mgr Jerzy Wałaszek
.

do podrozdziału  do strony 

Podsumowanie

Cechy Algorytmu Dwukierunkowego
Sortowania Bąbelkowego
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

do podrozdziału  do strony 
Zobacz również na: Wersję 1 | Wersję 2 | Wersję 3 | Wersję 4
Zespół Przedmiotowy
Chemii-Fizyki-Informatyki
w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2026 mgr Jerzy Wałaszek

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.