Sortering av algoritmer i Java - Ulike typer sorteringsalgoritmer i Java

• Introduksjon til sortering av algoritmer i Java

Introduksjon til sortering av algoritmer i Java

Å sortere informasjonen i en viss rekkefølge, ofte innenfor en matrikklignende ramme, er å ordne dem. Du kan bruke forskjellige sekvenskrav, populære er sortering av tall fra minst til største eller omvendt, eller leksikografisk sortering av strenger. Vi vil dekke forskjellige algoritmer, fra ineffektive, men intuitive alternativer til effektive algoritmer som er effektivt implementert i Java og på andre språk hvis du er interessert i hvordan sortering skal fungere.

Ulike sorteringsalgoritmer i java

Det er forskjellige sorteringsalgoritmer, og ikke alle er like effektive. For å sammenligne dem og se hvilke som gir best resultater, vil vi analysere tidskompleksitetene.

1. Innsettingssortering
2. Bubble Sort
3. Valgssortering
4. Slå sammen sortering
5. Heapsort

1. Innsettingssortering

Konseptet bak Insertion Sort deler rekkevidden i delområdene som er sortert og usortert. Den klassifiserte delen er i begynnelsen av varighet 1 og samsvarer med den første (venstre side) komponenten i matrisen. Vi beveger oss gjennom matrisen og utvider den klassifiserte delen av matrisen med en komponent under hver iterasjon. Når vi utvider, plasserer vi det ferske elementet i den sorterte undergruppen. Dette gjør vi ved å flytte alle elementene til høyre til vi finner ut at vi ikke trenger å endre den første komponenten. Når den dristige delen er sortert i stigende rekkefølge, for eksempel i følgende gruppe, oppstår det:

1. 3 5 7 8 4 2 1 9 6: Tenk på 4 og sett inn dette er hva vi trenger. Vi har skiftet siden 8> 4
2. 2. 3 5 7 x 8 2 1 9 6
3. 3 5 x 7 8 2 1 9 6
4. 3 x 5 7 8 2 1 9 6
5. 3 4 5 7 8 2 1 9 6

Kode:

