Boble sorter med java

Bubble Sort er den enkleste sorteringsalgoritmen: Anta at det er elementer på rad som ikke er sortert. Boble -sortering skanner raden fra venstre, og bytter et tilstøtende par elementer som ikke er i riktig rekkefølge. Denne skanning av hele raden gjentas gjentatte ganger til hele raden er sortert. Hvis sorteringen skal stigende, byttes det tilstøtende paret for å gjøre elementet til venstre mindre enn elementet til høyre. Hvis sorteringen skal synkes, byttes det tilstøtende paret for å gjøre elementet til venstre større enn elementet til høyre.

Bubble Sort Illustrasjon uten kode

Tenk på følgende usorterte radliste over tegn i alfabetet:

Q w e r t y u i o p

Denne listen vil bli sortert i stigende rekkefølge som følger. I den første skanningen blir Q og W sammenlignet; Q er mindre enn W, så det er ingen bytte. Likevel, i den første skanningen, blir W og E sammenlignet; E er mindre enn w, så det bytter. Det nye tredje elementet, W, sammenlignes med R; R er mindre enn w, så det bytter. Det nye fjerde elementet, W, sammenlignes med T; T er mindre enn w, så det bytter. Det nye femte elementet, W, sammenlignes med Y; W er mindre enn y, og det er ingen bytte. Likevel, i den første skanningen, blir Y sammenlignet med U; U er mindre enn y, så det bytter. Det nye syvende elementet, Y, sammenlignes med i; Jeg er mindre enn y, og det bytter. Det nye åttende elementet, Y, sammenlignes med O; O er mindre enn y, og det bytter. Det nye niende elementet, Y, sammenlignes med P; P er mindre enn y, og det er bytte. Den første skanningen ender der. Resultatet for den første skanningen er,

Q e r t w u i o p y

Legg merke til at det største elementet er på slutten etter den første skanningen. Skanning av alle de resulterende ti elementene, og mulig bytte, gjentas igjen å ha:

E r q t u i o p w y

Legg merke til at det neste største elementet nå er det siste-men-ett-elementet, og det var ikke nødvendig å sammenligne det med det siste elementet, så en liten tid ville ikke vært bortkastet. Skanning av alle de resulterende ti elementene, og mulig bytte, gjentas igjen å ha:

E q r t i o p u w y

Legg merke til at det tredje største elementet mot slutten nå er på tredje plassering fra slutten, og at det ikke var behov for å sammenligne det med de to siste elementene, og ingen grunn til å sammenligne de to siste elementene selv, og så litt liten tid ville ikke blitt bortkastet. Skanning av alle de resulterende ti elementene, og mulig bytte, gjentas igjen å ha:

E q r i o p t u w y

Legg merke til at det fjerde største elementet mot slutten nå er på fjerde plassering fra slutten, og at det ikke var behov for å sammenligne det med de tre siste elementene, og ingen grunn til å sammenligne de tre siste elementene i seg selv, og så ville det ikke har blitt bortkastet. Skanning av alle de resulterende ti elementene, og mulig bytte, gjentas igjen å ha:

E q i o p r t u w y

Legg merke til at det femte største elementet mot slutten nå er på femte plassering fra slutten, og at det ikke var behov for å sammenligne det med de fire siste elementene, og ingen grunn til å sammenligne de fire siste elementene i seg selv, og at tiden ikke ville ha blitt bortkastet. Skanning av alle de resulterende ti elementene, og mulig bytte, gjentas igjen for å ha:

E i o p q r t u w y

Resten av skanningsresultatene er som følger:

E i o p q r t u w y
E i o p q r t u w y
E i o p q r t u w y
E i o p q r t u w y

Legg merke til at ingen sortering har funnet sted for disse fire siste resultatene.

Det motsatte av alle de ovennevnte algoritmene kan gjøres for sorterende synkende.

Optimalisering av boble -sortering

