Sortering af algoritmer i Java - Forskellige typer sorteringsalgoritmer i Java

• Introduktion til sortering af algoritmer i Java

Introduktion til sortering af algoritmer i Java

At sortere informationerne i en bestemt rækkefølge, ofte inden for en matrixlignende ramme, er at arrangere dem. Du kan bruge forskellige sekvenskrav, populære er sortering af tal fra mindst til største eller omvendt eller leksikografisk sortering af strenge. Vi vil dække forskellige algoritmer, fra ineffektive, men intuitive alternativer til effektive algoritmer, der effektivt er implementeret i Java og på andre sprog, hvis du er interesseret i, hvordan sortering skal fungere.

Forskellige sorteringsalgoritmer i java

Der er forskellige sorteringsalgoritmer, og ikke alle af dem er lige så effektive. For at sammenligne dem og se, hvilke der er bedst, analyserer vi deres tidskompleksiteter.

1. Indsættelsessortering
2. Bubble Sort
3. Valgssortering
4. Flet sortering
5. Heapsort

1. Indsættelsessortering

Konceptet bag Insertion Sort opdeler området i de underområder, der er sorteret og usorteret. Den klassificerede del er ved starten af ​​varighed 1 og matcher den første (venstre side) komponent i matrixen. Vi bevæger os gennem arrayet og udvider den klassificerede del af arrayet med en komponent under hver iteration. Når vi udvider, placerer vi det friske element i den sorterede undergruppe. Vi gør dette ved at flytte alle elementerne til højre, indtil vi finder ud af, at vi ikke behøver at ændre den første komponent. Når den dristige del sorteres i stigende rækkefølge, for eksempel i følgende array, forekommer den:

1. 3 5 7 8 4 2 1 9 6: Overvej 4 og indsæt det er, hvad vi har brug for. 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+" ");
)
)
)

Produktion:

Efter denne metode udvidede en komponent den sorterede del, vi har nu fem i stedet for fire elementer. Hver iteration gør dette, og hele matrixen vil blive sorteret ved udgangen.

Bemærk: Dette skyldes, at vi er nødt til at overføre hele den klassificerede liste en efter en i hver iteration, som er O (n). For hver komponent i hver tabel skal vi gøre dette, hvilket indebærer, at det er O (n 2) afgrænset.2.

2. Bubble Sort

Hvis boblen ikke er i den krævede rækkefølge, fungerer den ved at udskifte nabokomponenter. Dette gentages, indtil alle komponenter er i orden fra starten af ​​arrayen. Vi ved, at hvis vi formår at udføre hele iterationen uden swaps, var alle elementer sammenlignet med deres tilstødende elementer i den ønskelige rækkefølge og i forlængelse heraf hele matrixen. Årsagen til Bubble Sort-algoritmen er, at tallene som "bobler op" i "jorden." Hvis du efter et bestemt beløb går gennem forekomsten igen (4 er et godt eksempel), vil du bemærke, at antallet langsomt bevæger sig til højre.

Trin til boble sortering er som følger:

1. 4 2 1 5 3: Her er første to tal ikke i den rigtige rækkefølge, og derfor er vi nødt til at sortere begge numre.
2. 2 4 1 5 3: Derefter er næste par nummer heller ikke i den rigtige rækkefølge. Så sortering sker igen.
3. 2 1 4 5 3: Disse to er i den rigtige rækkefølge, 4 <5, og det er derfor ikke nødvendigt at bytte dem.
4. 2 1 4 5 3 : Igen skal vi bytte for korrekt orden.
5. 2 1 4 3 5: Her er det resulterende array efter en iteration.
6. Vi er nødt til at gentage denne proces igen, indtil tallene er i korrekt orden.

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) + " ");
)
)
)

Produktion:

Bemærk: Det kan have havnet i en uendelig sløjfe, hvis jeg brugte en (i)> = a (i + 1), fordi denne forbindelse stadig ville være gyldig med ækvivalente komponenter og derfor altid bytte dem fra et element til et andet.

3. Valgssortering

Selection Sort opdeler arrayet i en række klassificeringer, der ikke er sorteret. Denne gang dannes imidlertid sorteringsundergruppen ved at indsætte i slutningen af ​​den sorterede matrix minimumselementet i den usorterede undergruppe ved at 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+" ");
)
)
)

