Domů » Informatika » Algoritmus » Řadící algoritmus » Bubble Sort (bublinkové řazení)

Bubble Sort (bublinkové řazení)

Bubble sort je jednoduchý řadící algoritmus s asymptotickou složitostí € O(n^2) €. Traduje se, že kdysi vznikl kvůli tomu, že byly čtecí hlavy páskových mechanik pomalé a bylo tedy žádoucí, aby se hlava pohybovala po pásce po nejkratších možných trajektoriích.

Algoritmus prochází pole a najde-li dva prvky ve špatném pořadí, prohodí je. To opakuje tak dlouho, dokud není pole seřazeno. Po skončení každé n-té iterace vnějšího cyklu je správně seřazeno n prvků na konci pole. Algoritmus bubble sort je přirozený a stabilní.

Implementace (Java)

kód v jazyce Java - Zobrazit

  1. /**
  2.  * Implementace algoritmu bubble sort.
  3.  * @param input vstupní pole
  4.  * @author Vojtěch Hordějčuk
  5.  */
  6. public static <T extends Comparable<? super T>> void bubbleSort(final T[] input)
  7. {
  8.   // průchod skončí na předposledním prvku (index 'i - 2')
  9.   // (prvek se vždy porovnává se svým následníkem)
  10.  
  11.   for (int i = 0; i < input.length - 1; i++)
  12.   {
  13.     // už jsme seřadili 'i' prvků
  14.     // (na konci pole je tedy nemusíme kontrolovat)
  15.  
  16.     for (int j = 0; j < input.length - 1 - i; j++)
  17.     {
  18.       // prohoď sousední prvky, pokud jsou ve špatném pořadí
  19.  
  20.       if (input[j].compareTo(input[j + 1]) == 1)
  21.       {
  22.         final T temp = input[j];
  23.         input[j] = input[j + 1];
  24.         input[j + 1] = temp;
  25.       }
  26.     }
  27.   }
  28. }

Ukázkový běh

Pole Operace
5 2 3 9 1 Toto pole chceme seřadit bubble sortem.
(2 5) 3 9 1 Čísla 5, 2 jsou ve špatném pořadí, prohodit.
2 (3 5) 9 1 Čísla 5, 3 jsou ve špatném pořadí, prohodit.
2 3 (5 9) 1 Čísla 5, 9 jsou ve správném pořadí.
2 3 5 (1 9) Čísla 9, 1 jsou ve špatném pořadí, prohodit.
2 3 5 1 9 Na konci máme správně seřazen jeden prvek.
(2 3) 5 1 9 Čísla 2, 3 jsou ve správném pořadí.
2 (3 5) 1 9 Čísla 3, 5 jsou ve správném pořadí.
2 3 (1 5) 9 Čísla 5, 1 jsou ve špatném pořadí, prohodit.
2 3 1 5 9 Na konci máme správně seřazeny dva prvky.
(2 3) 1 5 9 Čísla 2, 3 jsou ve správném pořadí.
2 (1 3) 5 9 Čísla 3, 1 jsou ve špatném pořadí, prohodit.
2 1 3 5 9 Na konci máme správně seřazeny tři prvky.
(1 2) 3 5 9 Čísla 2, 1 jsou ve špatném pořadí, prohodit.
1 2 3 5 9 Na konci máme správně seřazeny čtyři prvky.
1 2 3 5 9 Pole je seřazeno.