Algorytmy Sortujące - Zaotymalizowane Sortowanie Bąbelkowe

Czy algorytm sortowania bąbelkowego można jeszcze ulepszyć? Tak, ale zaczynamy już osiągać kres jego możliwości, ponieważ ulepszenia polegają jedynie na redukcji operacji pustych. Wykorzystamy informację o miejscu wystąpienia zamiany elementów (czyli o miejscu wykonania operacji sortującej).

Jeśli w obiegu sortującym wystąpi pierwsza zamiana na pozycji i-tej, to w kolejnym obiegu będziemy rozpoczynali sortowanie od pozycji o jeden mniejszej (chyba że pozycja i-ta była pierwszą pozycją w zbiorze). Dlaczego? Odpowiedź jest prosta. Zamiana spowodowała, iż młodszy element znalazł się na pozycji i-tej. Ponieważ w obiegu sortującym młodszy element zawsze przesuwa się o 1 pozycję w kierunku początku zbioru, to nie ma sensu sprawdzanie pozycji od 1 do i-2, ponieważ w poprzednim obiegu zostały one już sprawdzone, nie wystąpiła na nich zamiana elementów, zatem elementy na pozycjach od 1 do i-2 są chwilowo w dobrej kolejności względem siebie. Nie mamy tylko pewności co do pozycji i-1-szej oraz i-tej, ponieważ ostatnia zamiana elementów umieściła na i-tej pozycji młodszy element, który być może należy wymienić z elementem na pozycji wcześniejszej, czyli i-1. W ten sposób określimy początkową pozycję, od której rozpoczniemy sortowanie elementów w następnym obiegu sortującym.

Ostatnia zamiana elementów wyznaczy pozycję końcową dla następnego obiegu. Wiemy, iż w każdym obiegu sortującym najstarszy element jest zawsze umieszczany na swojej docelowej pozycji. Jeśli ostatnia zamiana elementów wystąpiła na pozycji i-tej, to w następnym obiegu porównywanie elementów zakończymy na pozycji o 1 mniejszej - w ten sposób nie będziemy sprawdzać już najstarszego elementu z poprzedniego obiegu.

Sortowanie prowadzimy dotąd, aż w obiegu sortującym nie wystąpi ani jedna zamiana elementów.

Teoretycznie powinno to zoptymalizować algorytm, ponieważ są sortowane tylko niezbędne fragmenty zbioru - pomijamy obszary posortowane, które tworzą się na końcu i na początku zbioru. Oczywiście zysk nie będzie oszałamiający w przypadku zbioru nieuporządkowanego lub posortowanego odwrotnie (może się zdarzyć, iż ewentualne korzyści czasowe będą mniejsze od czasu wykonywania dodatkowych operacji). Jednakże dla zbiorów w dużym stopniu uporządkowanych możemy uzyskać całkiem rozsądny algorytm sortujący prawie w czasie liniowym O(n).

Przykład:

Według opisanej powyżej metody posortujmy zbiór { 0 1 2 3 5 4 7 9 }. W zbiorze tym są tylko dwa elementy nieuporządkowane - 5 i 4.

Obieg	Zbiór	Opis operacji
1	0 1 2 3 5 4 7 9	Pierwszy obieg, rozpoczynamy od pierwszej pozycji.
	0 1 2 3 5 4 7 9	Elementy w dobrej kolejności. Zamiana miejsc nie występuje.
	0 1 2 3 5 4 7 9
	0 1 2 3 5 4 7 9
	0 1 2 3 5 4 7 9	Elementy w złej kolejności. Zapamiętujemy pozycję wymiany. Jest to jednocześnie pierwsza i ostatnia wymiana elementów w tym obiegu sortującym.
	0 1 2 3 4 5 7 9	Elementy w dobrej kolejności. Zamiana miejsc nie występuje.
	0 1 2 3 4 5 7 9	Elementy w dobrej kolejności. Zamiana miejsc nie występuje.
	0 1 2 3 4 5 7 9	Koniec pierwszego obiegu. Zbiór jest już uporządkowany, ale ponieważ była zamiana elementów, algorytm dla pewności musi wykonać jeszcze jeden obieg sortujący.
2	0 1 2 3 4 5 7 9	Sortowanie rozpoczynamy od pozycji o 1 mniejszej od tej, na której wystąpiła w poprzednim obiegu wymiana elementów. Elementy są w dobrej kolejności. Dalszych sprawdzeń nie wykonujemy - kończymy na pozycji o 1 mniejszej, niż pozycja ostatniej zamiany w poprzednim obiegu.
2	0 1 2 3 4 5 7 9	Koniec, zbiór jest posortowany

Chociaż podany przykład jest troszeczkę tendencyjny, to jednak pokazuje wyraźnie, iż zoptymalizowany algorytm sortowania bąbelkowego może bardzo szybko posortować zbiory prawie uporządkowane.

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

K01:	p_min ← 1; p_max ← n - 1
K02	p ← 0
K03:	Dla i = p_min, ..., p_max: wykonuj kroki K04...K07
K04:	Jeśli d[i] ≤ d[i + 1], to następny obieg pętli K03
K05:	d[i] ↔ d[i + 1]
K06:	Jeśli p = 0, to p_min ← i
K07:	p ← i
K08:	Jeśli p_min > 1, to p_min ← p_min - 1
K09:	p_max ← p - 1
K10:	Jeśli p > 0, to idź do kroku K02
K11:	Zakończ

Schemat blokowy

Tym razem wprowadzonych zmian do algorytmu sortowania bąbelkowego jest dużo, zatem opiszemy cały algorytm od początku.

