Introduktion till Bubble Sort i Java
Bubblesortering är en av de mest använda algoritmerna för att sortera data i Java. Sortering här görs genom att rekursivt jämföra de angränsande siffrorna och flytta dem i ökande eller minskande ordning efter behov. Denna förskjutning av element görs tills alla siffror är helt sorterade i önskad ordning.
Namnet "Bubble sort" på denna algoritm beror på att elementen i en matris bubblar sig till början av den. Låt oss förstå bubblasorteringsalgoritmen genom att ta ett exempel.
Exempel: Tänk på en mängd siffror (6 1 8 5 3) som måste ordnas i ökande ordning.
Bubblesorteringsalgoritm fungerar i flera iterationer tills den upptäcker att alla nummer är sorterade.
iterationer
Nedan visas iterationerna som utförs i Bubble Sort i Java som är följande:
Första Iteration
(6 1 8 5 3) - Det börjar med att jämföra de två första siffrorna och förskjuter det mindre antalet av dem till höger. Därför bland 6 och 1 är 1 det mindre antalet flyttas till vänster och 6 till höger. (1 6 8 5 3) - Därefter jämförs de intilliggande två siffrorna genom att flytta en position till höger. Här är nummer 6 mindre än 8 och följaktligen bibehålls samma ordning. (1 6 8 5 3) - Återigen genom att flytta en position till höger jämförelse sker mellan 8 och 5. Nummer 5 flyttas till vänster eftersom det är mindre än 8. (1 6 5 8 3) - Här sker jämförelsen mellan siffrorna 8 och 3. Nummer 3 flyttas till vänster eftersom det är mindre än 8. (1 6 5 3 8) - Detta är slutresultatet av beställningen efter första iterationen.Andra Iteration
Eftersom antalet fortfarande inte är helt i sin ökande ordning, går programmet för den andra iterationen.
(1 6 5 3 8) - Här börjar jämförelsen igen från de två första siffrorna i resultatet från den första iterationen. Den jämför siffrorna 1 och 6 och behåller samma ordning eftersom 1 är mindre än 6. (1 6 5 3 8) - Här jämförs siffrorna 5 och 6. Samma ordning behålls eftersom den redan är i önskad ökande ordning. (1 5 6 3 8) - Här jämförelse mellan siffrorna 6 och 3. Skiftas nummer 3 till vänster eftersom det är mindre än 6. (1 5 3 6 8) - Nästa nummer 6 och 8 jämförs med varandra. Samma ordning behålls som i en förväntad ordning. (1 5 3 6 8) - Detta är det slutliga resultatet efter den andra iterationen. Vi kan ändå märka att siffrorna inte är ordnade i sin ökande ordning. Vi måste fortfarande byta nummer 5 och 3 för att få det slutliga resultatet. Därför går programmet för den tredje iterationen.Tredje Iteration
(1 5 3 6 8) - Den tredje iterationen börjar med att jämföra de första två siffrorna 1 och 5. Eftersom ordningen är som förväntat behålls den på samma sätt. (1 5 3 6 8) - Därefter jämförs de angränsande siffrorna 3 och 5. Eftersom 5 är större än 3 flyttas den till höger sida. (1 3 5 6 8) - Iterationen jämförs siffrorna 5 och 6, 6 och 8. Eftersom den är i önskad ordning behåller den ordningen. (1 3 5 6 8) - Slutligen stoppas iterationen när programmet går igenom att jämföra varje angränsande element och finner att alla siffror är i ökande ordning.Eftersom det här bara fanns fem element i en matris som behövde sorteras, tog det bara 3 iterationer totalt. När elementen i matrisen ökar ökar mängden iterationer också.
Bubble Sort Implementation med Java
Nedan är Java-koden som är implementeringen av Bubble-sorteringsalgoritmen. (Observera att den första positionen för en matris i Java börjar vid 0 och fortsätter i steg om 1 dvs. array (0), array (1), array (2) och den fortsätter.)
Koda:
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
)
)
)
Produktion:
Fördelar och nackdelar med Bubble Sort i Java
Nedan finns de olika fördelarna och nackdelarna med bubbelsorter i java:
fördelar
- Koden är mycket lätt att skriva och förstå. Vanligtvis tar bara några minuter.
- Implementering är också mycket lätt.
- Bubble sortering sorterar siffrorna och håller dem i minnet sparar därför mycket minne.
nackdelar
- Denna algoritm är inte lämplig för stora datasätt eftersom jämförelsen tar mycket tid. Tiden det tar att sortera inmatningsnummer ökar exponentiellt.
- O (n 2) är den genomsnittliga komplexiteten för Bubble sort och O (n) är den bästa fallkomplexiteten (bästa fallet är när elementen sorteras i första hand) där n är antalet element.
Realtidsapplikationer
Eftersom Bubble sortering kan upptäcka minutfel vid sortering används den i datorgrafik. Det används också i algoritmen för polygonfyllning där vertikonets foder måste sorteras.
Slutsats
I den här artikeln såg vi hur Bubble-sorteringsalgoritmen fungerar och hur den kan implementeras med Java-programmering. Bubble sort är en mycket stabil algoritm som enkelt kan implementeras för relativt små datasätt. Det handlar om jämförelsealgoritm och används av nybörjare på grund av dess enkelhet.
Rekommenderade artiklar
Detta är en guide till Bubble Sort i Java. Här diskuterar vi flera iterationer för att utföra bubblasortering i java och dess kodimplementering tillsammans med fördelar och nackdelar. Du kan också titta på följande artiklar för att lära dig mer -
- Bubble Sortera i JavaScript
- Sorterar i R
- 3D-matriser i Java
- Matriser i C #
- Bubble Sort i Python