Sortowanie bąbelkowe

Z Wikipedii

Sortowanie bąbelkowe (ang. bubble sort) to prosta metoda sortowania, o złożoności czasowej O(n²) i pamięciowej O(1). Polega na porównywaniu dwóch kolejnych elementów i zamianie ich kolejności, jeżeli zaburza ona porządek, w jakim się sortuje tablicę. Sortowanie kończy się, gdy podczas kolejnego przejścia nie dokonano żadnej zmiany.

Spis treści 1 Przykład działania 2 Przykład w C 3 Przykład w C++ 4 Przykład sortowania bąbelkowego (bez znacznika zmiany change) w C# 5 Przykład sortowania bąbelkowego w Pascalu 6 Przykład odmiany sortowania bąbelkowego zwanej sortowaniem bąbelkowym mieszanym (shuttle sort, cocktail sort) w C#

[edytuj] Przykład działania

Ciąg wejściowy: |4|2|5|1|7|

^-^ oznacza aktualnie porównywane komórki

Każdy wiersz symbolizuje wypchnięcie kolejnego największego elementu na koniec ("wypłynięcie największego bąbelka")

|4|2|5|1|7| -> |2|4|5|1|7| -> |2|4|5|1|7| -> |2|4|1|5|7|
 ^-^              ^-^              ^-^              ^-^
|2|4|1|5|7| -> |2|4|1|5|7| -> |2|1|4|5|7|
 ^-^              ^-^              ^-^
|2|1|4|5|7| -> |1|2|4|5|7| -> 
 ^-^              ^-^
|1|2|4|5|7| -> 
 ^-^           

[edytuj] Przykład w C

• tab[] - tablica elementów ciągu np. o indeksach od 0 do 99
• tmp - zmienna pomocnicza o formacie elementu tablicy tab[]
• change - zmienna logiczna

...i załóżmy, że sortuje się rosnąco:

typedef int TYP

void bubblesort( TYP a[], int n ) 
{
  int i,j;
  TYP tmp;
  int change;

  for (i=0; i<n-1; i++) 
  {
       change=0;
       for (j=0; j<n-1-i; j++)
          if (a[j+1] < a[j])   //porównanie sąsiądów
          {  
              tmp = a[j];      
              a[j] = a[j+1];
              a[j+1] = tmp;    //wypchanie bąbelka     
              change=1;
          }
       if(!change) break;      // nie dokonano zmian - koniec!
  }
}

[edytuj] Przykład w C++

void BubbleSort (int* tab, int ile_elem)
{
    bool b=false;
    for (int j=ile_elem-1;j>0;j++)
    {
        for (int i=ile_elem-1;i>0;i--)
        {
            if (tab[i]>tab[i-1])
            {
                tab[i]=tab[i]^tab[i-1];     // zamienia liczby
                tab[i-1]=tab[i]^tab[i-1];
                tab[i]=tab[i]^tab[i-1];
                b=true;
            }
        }
        if (!b)     // jesli juz posortowano
        {
            return;     // wyjdz z funkcji
        }
        b=false;
    }
}

[edytuj] Przykład sortowania bąbelkowego (bez znacznika zmiany change) w C#

public static void BubbleSort(IComparable[] a)
{
  int n = a.Length;
  for(int i = 1; i < n; i++)
    for(int j = n - 1; j >= i; j--)
      if(a[j - 1].CompareTo(a[j]) > 0)
      {
        IComparable x = a[j - 1];
        a[j - 1] = a[j];
        a[j] = x;
      }
}

[edytuj] Przykład sortowania bąbelkowego w Pascalu

program sortowanie_babelkowe;
var
i,n,b,c:integer;
tab:array[1..30] of integer;
pomoc:integer;

begin
writeln('Podaj ilość liczb');
readln(n);
writeln('Podawaj kolejno liczby');
for i:=1 to n do readln(tab[i]);

b:=0;
c:=1;
while c>0 do
begin
inc(b);
c:=0;
for i:=1 to n-b do
        begin
        if tab[i] > tab[i+1] then
                begin
                pomoc:=tab[i+1];
                tab[i+1]:=tab[i];
                tab[i]:=pomoc;
                inc(c);
                end;
        end;
end;
for i:=1 to n do
        write(tab[i],', ');
readln;
end.

[edytuj] Przykład odmiany sortowania bąbelkowego zwanej sortowaniem bąbelkowym mieszanym (shuttle sort, cocktail sort) w C#

public static void ShuttleSort(IComparable[] a)
{
  int l = 1;
  int p = a.Length - 1;
  int k = p;
  do
  {
    for(int j = p; j >= l; j--)
      if(a[j - 1].CompareTo(a[j]) > 0)
      {
        IComparable x = a[j - 1];
        a[j - 1] = a[j];
        a[j] = x;
        k = j;
      }
    l = k + 1;
    for(int j = l; j <= p; j++)
      if(a[j - 1].CompareTo(a[j]) > 0)
      {
        IComparable x = a[j - 1];
        a[j - 1] = a[j];
        a[j] = x;
        k = j;
      }
    p = k - 1;
  }
  while (l < p);
}