Fra den grunnleggende definisjonen av boble -sortering, hvis det er N -elementer, vil det være N komplette skanninger. En skanning er en iterasjon. Så, de ti elementene ovenfor betyr ti komplette iterasjoner. Den totale tiden for å boble sortering av en liste (matrise) kan reduseres for mange usorterte lister. Dette innebærer boble -sorteringsstrategier. Boble -sortering er optimalisert med to strategier.

Første optimaliseringsstrategi

Legg merke til ovenstående at etter den første komplette iterasjonen er det største elementet på slutten, og det ville være bortkastet tid å få tilgang til det i den andre iterasjonen. Etter den andre iterasjonen er de to siste elementene i sine rette posisjoner, og tiden skal ikke bli bortkastet tilgang til dem i den tredje iterasjonen. Dette betyr at den andre iterasjonen skal ende ved n-1. Etter den tredje iterasjonen er de tre siste elementene i sine rette posisjoner, og tiden skal ikke bli bortkastet tilgang til dem i den fjerde iterasjonen. Dette betyr at den tredje iterasjonen skal ende på N-2. Etter den fjerde iterasjonen er de fire siste elementene i sine rette posisjoner, og tiden skal ikke bli bortkastet tilgang til dem i den femte iterasjonen. Dette betyr at den fjerde iterasjonen skal ende på N-3. Dette fortsetter.

Fra den grunnleggende definisjonen av boble -sort, må iterasjonen gjøres n ganger. Hvis telleren for n iterasjonene er på i, bør iterasjonen få tilgang til n - I -elementer for å unngå å kaste bort tid på slutten av matrisen; og med jeg begynner fra 0. Så det må være to java for-loops: den ytre for-loop itererer n ganger, og den indre for-loop itererer n-i ganger, for matriseelementene, for hver av n ganger. Iterere en matrise n - i ganger er den første strategien.

Andre optimaliseringsstrategi

Skulle den ytre for-loop virkelig iterere n ganger? Skulle den ytre for-loop for listen ovenfor iterere 10 ganger? - Nei, fordi de fire siste iterasjonene ikke ville endre noe (det gjør ingen sortering). Dette betyr at listen er sortert så snart den blir oppdaget; den ytre sløyfen skal gå i stykker, så sortering skal stoppe. Dette vil spare mer tid. Dette kan oppnås ved å ha en boolsk variabel for ytre sløyfe, som vil forbli usant i indre sløyfe når du bytter stopper for å finne sted.

Java -kode for boble -sortering

Følgende klasse har metoden for å gjøre sortering:

klasse aclass
statisk tomrom Bubblesort (char arr [])
int n = arr.lengde;
boolsk byttet = falsk;
for (int i = 0; i < N; i++)
byttet = falsk;
for (int j = 1; j < N - i; j++)
if (arr [j] < arr[j - 1])
char temp = arr [j];
arr [j] = arr [j - 1];
arr [j - 1] = temp;
byttet = sant;


if (byttet == falsk) pause;

Legg merke til mens-betingelsen, “J < N - i;” for the inner for-loop, for the first strategy. Note the use of the boolean variable in the outer for-loop and the inner for-loop for the second strategy.

En passende hovedklasse for dette, er:

public class theclass
public static void main (String [] args)
char ar [] = 'q', 'w', 'e', ​​'r', 't', 'y', 'u', 'i', 'o', 'p';
En klasse.Bubblesort (AR);
for (int i = 0; iSystem.ute.print (ar [i]); System.ute.skrive ut(' ');

System.ute.println ();

Arrayen sendes med henvisning til Bubblesort () -metoden i en annen klasse. Så innholdet er endret. Utgangen er:

E i o p q r t u w y

Konklusjon

Boble -sorterer ved å bytte tilstøtende elementer fra begynnelsen til slutten av listen. Denne prosedyren gjentas igjen og igjen til hele listen er sortert helt. Sortering er enten stigende eller synker. Boble -sortering skal optimaliseres, som forklart ovenfor.