Bublinkové triedenie

Bublinkové triedenie () 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 .

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.

Kategória:Triediacie algoritmy

no:Sorteringsalgoritme#Boblesortering