Sortowanie bąbelkowe

Z Wikipedii

"Bąbelek" (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 sortowania bąbelkowego (bez znacznika zmiany change) w C#: 4 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;
  bool change;

  for (i=0; i<n-1; i++) 
  {
       change=false;
       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=true;
          }
       if(!change) break;      // nie dokonano zmian - koniec!
  }
}

[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 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);
}