Introduksjon til Bubble Sort i Java

Boble sortering er en av de mest brukte algoritmene for å sortere data i Java. Sortering her gjøres ved rekursivt å sammenligne de tilstøtende tallene og flytte dem i økende eller avtagende rekkefølge etter behov. Denne forskyvningen av elementer gjøres til alle sifrene er fullstendig sortert i ønsket rekkefølge.

Navnet “Bubble sort” på denne algoritmen skyldes at elementene i en matrise boble seg til starten av den. La oss forstå boblesorteringsalgoritmen ved å ta et eksempel.

Eksempel: Tenk på en rekke tall (6 1 8 5 3) som må ordnes i økende rekkefølge.

Bubble sorteringsalgoritme fungerer i flere iterasjoner til den finner ut at alle tallene er sortert.

gjentakelser

Nedenfor er iterasjonene utført i Bubble Sort i Java som er som følger:

Første itterasjon

(6 1 8 5 3) - Det starter med å sammenligne de to første tallene og forskyver det minste tallet til de to til høyre. Derav blant 6 og 1 er 1 det mindre tallet forskjøvet til venstre og 6 til høyre.

(1 6 8 5 3) - Deretter sammenligner de to tilstøtende tall ved å forskyve en posisjon til høyre. Her er nummer 6 mindre enn 8 og følgelig beholdes samme rekkefølge.

(1 6 8 5 3) - Igjen ved å flytte en posisjon til høyre, vil sammenligningen finne sted mellom 8 og 5. Nummer 5 blir forskjøvet til venstre da det er mindre enn 8.

(1 6 5 8 3) - Her foregår sammenligningen mellom tall 8 og 3. Nummer 3 forskyves til venstre siden det er mindre enn 8.

(1 6 5 3 8) - Dette er det endelige resultatet av ordren etter 1. iterasjon.

Andre itterasjon

Siden tallene fremdeles ikke er helt i økende rekkefølge ennå, går programmet til den andre iterasjonen.

(1 6 5 3 8) - Her starter sammenligningen igjen fra de to første sifrene i resultatet fra den første iterasjonen. Den sammenligner nummer 1 og 6 og beholder den samme rekkefølgen siden 1 er mindre enn 6.

(1 6 5 3 8) - Her blir tallene 5 og 6 sammenlignet. Den samme ordren beholdes som den allerede er i den nødvendige økende rekkefølge.

(1 5 6 3 8) - Her finner man sammenligning mellom tall 6 og 3. Nummer 3 forskyves til venstre da det er mindre enn 6.

(1 5 3 6 8) - Neste tall 6 og 8 sammenlignes med hverandre. Den samme ordren beholdes som i en forventet rekkefølge.

(1 5 3 6 8) - Dette er det endelige resultatet etter den andre iterasjonen. Likevel kan vi merke at sifrene ikke er helt ordnet i sin økende rekkefølge. Fortsatt må vi bytte nummer 5 og 3 for å få det endelige resultatet. Derfor går programmet for den tredje iterasjonen.

Tredje Iterasjon

(1 5 3 6 8) - Den tredje iterasjonen starter med å sammenligne de to første sifrene 1 og 5. Siden ordren er som forventet, beholdes den den samme.

(1 5 3 6 8) - Deretter sammenlignes de tilstøtende tallene 3 og 5. Siden 5 er større enn 3, blir den forskjøvet til høyre side.

(1 3 5 6 8) - Iterasjonen fortsetter å sammenligne tallene 5 og 6, 6 og 8. Siden den er i ønsket rekkefølge, beholder den ordren.

(1 3 5 6 8) - Endelig stoppes iterasjonen når programmet går gjennom å sammenligne hvert tilstøtende element og finner ut at alle sifrene er i økende rekkefølge.

Siden det her bare var fem elementer av en matrise som måtte sorteres, tok det bare 3 iterasjoner totalt. Når elementene i arrayet øker, øker også mengden av iterasjoner.

Implementering av boble sortering ved hjelp av Java

Nedenfor er Java-koden som er implementeringen av Bubble-sorteringsalgoritmen. (Merk at den første posisjonen til en matrise i Java starter ved 0 og fortsetter i trinn på 1 dvs. matrise (0), matrise (1), matrise (2) og den fortsetter.)

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
)
)
)

Produksjon:

Fordeler og ulemper med Bubble Sort i Java

Nedenfor er de forskjellige fordeler og ulemper med boble sortering i java:

Fordeler

  1. Koden er veldig enkel å skrive og forstå. Det tar vanligvis bare noen få minutter.
  2. Implementering er også veldig enkelt.
  3. Bubblesortering sorterer tallene og holder dem i minnet og sparer dermed mye minne.

ulemper

  1. Denne algoritmen er ikke egnet for store datasett, siden sammenligningen tar mye tid. Tiden det tar å sortere inntastene øker eksponentielt.
  2. O (n 2) er den gjennomsnittlige kompleksiteten til Bubble sort og O (n) er den beste sakskompleksiteten (best case er når elementene er sortert i utgangspunktet) der n er antall elementer.

Sanntidsapplikasjoner

Siden Bubble sort er i stand til å oppdage småfeil i sortering, brukes den i datagrafikk. Det brukes også i polygonfyllingsalgoritmen der toppunktets fôr til polygonen må sorteres.

Konklusjon

I denne artikkelen så vi hvordan Bubble-sorteringsalgoritmen fungerer og hvordan den kan implementeres ved hjelp av Java-programmering. Bubble sort er en veldig stabil algoritme som enkelt kan implementeres for relativt små datasett. Det er et tilfelle av sammenligningsalgoritme og brukes av nybegynnere på grunn av sin enkelhet.

Anbefalte artikler

Dette er en guide til Bubble Sort i Java. Her diskuterer vi flere iterasjoner for å utføre boble sortering i java og dens implementering av kode sammen med fordeler og ulemper. Du kan også se på følgende artikler for å lære mer -

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

Kategori:

Programvare utvikling