Bublinkové triedenie

Bublinkové triedenie (angl. bubble sort) je implementačne jednoduchý výmenný triediaci algoritmus. Pracuje na mieste a nepatrí medzi prirodzené triediace algoritmy. Pre praktické využitie je neefektívny.

Bublinkové triedenie upravené color

Pracuje opakovaným prechodom cez zoznam, ktorý má byť utriedený porovnávajúc vždy dva prvky. Ak prvky nie sú v správnom poradí, zamení ich. Porovnávanie prvkov v zozname trvá, pokiaľ sú potrebné výmeny, teda pokiaľ nie je zoznam usporiadaný. Algoritmus dostal názov vďaka tomu, že menšie prvky sa „prebublinkujú“ na začiatok zoznamu.

Algoritmus

Poznámka: toto je len jedna z variácií algoritmu.

Pre i od 1 po (počet prvkov)
  Pre j od 1 po (počet prvkov - i)
    Ak zoznam[j] > zoznam[j+1]
      Vymeň zoznam[j] ↔ zoznam[j+1]

for I := High(A) downto Low(A) do
   for J := Low(A) to High(A) - 1 do
     if A[J] > A[J + 1] then
       begin
         T := A[J];
         A[J] := A[J + 1];
         A[J + 1] := T;
       end;

Java

public static void bubbleSort(int[] array){
   for (int i = 0; i < array.length - 1; i++) {
       for (int j = 0; j < array.length - i - 1; j++) {
           if(array[j] < array[j+1]){
               int tmp = array[j];
               array[j] = array[j+1];
               array[j+1] = tmp;

           }
       }
   }
}

C++

void bubbleSort(int * array, int size){
   for(int i = 0; i < size - 1; i++){
       for(int j = 0; j < size - i - 1; j++){
           if(array[j+1] < array[j]){
               int tmp = array[j + 1];
               array[j + 1] = array[j];
               array[j] = tmp;
           }   
       }   
   }   
}    

C#

static void BubbleSort(int[] arr)
{
   for (int i = 0; i < arr.Length - 1; i++)
   {
       for (int j = 0; j < arr.Length - i - 1; j++)
       {
           if (arr[j + 1] < arr[j])
           {
               int tmp = arr[j + 1];
               arr[j + 1] = arr[j];
               arr[j] = tmp;
           }
       }
   }
}

JavaScript

function bubbleSort(array){
   for (var i = 0; i < array.length - 1; i++) {
       for (var j = 0; j < array.length - i - 1; j++) {
           if(array[j] < array[j+1]){
               var tmp = array[j];
               array[j] = array[j+1];
               array[j+1] = tmp;
           }
       }
   }
}   

Pascal

procedure BubbleSort(var X : ArrayType; N : integer);
var
 I,
 J : integer;
begin
 for I := 2 to N do
   begin
     for J := N downto I do
       if (X[J] > X[J - 1]) then
         Swap(X[J - 1], X[J]);
   end
end;

procedure Swap(var X, Y : integer);
var
 Temp : integer;
begin
 Temp := X;
 X := Y;
 Y := Temp
end;

PHP

function bubble_sort($arr)
{
   $count = count($arr);
   for($i = 0; $i < $count - 1; $i++) {
       for($j = 0; $j < $count - $i - 1; $j++) {
           if($arr[$j + 1] < $arr[$j]) {
               $tmp = $arr[$j + 1];
               $arr[$j + 1] = $arr[$j];
               $arr[$j] = $tmp;
           }
       }
   }
}

Zložitosť

Asymptotická priemerná aj najhoršia zložitosť bublinkového triedenia je $O(n^{2})$.

Tento algoritmus triedenia je jedným z najhorších, oproti iným algoritmom s rovnakou rádovou zložitosťou vyžaduje veľa zápisov do pamäte a neefektívnu prácu s cache procesora. Takmer neexistuje prípad, kedy by mal nejakú výhodu oproti iným postupom.