Produktion:

Bemærk: Minimum er O (n) for arraystørrelsen, fordi alle komponenter skal kontrolleres. For hvert element i matrixen skal vi finde det minimum og gøre hele processen O (n 2) begrænset.

4. Flet sortering

Merge Sort bruger rekursion til at løse problemet med skillelinjen og erobringsmetoden mere effektivt end tidligere beskrevet algoritmer.

Dette træ viser, hvordan de rekursive opkald fungerer. Ned-pil markerede arrays er de arrays, som vi kalder funktion for, mens vi smelter sammen pil-arrays. Derefter følger du pilen til træets kant og vender derefter tilbage og flettes. Vi har 3 5 3 1 rækkevidde, så vi opdeler det i 3 5 4 og 2 1. Vi opdeler dem i deres dele for at sortere dem. Vi begynder at fusionere og sortere dem, når vi går, når vi kommer til bunden.

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 program har vi bedt brugeren om at indtaste input. Outputet vil være i sorteret rækkefølge baseret på brugerens input.

Produktion:

5. Heap Sort

Du skal først kende de rammer, som Heapsort fungerer på - dyngen, for at forstå, hvorfor den fungerer. Vi vil specifikt tale om en binær bunke, men du kan også generalisere dette til andre bunkekonstruktioner. En bunke er et træ, der opfylder bunkeens egenskab, nemlig at alle dets børn har forhold til hver knude. En bunke skal også være næsten færdig. En næsten komplet binær dybdedybde har en d-1-undertræ med den samme rod, og hver knude har en fuld, venstre undertræ med en venstre faldende.

Med andre ord får du et lavere og lavere antal (min-bunke) eller større og større (max-heap), når du bevæger dig ned ad træet. Her er en max-heap-forekomst:

1. 6 1 8 3 5 2 4 : Her er begge børnenes antal mindre end forælderen, hvorfor vi ikke behøver at ændre noget.
2. 6 1 8 3 5 2 4: Her, 5> 1, er vi nødt til at bytte dem. Vi er nødt til at heapify for 5.
3. 6 5 8 3 1 2 4: Begge børnenes antal er mindre, alt forbliver 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: Efter denne iteration får vi dette resultat.

Når vi har gentaget denne proces igen, får vi følgende resultater:

• 8 5 6 3 1 2 4

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

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

Produktion:

Du kan se det fra punkt til niveau på grafen, fra venstre mod højre. Hvad vi opnåede her, er, at når vi har den kth-komponent i matrixen, er dens børns position 2 \ * k + 1 og 2 \ * k + 2 (forudsat at indeksering begynder ved 0). Dette kan overvåges af dig. Forældrenes position er altid (k-1) / 2 for den kth-komponent. Du kan nemt "maksimal heap up" ethvert interval, fordi du ved det. Kontroller, om et af dets børn er lavere end for hver komponent. I så fald skal du parre en forælder og gentage dette trin rekursivt med forælderen.

Bemærk: Da iterering af for-loops over hele matrixen gør heapSort) (åbenlyst O (N), ville det skabe Heapsort O's samlede kompleksitet (nlog n). Heapsort har en type på stedet, hvilket betyder, at det kræver O ( 1) mere plads end Flet sortering, men det har nogle ulemper, såsom paralleller, der er svære.

Konklusion - Sortering af algoritmer i Java

Sortering er en meget udbredt procedure med datasæt, hvad enten det er til yderligere analyse, hurtig søgning med mere effektive algoritmer, der er afhængige af sorteret information, filtrering af information osv. Sortering er godkendt af flere sprog, og ofte skjuver grænsefladerne, hvad programmøren gør.

Anbefalede artikler

Dette er en guide til sortering af algoritmer i Java. Her diskuterer vi forskellige typer sortering i Java sammen med deres algoritmer. Du kan også gennemgå vores andre foreslåede artikler -

1. Flet sorteringsalgoritmer i Java
2. JComboBox i Java
3. StringBuffer i Java
4. JTextField i Java
5. Heap Sort i Python
6. Hurtig sorteringsalgoritmer i Java
7. Komplet guide til sortering i C # med eksempler
8. Sortering af algoritmer i JavaScript
9. Vejledning til eksempler på C ++ algoritme
10. Komplet guide til sortering af algoritmer i Python