Algorytmy Sortujące - Sortowanie Bąbelkowe Dwukierunkowe

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

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
p_min	- dolna granica pozycji sortowanych elementów, p_min ∈ N
p_max	- górna granica pozycji sortowanych elementów, p_max ∈ 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:	p_min ← 1; p_max ← n - 1
K02:	p ← 0
K03:	Dla i = p_min, p_min + 1, ..., p_max: wykonuj operację sortującą
K04:	Jeśli p = 0, to zakończ
K05:	p_max ← p - 1; p ← 0
K06:	Dla i = p_max, p_max - 1, ..., p_min: wykonuj operację sortującą
K07:	p_min ← p + 1
K08:	Jeśli p > 0, to idź do kroku K02
K09:	Zakończ

Schemat blokowy

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:

- dolną w p_min
- górną w p_max.

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 p_min do p_max. 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 p_max 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 p_max do p_min. 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 p_min 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

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>
    <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">Dwukierunkowe Sortowanie Bąbelkowe</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>

// 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; // Liczebność zbioru.

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("t_out").innerHTML = t;
}

</script> 

  </body>
</html>

do podrozdziału do strony

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

Dwukierunkowe sortowanie bąbelkowe
Bidirectional Bubble Sort
Cocktail Sort

Algorytm

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Operacja sortująca

Algorytm główny

Schemat blokowy

Przykładowe programy

Dwukierunkowe Sortowanie Bąbelkowe

Podsumowanie

Dwukierunkowe sortowanie bąbelkowe Bidirectional Bubble Sort Cocktail Sort

Algorytm

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Operacja sortująca

Algorytm główny

Schemat blokowy

Przykładowe programy

Dwukierunkowe Sortowanie Bąbelkowe

Podsumowanie

Dwukierunkowe sortowanie bąbelkowe
Bidirectional Bubble Sort
Cocktail Sort