public class InsertionSortEx (
public static void insertionSort(int() arr) (
for (int x = 1; x < arr.length; x++) (
int current = arr(x);
int y = x - 1;
while(y >= 0 && current < arr(y)) (
arr(y+1) = arr(y);
y--;
)
arr(y+1) = current;
)
)
public static void main(String a())(
int() arr1 = (3, 5, 7, 8, 4, 2, 1, 9, 6);
System.out.println("Before Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
System.out.println();
insertionSort(arr1);//sorting array using insertion sort
System.out.println("After Insertion Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
)
)

Produksjon:

Etter denne metoden utvidet en komponent den sorterte delen, vi har nå fem i stedet for fire elementer. Hver iterasjon gjør dette, og hele matrisen vil bli sortert mot slutten.

Merk: Dette er fordi vi må overføre hele den klassifiserte listen en etter en i hver iterasjon, som er O (n). For hver komponent i hver tabell må vi gjøre dette, noe som innebærer at det er O (n 2) avgrenset.2.

2. Bubble Sort

Hvis boblen ikke er i ønsket rekkefølge, fungerer den ved å bytte ut nabokomponenter. Dette gjentas til alle komponentene er i orden fra starten av matrisen. Vi vet at hvis vi klarer å gjøre hele iterasjonen uten bytter, var alle elementene sammenlignet med deres tilstøtende elementer i ønsket rekkefølge og i forlengelse av det hele arrayet. Årsaken til Bubble Sort-algoritmen er at tallene som "bobler opp" i "bakken." Hvis du etter et bestemt beløp går gjennom forekomsten igjen (4 er et godt eksempel), vil du merke at tallet sakte beveger seg til høyre.

Trinn for å boble sortering er som følger:

1. 4 2 1 5 3: Her er første nummer to ikke i riktig rekkefølge, og derfor må vi sortere begge tallene.
2. 2 4 1 5 3: Etter det er neste antall par heller ikke i riktig rekkefølge. Så skjer sortering igjen.
3. 2 1 4 5 3: Disse to er i riktig rekkefølge, 4 <5, derfor er det ikke nødvendig å bytte dem.
4. 2 1 4 5 3 : Igjen må vi bytte for riktig orden.
5. 2 1 4 3 5: Her er den resulterende matrisen etter en iterasjon.
6. Vi må gjenta denne prosessen igjen til tallene er i riktig rekkefølge.

Kode:

public class BubbleSortExample (
public static void bubbleSort(int() arr) (
int n = arr.length;
int tmp = 0;
for(int x=0; x < n; x++)(
for(int y=1; y < (nx); y++)(
if(arr(y-1) > arr(y))(
//swap elements
tmp = arr(y-1);
arr(y-1) = arr(y);
arr(y) = tmp;
)
)
)
)
public static void main(String() args) (
int arr() =(4, 2, 1, 5, 3);
System.out.println("Array Before Bubble Sort");
for(int x=0; x < arr.length; x++)(
System.out.print(arr(x) + " ");
)
System.out.println();
bubbleSort(arr);
System.out.println("Array After Bubble Sort");
for(int x=0; x < arr.length; x++)(
System.out.print(arr(x) + " ");
)
)
)

Produksjon:

Merk: Det kan ha havnet i en uendelig sløyfe hvis jeg brukte en (i)> = a (i + 1), fordi den tilkoblingen fortsatt ville være gyldig med ekvivalente komponenter og dermed alltid bytte dem fra ett element til et annet.

3. Utvalgssortering

Valgssortering deler arrayen i en rekke klassifiseringer som ikke er sortert. Denne gangen blir imidlertid sorteringsundersnittet dannet ved å sette inn på slutten av den sorterte matrisen minimumselementet i den usorterte undergruppen, ved å bytte:

1. 3 5 1 2 4
2. 1 5 3 2 4
3. 1 2 3 5 4
4. 1 2 3 5 4
5. 1 2 3 4 5
6. 1 2 3 4 5

Kode:

public class SelectionSortEx (
public static void selectionSort(int() arr)(
for (int x = 0; x < arr.length - 1; x++)
(
int indx = x;
for (int y = x + 1; y < arr.length; y++)(
if (arr(y) < arr(indx))(
indx = y;
)
)
int smallNumber = arr(indx);
arr(indx) = arr(x);
arr(x) = smallNumber;
)
)
public static void main(String a())(
int() arr1 = (3, 5, 1, 2, 4);
System.out.println("Before Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
System.out.println();
selectionSort(arr1);
System.out.println("After Selection Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
)
)

Produksjon:

Merk: Minimumsnivået er O (n) for matrisestørrelsen fordi alle komponentene må kontrolleres. For hvert element i matrisen, må vi finne det minste og begrense hele prosessen O (n 2).

4. Slå sammen sortering

Merge Sort benytter rekursjon for å fikse problemet med skillet og erobringen metoden mer effektivt enn tidligere beskrevne algoritmer.

Dette treet viser hvordan de rekursive samtalene fungerer. Pil ned markerte matriser er matriser som vi kaller funksjon for mens vi smelter sammen pil-arrays. Så følger du pilen til trekanten, og deretter går du tilbake og fusjonerer. Vi har 3 5 3 1 rekkevidde, så vi delte det inn i 3 5 4 og 2 1. Vi delte dem inn i deres deler for å sortere dem. Vi begynner å smelte sammen og sortere dem når vi kommer til bunns.

Kode:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class MergeSort (
static void merge(int() array, int lowval, int midval, int highval)(
int x, y, k;
int() c= new int(highval-lowval+1);
k = 0;
x=lowval;
y=midval+1;
while(x<=midval && y<=highval)(
if(array(x)<=array(y))(
c(k++) = array(x++);
)
else(
c(k++) = array(y++);
)
)
while(x<=midval)(
c(k++) = array(x++);
)
while(y<=highval)(
c(k++) = array(y++);
)
k=0;
for(x = lowval; x<=highval; x++)(
array(x) = c(k++);
)
)
static void mergeSort(int() array, int lowval, int highval)(
if(highval-lowval+1>1)(
int midval = (lowval+highval)/2;
mergeSort(array, lowval, midval);
mergeSort(array, midval+1, highval);
merge(array, lowval, midval, highval);
)
)
public static void main(String() args) (
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
int size;
System.out.println("Enter the array");
try (
size = Integer.parseInt(r.readLine());
) catch (Exception e) (
System.out.println("Please Enter valid Input");
return;
)
int() array = new int(size);
System.out.println("Enter array elements");
int x;
for (x = 0; x < array.length; x++) (
try (
array(x) = Integer.parseInt(r.readLine());
) catch (Exception e) (
System.out.println("An error Occurred");
)
)
System.out.println("After Sorting");
System.out.println(Arrays.toString(array));
mergeSort(array, 0, array.length-1);
System.out.println("Before Merge Sorting");
System.out.println(Arrays.toString(array));
)
)

I dette programmet har vi bedt brukeren legge inn innspill. Utgangen vil være i sortert rekkefølge basert på brukerens inngang.

Produksjon:

5. Heap Sort

Du må først kjenne til rammene som Heapsort opererer - dyngen for å forstå hvorfor den fungerer. Vi vil spesifikt snakke om en binær haug, men du kan også generalisere dette til andre haugkonstruksjoner. En haug er et tre som oppfyller haugens eiendom, nemlig at alle barna har forhold til hver node. En haug må også være nesten ferdig. En nesten fullstendig d-dybde binær har en d-1 undertree, med den samme roten, og hver node har en full, venstre undertree, med en venstre synkende.

Med andre ord får du et lavere og lavere tall (min-haug) eller større og større (maks-haug) når du beveger deg nedover treet. Her er en max-heap-forekomst:

1. 6 1 8 3 5 2 4 : Her er begge barnas antall mindre enn foreldrene, og derfor trenger vi ikke å endre noe.
2. 6 1 8 3 5 2 4: Her, 5> 1, må vi bytte dem. Vi må heapify for 5.
3. 6 5 8 3 1 2 4: Begge barnas antall er mindre, alt forblir det samme.
4. 6 5 8 3 1 2 4: Her, 8> 6, derfor bør vi bytte dem.
5. 8 5 6 3 1 2 4: Etter denne iterasjonen vil vi få dette resultatet.

Etter å ha gjentatt denne prosessen igjen, får vi følgende resultater:

• 8 5 6 3 1 2 4

1. 4 5 6 3 1 2 8 : Bytting
2. 6 5 4 3 1 2 8 : Heapify
3. 2 5 4 3 1 6 8 : Bytting
4. 5 2 4 2 1 6 8 : Heapify
5. 1 2 4 2 5 6 8 : Bytting

Kode:

public class HeapSort
(
public void sort(int arr())
(
int n = arr.length;
for (int x = n / 2 - 1; x >= 0; x--)
heapify(arr, n, x);
for (int x=n-1; x>=0; x--)
int tmp = arr(0);
arr(0) = arr(x);
arr(x) = tmp;
heapify(arr, x, 0);
)
)
void heapify(int arr(), int n, int x)
(
int largest = x;
int L = 2*x + 1;
int r = 2*x + 2;
if (L arr(largest))
largest = L;
if (r arr(largest))
largest = r;
if (largest != x)
(
int swap = arr(x);
arr(x) = arr(largest);
arr(largest) = swap;
heapify(arr, n, largest);
)
)
static void printArray(int arr())
(
int n = arr.length;
for (int x=0; x System.out.print(arr(x)+" ");
System.out.println();
)
public static void main(String args())
(
int arr() = (6, 1, 8, 3, 5, 2, 4);
int n = arr.length;
System.out.println("Before Sorting:");
printArray(arr);
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("After Heap Sorting:");
printArray(arr);
)
) public class HeapSort
(
public void sort(int arr())
(
int n = arr.length;
for (int x = n / 2 - 1; x >= 0; x--)
heapify(arr, n, x);
for (int x=n-1; x>=0; x--)
int tmp = arr(0);
arr(0) = arr(x);
arr(x) = tmp;
heapify(arr, x, 0);
)
)
void heapify(int arr(), int n, int x)
(
int largest = x;
int L = 2*x + 1;
int r = 2*x + 2;
if (L arr(largest))
largest = L;
if (r arr(largest))
largest = r;
if (largest != x)
(
int swap = arr(x);
arr(x) = arr(largest);
arr(largest) = swap;
heapify(arr, n, largest);
)
)
static void printArray(int arr())
(
int n = arr.length;
for (int x=0; x System.out.print(arr(x)+" ");
System.out.println();
)
public static void main(String args())
(
int arr() = (6, 1, 8, 3, 5, 2, 4);
int n = arr.length;
System.out.println("Before Sorting:");
printArray(arr);
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("After Heap Sorting:");
printArray(arr);
)
)

Produksjon:

Du kan se den fra punkt til nivå på grafen, fra venstre til høyre. Det vi oppnådde her, er at når vi har den kth-komponenten i matrisen, er plasseringen av barna 2 \ * k + 1 og 2 \ * k + 2 (forutsatt at indekseringen begynner på 0). Dette kan overvåkes av deg. Foreldres plassering er alltid (k-1) / 2 for kth-komponenten. Du kan lett “maksimal øke” ethvert område, fordi du vet det. Sjekk om et av barna er lavere enn det for hver komponent. I så fall, par den ene forelderen og gjenta dette trinnet rekursivt med forelderen.

Merk: Siden iterating for-loops over hele matrisen gjør heapSort) (tydeligvis O (N), vil det skape Heapsort Os generelle kompleksitet (nlog n). Heapsort har en type på stedet, som betyr at den krever O ( 1) mer rom enn Merge Sort, men det har noen ulemper, for eksempel paralleller som er harde.

Konklusjon - Sortering av algoritmer i Java

Sortering er en veldig utbredt prosedyre med datasett, enten det er for videre analyse, raskere søk med mer effektive algoritmer avhengig av sortert informasjon, filtrering av informasjon osv. Sortering er godkjent av flere språk og ofte skjuler grensesnittene hva programmereren gjør.

Anbefalte artikler

Dette er en guide til sortering av algoritmer i Java. Her diskuterer vi forskjellige typer sortering i Java sammen med algoritmene deres. Du kan også gå gjennom andre foreslåtte artikler -

1. Slå sammen sorteringsalgoritmer i Java
2. JComboBox i Java
3. StringBuffer i Java
4. JTextField i Java
5. Heap Sort in Python
6. Rask sorteringsalgoritmer i Java
7. Komplett guide til sortering i C # med eksempler
8. Sortering av algoritmer i JavaScript
9. Veiledning til eksempler på C ++ algoritme
10. Komplett guide til sortering av algoritmer i Python