Zmienna p_min przechowuje numer pozycji, od której rozpoczyna się sortowanie zbioru. W pierwszym obiegu sortującym rozpoczynamy od pozycji nr 1. Zmienna p_max przechowuje numer ostatniej pozycji do sortowania. Pierwszy obieg sortujący kończymy na pozycji n-1, czyli na przedostatniej.

Pętla numer 1 wykonywana jest dotąd, aż w wewnętrznej pętli nr 2 nie wystąpi żadna zamiana elementów. Zmienna p pełni w tej wersji algorytmu nieco inną rolę niż poprzednio. Mianowicie będzie przechowywała numer pozycji, na której algorytm ostatnio dokonał wymiany elementów. Na początku wpisujemy do p wartość 0, która nie oznacza żadnej pozycji w zbiorze. Zatem jeśli ta wartość zostanie zachowana, uzyskamy pewność, iż zbiór jest posortowany, ponieważ nie dokonano wymiany elementów.

Wewnętrzną pętlę sortującą rozpoczynamy od pozycji p_min. W pętli sprawdzamy kolejność elementu i-tego z elementem następnym. Jeśli kolejność jest zła, wymieniamy miejscami te dwa elementy. Po wymianie sprawdzamy, czy jest to pierwsza wymiana - zmienna p ma wtedy wartość 0. Jeśli tak, to numer pozycji, na której dokonano wymiany umieszczamy w p_min. Numer ten zapamiętujemy również w zmiennej p. Zwróć uwagę, iż dzięki takiemu podejściu p zawsze będzie przechowywało numer pozycji ostatniej wymiany - jest to zasada zwana "ostatni zwycięża".

Po sprawdzeniu elementów przechodzimy do następnej pozycji zwiększając i o 1 i kontynuujemy pętlę, aż do przekroczenia pozycji p_max. Wtedy pętla wewnętrzna zakończy się.

Jeśli w pętli nr 2 była dokonana zamiana elementów, to p_min zawiera numer pozycji pierwszej zamiany. Jeśli nie jest to pierwsza pozycja w zbiorze, p_min zmniejszamy o 1, aby pętla sortująca rozpoczynała od pozycji poprzedniej w stosunku do pozycji pierwszej zamiany elementów.

Pozycję ostatnią zawsze ustalamy o 1 mniejszą od numeru pozycji końcowej zamiany elementów.

Na koniec sprawdzamy, czy faktycznie doszło do zamiany elementów. Jeśli tak, to p jest większe od 0, gdyż zawiera numer pozycji w zbiorze, na której algorytm wymienił miejscami elementy. W takim przypadku pętlę nr 1 rozpoczynamy od początku. W przeciwnym razie kończymy, zbiór jest uporządkowany

do podrozdziału do strony

C++

// Sortowanie Bąbelkowe - Wersja nr 4
//-----------------------------------
// (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,p,pmin,pmax;

  cout << " Sortowanie babelkowe\n"
          "     WERSJA NR 4\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]);
        if(p < 0) pmin = i;
        p = i;
      }
    if(pmin) pmin--;
    pmax = p;
  } 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

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

program Bubble_Sort_4;

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

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

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

var
   i,p,pmin,pmax,x : integer;
begin
  writeln(' Sortowanie babelkowe ');
  writeln('     WERSJA  NR 4     ');
  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;
        if p = 0 then pmin := i;
        p := i;
      end;
    if pmin > 1 then dec(pmin);
    pmax := 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

' Sortowanie Bąbelkowe - Wersja nr 4
'-----------------------------------
' (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 " Sortowanie babelkowe "
PRINT "     WERSJA  NR 4     "
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)
      IF p = 0 THEN pmin = i
      p = i
    END IF
  NEXT
  IF pmin > 1 THEN pmin -= 1
  pmax = 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 4
#-----------------------------------
# (C)2012 mgr Jerzy Wałaszek
# I Liceum Ogólnokształcące
# im. K. Brodzińskiego
# w Tarnowie

import random

n = 20 # Liczebność zbioru.

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

print(" Sortowanie bąbelkowe ")
print("     WERSJA  NR 4     ")
print("----------------------")
print("(C)2026 Jerzy Wałaszek")
print()

# Wyświetlamy d[]

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]
            if p < 0: pmin = i
            p = i
    if pmin: pmin -= 1
    pmax = p - 1

# Wyświetlamy wynik sortowania

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

Wynik:

 Sortowanie bąbelkowe 
     WERSJA  NR 4     
----------------------
(C)2026 Jerzy Wałaszek

Przed sortowaniem:

  40  32  91  23  32  91  87   4  31  10  63  40  62  54  27  28  52   3   2  14

Po sortowaniu:

   2   3   4  10  14  23  27  28  31  32  32  40  40  52  54  62  63  87  91  91

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>
          Sortowanie
          Bąbelkowe IV
          </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 language="javascript">

//  Sortowanie  Bąbelkowe IV
//---------------------------
// (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,p,pmin,pmax,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 - 1;
  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;
        if(p < 0) pmin = i;
        p = i;
      };
    if(pmin) pmin--;
    pmax = p;
  } 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>

do podrozdziału do strony

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

Sortowanie bąbelkowe - wersja nr 4
Bubble Sort

Algorytm

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Schemat blokowy

Przykładowe programy

Podsumowanie

Sortowanie bąbelkowe - wersja nr 4 Bubble Sort

Algorytm

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Schemat blokowy

Przykładowe programy

Podsumowanie

Sortowanie bąbelkowe - wersja nr 4
Bubble Sort