Úvod do třídění bublin v Javě

Bubble sort je jedním z nejčastěji používaných algoritmů pro třídění dat v Javě. Třídění se provádí rekurzivním porovnáváním sousedních čísel a jejich posunutím v rostoucím nebo klesajícím pořadí podle potřeby. Toto posunutí prvků se provádí, dokud nejsou všechny číslice kompletně seřazeny v požadovaném pořadí.

Název „Bubble sort“ tohoto algoritmu je způsoben tím, že elementy pole se dostanou na začátek. Podívejme se na algoritmus třídění bublin na příkladu.

Příklad: Zvažte řadu čísel (6 1 8 5 3), která je třeba uspořádat ve vzestupném pořadí.

Algoritmus řazení bublin funguje ve více iteracích, dokud nezjistí, že jsou všechna čísla seřazena.

Iterace

Níže jsou uvedeny iterace provedené v Bubble Sort in Java, které je následující:

První iterace

(6 1 8 5 3) - Začíná porovnáním prvních dvou čísel a posune menší číslo z nich doprava. Proto mezi 6 a 1, 1 je menší počet posunut doleva a 6 doprava.

(1 6 8 5 3) - Dále porovnává sousední dvě čísla posunutím jedné pozice doprava. Zde je číslo 6 menší než 8, a proto je zachováno stejné pořadí.

(1 6 8 5 3) - Opět posouváním jedné polohy doprava dochází k porovnání mezi 8 a 5. Číslo 5 se posune doleva, protože je menší než 8.

(1 6 5 8 3) - Zde se provádí srovnání mezi čísly 8 a 3. Číslo 3 se posune doleva, protože je menší než 8.

(1 6 5 3 8) - Toto je konečný výsledek objednávky po 1. iteraci.

Druhá iterace

Protože čísla stále ještě nejsou zcela v rostoucím pořadí, program jde na druhou iteraci.

(1 6 5 3 8) - Zde opět začíná srovnání od prvních dvou číslic výsledku z první iterace. Porovnává čísla 1 a 6 a zachovává stejné pořadí, protože 1 je menší než 6.

(1 6 5 3 8) - Zde jsou porovnána čísla 5 a 6. Stejná objednávka je zachována jako již v požadovaném rostoucím pořadí.

(1 5 6 3 8) - Zde se provádí srovnání mezi čísly 6 a 3. Číslo 3 se posune doleva, protože je menší než 6.

(1 5 3 6 8) - Další čísla 6 a 8 jsou vzájemně porovnána. Stejné pořadí je zachováno jako v očekávaném pořadí.

(1 5 3 6 8) - Toto je konečný výsledek po druhé iteraci. Přesto si můžeme všimnout, že číslice nejsou zcela uspořádány v jejich rostoucím pořadí. Stále musíme vyměnit čísla 5 a 3, abychom získali konečný výsledek. Program tedy platí pro třetí iteraci.

Třetí iterace

(1 5 3 6 8) - Třetí iterace začíná porovnáním prvních dvou číslic 1 a 5. Protože objednávka je podle očekávání, zůstane stejná.

(1 5 3 6 8) - Dále jsou porovnány sousední čísla 3 a 5. Protože 5 je větší než 3, je posunut na pravou stranu.

(1 3 5 6 8) - iterace pokračuje ve srovnání čísel 5 a 6, 6 a 8. Protože je v požadovaném pořadí, zachovává si pořadí.

(1 3 5 6 8) - Nakonec se iterace zastaví, když program přejde porovnáním každého sousedního prvku a zjistí, že všechny číslice jsou ve vzestupném pořadí.

Protože zde bylo pouze 5 prvků pole, které bylo třeba třídit, trvalo celkem pouze 3 iterace. Jak se prvky v poli zvětšují, zvyšuje se také množství iterací.

Implementace třídění bublin pomocí Java

Níže je kód Java, který je implementací algoritmu třídění bublin. (Všimněte si, že první pozice pole v Javě začíná na 0 a pokračuje v krocích po 1, tj. Pole (0), pole (1), pole (2) a pokračuje.)

Kód:

import java.util.Scanner;
public class BubbleSort (
static void bubbleSort(int() arraytest) (
int n = arraytest.length; //length of the array is initialized to the integer n
int temp = 0; //A temporary variable called temp is declared as an integer and initialized to 0
for(int i=0; i < n; i++)( // first for loop performs multiple iterations
for(int j=1; j < (ni); j++)(
if(arraytest(j-1) > arraytest(j))( // if loop compares the adjacent numbers
// swaps the numbers
temp = arraytest(j-1); // assigns the greater number to temp variable
arraytest(j-1) = arraytest(j); // shifts the lesser number to the previous position
arraytest(j) = temp; // bigger number is then assigned to the right hand side
)
)
)
)
public static void main(String() args) (
int arraytest() =(23, 16, 3, 42, 75, 536, 61); // defining the values of array
System.out.println("Array Before Doing Bubble Sort");
for(int i=0; i < arraytest.length; i++)( // for loop used to print the values of array
System.out.print(arraytest(i) + " ");
)
System.out.println();
bubbleSort(arraytest); // array elements are sorted using bubble sort function
System.out.println("Array After Doing Bubble Sort");
for(int i=0; i < arraytest.length; i++)(
System.out.print(arraytest(i) + " "); // for loop to print output values from array
)
)
)

Výstup:

Výhody a nevýhody třídění bublin v Javě

Níže jsou uvedeny různé výhody a nevýhody bublin v java:

Výhody

  1. Kód je velmi snadno zapisovatelný a srozumitelný. Obvykle to trvá jen několik minut.
  2. Implementace je také velmi snadná.
  3. Třídění bublin setřídí čísla a udržuje je v paměti, čímž šetří spoustu paměti.

Nevýhody

  1. Tento algoritmus není vhodný pro velké datové sady, protože porovnání trvá hodně času. Čas potřebný k třídění vstupních čísel exponenciálně roste.
  2. O (n 2) je průměrná složitost Bubble sort a O (n) je nejlepší složitost případu (nejlepší případ je, když jsou prvky seřazeny na prvním místě), kde n je počet prvků.

Aplikace v reálném čase

Protože Bubble sort dokáže detekovat drobné chyby při třídění, používá se v počítačové grafice. Používá se také v algoritmu výplně mnohoúhelníku, kde je třeba třídit obložení vrcholů polygonu.

Závěr

V tomto článku jsme viděli, jak funguje algoritmus řazení bublin a jak jej lze implementovat pomocí programování v jazyce Java. Bubble sort je velmi stabilní algoritmus, který lze snadno implementovat pro poměrně malé datové sady. Jedná se o srovnávací algoritmus a je používán začátečníky kvůli jeho jednoduchosti.

Doporučené články

Toto je průvodce třídením bublin v Javě. Zde diskutujeme o několika iteracích k provedení bublinového třídění v javě a implementaci kódu spolu s výhodami a nevýhodami. Další informace naleznete také v následujících článcích -

  1. Řazení bublin v JavaScriptu
  2. Třídění v R.
  3. 3D pole v Javě
  4. Pole v C #
  5. Řazení bublin v Pythonu

Kategorie:

Vývoj softwaru