Bublinkové triedenie

Bublinkové triedenie upravené color

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.

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.