Úvod do bublinového triedenia v Jave
Bubble sort je jedným z najbežnejšie používaných algoritmov na triedenie údajov v Java. Triedenie sa tu vykonáva rekurzívnym porovnávaním susedných čísel a ich posúvaním v rastúcom alebo klesajúcom poradí podľa potreby. Toto posúvanie prvkov sa vykonáva dovtedy, kým nie sú všetky číslice úplne zoradené v požadovanom poradí.
Názov „Bubble sort“ tohto algoritmu je ten, že prvky poľa sa dostanú na jeho začiatok. Pochopme algoritmus triedenia bublín pomocou príkladu.
Príklad: Zoberme si rad čísel (6 1 8 5 3), ktoré je potrebné usporiadať vo vzostupnom poradí.
Algoritmus triedenia bubliniek funguje vo viacerých iteráciách, kým nezistí, že sú všetky čísla zoradené.
iterácie
Nižšie sú uvedené iterácie vykonávané v aplikácii Bubble Sort in Java, ktoré sú nasledujúce:
Prvá iterácia
(6 1 8 5 3) - Začína porovnaním prvých dvoch čísiel a posunutím menšieho čísla napravo. Preto medzi 6 a 1, 1 je menšie číslo posunuté doľava a 6 doprava. (1 6 8 5 3) - Ďalej porovnáva susedné dve čísla posunutím jednej polohy doprava. Tu je číslo 6 menšie ako 8, a preto sa zachováva rovnaký poriadok. (1 6 8 5 3) - Opäť posunutím jednej polohy doprava sa uskutoční porovnanie medzi 8 a 5. Číslo 5 sa posunie doľava, pretože je menšie ako 8. (1 6 5 8 3) - Tu sa uskutočňuje porovnanie medzi číslami 8 a 3. Číslo 3 sa posúva doľava, pretože je menšie ako 8. (1 6 5 3 8) - Toto je konečný výsledok objednávky po 1. iterácii.Druhá iterácia
Pretože čísla ešte stále nie sú úplne v rastúcom poradí, program ide na druhú iteráciu.
(1 6 5 3 8) - Tu znova začína porovnávanie od prvých dvoch číslic výsledku z prvej iterácie. Porovnáva čísla 1 a 6 a zachováva rovnaké poradie, pretože 1 je menší ako 6. (1 6 5 3 8) - Tu sa porovnávajú čísla 5 a 6. Rovnaké poradie sa zachová, ako je už v požadovanom rastúcom poradí. (1 5 6 3 8) - Tu sa uskutočňuje porovnanie medzi číslami 6 a 3. Číslo 3 sa posúva doľava, pretože je menšie ako 6. (1 5 3 6 8) - Nasledujúce čísla 6 a 8 sa navzájom porovnávajú. Rovnaké poradie sa zachová ako v očakávanom poradí. (1 5 3 6 8) - Toto je konečný výsledok po druhej iterácii. Napriek tomu si môžeme všimnúť, že číslice nie sú úplne usporiadané v rastúcom poradí. Aby sme dosiahli konečný výsledok, stále si musíme vymeniť čísla 5 a 3. Program sa preto týka tretej iterácie.Tretia iterácia
(1 5 3 6 8) - Tretia iterácia sa začína porovnaním prvých dvoch číslic 1 a 5. Keďže poradie je podľa očakávania, zostáva zachované. (1 5 3 6 8) - Ďalej sa porovnajú susedné čísla 3 a 5. Pretože 5 je väčší ako 3, posunie sa na pravú stranu. (1 3 5 6 8) - V iterácii sa porovnávajú čísla 5 a 6, 6 a 8. Keďže je v požadovanom poradí, zachováva si poradie. (1 3 5 6 8) - Nakoniec sa iterácia zastaví, keď program prechádza porovnaním každého susedného prvku a zistí, že všetky číslice sú v rastúcom poradí.Pretože tu bolo len 5 prvkov poľa, ktoré bolo treba triediť, trvalo celkom iba 3 iterácie. So zvyšovaním prvkov v poli sa zvyšuje aj počet iterácií.
Implementácia triedenia bubliniek pomocou Java
Nižšie je uvedený kód Java, ktorý je implementáciou algoritmu Bubble sort. (Všimnite si, že prvá pozícia poľa v Java začína na 0 a pokračuje v prírastkoch 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ýkon:
Výhody a nevýhody triedenia bubliniek v Jave
Nižšie sú uvedené rôzne výhody a nevýhody bubliniek v jave:
výhody
- Kód je veľmi ľahko písateľný a zrozumiteľný. Zvyčajne to trvá iba pár minút.
- Implementácia je tiež veľmi jednoduchá.
- Triedenie bublín triedi čísla a uchováva ich v pamäti, čím šetrí veľa pamäte.
nevýhody
- Tento algoritmus nie je vhodný pre veľké súbory údajov, pretože porovnanie trvá veľa času. Čas potrebný na triedenie vstupných čísel exponenciálne narastá.
- O (n 2) je priemerná zložitosť Bubble sort a O (n) je najlepšia zložitosť prípadu (najlepší prípad je, keď sú prvky zoradené na prvom mieste), kde n je počet prvkov.
Aplikácie v reálnom čase
Pretože Bubble sort dokáže detekovať drobné chyby pri triedení, používa sa v počítačovej grafike. Používa sa tiež v algoritme výplne mnohouholníka, kde je potrebné triediť obloženie vrcholov polygónu.
záver
V tomto článku sme videli, ako funguje algoritmus triedenia Bubble a ako sa dá implementovať pomocou programovania Java. Bubble sort je veľmi stabilný algoritmus, ktorý možno ľahko implementovať pre pomerne malé množiny údajov. Ide o porovnávací algoritmus a pre jeho jednoduchosť ho používajú začiatočníci.
Odporúčané články
Toto je sprievodca triedením bubliniek v Jave. Tu diskutujeme o viacerých iteráciách na vykonanie bublinového triedenia v jave a jeho implementácii kódu spolu s výhodami a nevýhodami. Ďalšie informácie nájdete aj v nasledujúcich článkoch -
- Bublina Zoradiť v JavaScripte
- Triedenie v R.
- 3D polia v Jave
- Polia v C #
- Zoradenie bublín v Pythone