Introduktion til Bubble Sort i Java

Bobelsortering er en af ​​de mest almindeligt anvendte algoritmer til sortering af data i Java. Sortering her udføres ved rekursivt at sammenligne de tilstødende tal og flytte dem i stigende eller faldende rækkefølge efter behov. Denne forskydning af elementer udføres, indtil alle cifre er helt sorteret i den ønskede rækkefølge.

Navnet “Bubble sort” på denne algoritme skyldes, at elementerne i en matrix boble deres vej til starten af ​​den. Lad os forstå boble-sorteringsalgoritmen ved at tage et eksempel.

Eksempel: Overvej en række numre (6 1 8 5 3), der skal arrangeres i stigende rækkefølge.

Bubblesorteringsalgoritme fungerer i flere iterationer, indtil den finder ud af, at alle numrene er sorteret.

gentagelser

Herunder er iterationer udført i Bubble Sort i Java, som er som følger:

Første gentagelse

(6 1 8 5 3) - Det starter med at sammenligne de to første tal og flytter det mindste antal af de to til højre. Derfor er blandt 6 og 1, 1, det mindre antal forskydes til venstre og 6 til højre.

(1 6 8 5 3) - Herefter sammenligner de to tilstødende to numre ved at skifte en position til højre. Her er nummer 6 mindre end 8, og derfor bevares den samme rækkefølge.

(1 6 8 5 3) - Igen ved at skifte en position til højre finder sammenligningen sted mellem 8 og 5. Nummer 5 forskydes til venstre, da det er mindre end 8.

(1 6 5 8 3) - Her finder sammenligningen sted mellem numre 8 og 3. Nummer 3 forskydes til venstre, da det er mindre end 8.

(1 6 5 3 8) - Dette er det endelige resultat af ordren efter 1. iteration.

Anden Iteration

Da antallet stadig ikke er i stigende rækkefølge endnu, går programmet til den anden iteration.

(1 6 5 3 8) - Her starter sammenligningen igen fra de to første cifre i resultatet fra den første iteration. Den sammenligner nummer 1 og 6 og bevarer den samme rækkefølge, da 1 er mindre end 6.

(1 6 5 3 8) - Her sammenlignes numrene 5 og 6. Den samme rækkefølge bevares, da den allerede er i den krævede stigende rækkefølge.

(1 5 6 3 8) - Her finder sammenligningen sted mellem numrene 6 og 3. Nummer 3 forskydes til venstre, da det er mindre end 6.

(1 5 3 6 8) - Næste tal 6 og 8 sammenlignes med hinanden. Den samme ordre bevares, som den er i en forventet rækkefølge.

(1 5 3 6 8) - Dette er det endelige resultat efter den anden iteration. Vi kan stadig bemærke, at cifrene ikke er helt arrangeret i deres stigende rækkefølge. Vi er stadig nødt til at udveksle nummer 5 og 3 for at få det endelige resultat. Derfor går programmet til den tredje iteration.

Tredje gentagelse

(1 5 3 6 8) - Den tredje iteration starter med at sammenligne de første to cifre 1 og 5. Da ordren er som forventet, bevares den den samme.

(1 5 3 6 8) - Herefter sammenlignes de tilstødende numre 3 og 5. Da 5 er større end 3, flyttes den til højre side.

(1 3 5 6 8) - Iterationen fortsætter med at sammenligne numrene 5 og 6, 6 og 8. Da den er i den krævede rækkefølge, bevarer den ordren.

(1 3 5 6 8) - Endelig stoppes iterationen, da programmet gennemgår sammenligning af hvert tilstødende element og finder, at alle cifre er i stigende rækkefølge.

Da der kun var 5 elementer i en matrix, der skulle sorteres, tog det kun 3 iterationer i alt. Når elementerne i arrayet øges, øges mængden af ​​iterationer også.

Implementering af boble sortering ved hjælp af Java

Nedenfor er Java-koden, der er implementeringen af ​​Bubble-sorteringsalgoritmen. (Bemærk, at den første placering af en matrix i Java starter ved 0 og fortsætter i trin på 1 dvs. array (0), array (1), array (2), og den fortsætter.)

Kode:

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:

Fordele og ulemper ved Bubble Sort i Java

Nedenfor er de forskellige fordele og ulemper ved boble sortering i java:

Fordele

  1. Koden er meget let at skrive og forstå. Tager typisk kun et par minutter.
  2. Implementering er også meget let.
  3. Bubblesortering sorterer numrene og holder dem i hukommelsen og sparer derfor meget hukommelse.

Ulemper

  1. Denne algoritme er ikke egnet til store datasæt, da sammenligningen tager meget tid. Tiden det tager at sortere inputnumre øges eksponentielt.
  2. O (n 2) er den gennemsnitlige kompleksitet af Bubble-sort, og O (n) er den bedste case-kompleksitet (bedst er tilfældet, når elementerne sorteres i første omgang), hvor n er antallet af elementer.

Real-time applikationer

Da Bubble-sortering er i stand til at registrere små fejl i sorteringen, bruges den i computergrafik. Det bruges også i polygonudfyldningsalgoritmen, hvor knudepunktets foring af polygonen skal sorteres.

Konklusion

I denne artikel så vi, hvordan Bubble-sorteringsalgoritmen fungerer, og hvordan den kan implementeres ved hjælp af Java-programmering. Boblesortering er en meget stabil algoritme, der let kan implementeres til relativt små datasæt. Det er et tilfælde af sammenligningsalgoritme og bruges af begyndere på grund af dens enkelhed.

Anbefalede artikler

Dette er en guide til Bubble Sort i Java. Her diskuterer vi flere iterationer for at udføre boble sortering i java og dens kodeimplementering sammen med fordele og ulemper. Du kan også se på de følgende artikler for at lære mere -

  1. Bubble Sorter i JavaScript
  2. Sorterer i R
  3. 3D-arrays i Java
  4. Arrays i C #
  5. Bubble Sort i Python

Kategori:

Softwareudvikling