Třídící algoritmy: Bubble Sort

Třídit pole, respektive jakoukoliv množinu dat je docela užitečná věc. Tudíž se budu chvilku věnovat třídícím algoritmům. První část seriálu bude o Bubble sortu, na pochopení nejjednodušším ale také nejpomalejším algoritmem, takzvaným bublákem.

Složitost:

Složitost algoritmu BubbleSort je Ο(n2), což ho odsuzuje do použití na malých polích. Ale je to jeden z nejrychlejších způsobů jak zjistit, zda je pole setříděné.

Princip:

Začnu od prvního prvku a porovnám ho s druhým. Pokud je první větší, prvky prohodím, pokračuji na druhý prvek a znovu porovnám, takto pokračuji, dokud se nedostanu nakonec. Tím zajistím, že největší prvek pole je na konci pole. Takto jedu znovu od začátku, ale zarazím se o jeden prvek před koncem, protože vím, že tam je největší prvek. Toto opakuji tolikrát, kolik prvků má pole. Resoektive tak dlouho dokud je co třídit, což znamená, že pokud projdu jednu sekvenci od začátku do konce, bez jediného prohození prvku, je setříděno.

Vývojový diagram:

public void bubbleSortAsc(Int[] array) {
  int x;
  for (int i = 0; i < array.length; i++) {
    for (j = 1; j array.length - 1 - i; j++) {
      if (array [j-1] > array [j]) {
        x = array [j-1];
        array [j-1] = array [j];
        array [j] = x;
      }
    }
  }
}

public void bubbleSortDesc(Int[] array) {
  int x;
  for (int i = 0; i < array.length; i++) {
    for (j = 1; j array.length - 1 - i; j++) {
      if (array [j-1] < array [j]) {
        x = array [j-1];
        array [j-1] = array [j];
        array [j] = x;
      }
    }
  }
}

procedure BubbleSort(Items: Array of Integer);
var
  done: boolean;
  i, n: integer;
  Dummy: string;
begin
  n := Length(Items);

  repeat
    done := true;
    for i := 0 to n - 2 do
      if Items[i] > Items[i + 1] then
      begin
        Dummy := Items[i];
        Items[i] := Items[i + 1];
        Items[i + 1] := Dummy;

        done := false;
      end;
  until done;
end;