Sorteeralgoritmen in Java - Verschillende soorten sorteeralgoritmen in Java

• Inleiding tot sorteeralgoritmen in Java

Inleiding tot sorteeralgoritmen in Java

Om de informatie in een bepaalde volgorde te sorteren, vaak binnen een matrixachtig kader, is ze ordenen. U kunt verschillende reeksvereisten gebruiken, populaire zijn het sorteren van getallen van minste tot grootste of omgekeerd, of lexicografisch sorteren van tekenreeksen. We zullen verschillende algoritmen behandelen, van ineffectieve maar intuïtieve alternatieven tot efficiënte algoritmen die effectief zijn geïmplementeerd in Java en in andere talen als u geïnteresseerd bent in hoe sorteren moet werken.

Verschillende sorteeralgoritmen in Java

Er zijn verschillende sorteeralgoritmen en ze zijn niet allemaal even effectief. Om ze te vergelijken en te zien welke het beste presteren, zullen we hun tijdcomplexiteit analyseren.

1. Invoegsortering
2. Bubble Sort
3. Selectie sorteren
4. Sorteren samenvoegen
5. Heapsort

1. Invoegsortering

Het concept achter Insertion Sort verdeelt het bereik in de subreeksen die zijn gesorteerd en ongesorteerd. Het geclassificeerde gedeelte bevindt zich aan het begin van duur 1 en komt overeen met de eerste (linkerkant) component in de array. We gaan door de array en breiden het geclassificeerde deel van de array met één component uit tijdens elke iteratie. Wanneer we uitbreiden, plaatsen we het nieuwe element in de gesorteerde subarray. We doen dit door alle elementen naar rechts te verplaatsen totdat we merken dat we de eerste component niet hoeven te wijzigen. Wanneer het vetgedrukte gedeelte in oplopende volgorde wordt gesorteerd, bijvoorbeeld in de volgende array, gebeurt dit:

1. 3 5 7 8 4 2 1 9 6: Overweeg 4 en dit in te voegen is wat we nodig hebben. We zijn aan het verschuiven sinds 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

Code:

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

Output:

Volgens deze methode breidde één component het gesorteerde deel uit, we hebben nu vijf in plaats van vier elementen. Elke iteratie doet dit en de hele array wordt aan het einde gesorteerd.

Opmerking: Dit komt omdat we de hele geclassificeerde lijst één voor één moeten overbrengen in elke iteratie, wat O (n) is. Voor elke component in elke tabel moeten we dit doen, wat inhoudt dat het O (n 2) begrensd is.

2. Bellen sorteren

Als de bel niet in de vereiste volgorde staat, werkt hij door naburige componenten te vervangen. Dit wordt herhaald totdat alle componenten in orde zijn vanaf het begin van de array. We weten dat als we erin slagen om de hele iteratie zonder swaps te doen, alle items vergeleken met hun aangrenzende elementen in de gewenste volgorde waren en, bij uitbreiding, de hele array. De reden voor het Bubble Sort-algoritme is dat de getallen zoals "omhoog bellen" in de "grond". Als u na een bepaald aantal opnieuw door de instantie gaat (4 is een goede instantie), zult u merken dat het nummer langzaam gaat naar rechts.

Stappen om bellen te sorteren zijn als volgt:

1. 4 2 1 5 3: Hier zijn de eerste twee cijfers niet in de juiste volgorde, daarom moeten we beide nummers sorteren.
2. 2 4 1 5 3: Daarna is het volgende paar nummers ook niet in de juiste volgorde. Dus sorteren gebeurt opnieuw.
3. 2 1 4 5 3: Deze twee staan ​​in de juiste volgorde, 4 <5, daarom hoeven ze niet te worden verwisseld.
4. 2 1 4 5 3 : Opnieuw moeten we ruilen voor de juiste volgorde.
5. 2 1 4 3 5: Hier is de resulterende array na één iteratie.
6. We moeten dit proces opnieuw herhalen totdat de nummers in de juiste volgorde staan.

Code:

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

Output:

Opmerking: het is misschien in een oneindige lus terechtgekomen als ik een (i)> = a (i + 1) heb gebruikt, omdat die verbinding nog steeds geldig is met equivalente componenten en deze dus altijd van het ene element naar het andere verwisselt.

3. Selectie sorteren

Selectie sorteren splitst de array in een reeks classificaties die niet zijn gesorteerd. Deze keer wordt de sorteersubarray echter gevormd door aan het einde van de gesorteerde array het minimumelement van de ongesorteerde subarray in te voegen, door te wisselen:

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

Code:

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

Output:

Opmerking: het minimum is O (n) voor de array-grootte omdat alle componenten moeten worden gecontroleerd. Voor elk element van de array moeten we het minimum vinden en het hele proces O (n 2) beperkt maken.

4. Sorteren samenvoegen

Merge Sort gebruikt recursie om het probleem van de verdeel- en veroveringsmethode effectiever op te lossen dan eerder beschreven algoritmen.

Deze boom laat zien hoe de recursieve oproepen werken. Arrays met pijl omlaag zijn de arrays waarvoor we functie aanroepen, terwijl we pijlarrays fuseren. Volg dan de pijl naar de rand van de boom en keer dan terug en voeg samen. We hebben een bereik van 3 5 3 1, dus we splitsen het in 3 5 4 en 2 1. We splitsen ze in hun delen om ze te sorteren. We beginnen ze te fuseren en sorteren terwijl we naar de bodem gaan.

Code:

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

In dit programma hebben we de gebruiker gevraagd om invoer in te voeren. De uitvoer is in gesorteerde volgorde op basis van de invoer van de gebruiker.

Output:

5. Heap sorteren

Je moet eerst het raamwerk kennen waarop Heapsort werkt - de hoop - om te begrijpen waarom het werkt. We zullen het specifiek hebben over een binaire heap, maar je kunt dit ook generaliseren naar andere heap-constructies. Een hoop is een boom die de eigenschap van de hoop vervult, namelijk dat al zijn kinderen relaties hebben met elk knooppunt. Een hoop moet ook bijna af zijn. Een bijna volledige d-diepte binary heeft een d-1 substructuur, met dezelfde root, en elke knoop heeft een volledige, ondertitels links, met een naar links aflopende.

Met andere woorden, je krijgt een lager en lager nummer (min-heap) of groter en groter (max-heap) wanneer je door de boom naar beneden beweegt. Hier is een max-heap-instantie:

1. 6 1 8 3 5 2 4 : Hier zijn de aantallen van beide kinderen kleiner dan die van de ouder, vandaar dat we niets hoeven te veranderen.
2. 6 1 8 3 5 2 4: Hier, 5> 1, moeten we ze verwisselen. We moeten 5 heapify.
3. 6 5 8 3 1 2 4: Beide aantallen kinderen zijn kleiner, alles blijft hetzelfde.
4. 6 5 8 3 1 2 4: Hier, 8> 6, daarom moeten we ze ruilen.
5. 8 5 6 3 1 2 4: Na deze iteratie zullen we dit resultaat krijgen.

Na het herhalen van dit proces zullen we de volgende resultaten krijgen:

• 8 5 6 3 1 2 4

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

Code:

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

Output:

U kunt het van punt tot niveau in de grafiek bekijken, van links naar rechts. Wat we hier hebben bereikt, is dat wanneer we de component kth in de array hebben, de positie van de onderliggende elementen 2 \ * k + 1 en 2 \ * k + 2 is (ervan uitgaande dat het indexeren begint bij 0). Dit kan door u worden gemonitord. De positie van de ouder is altijd (k-1) / 2 voor de kth-component. Je kunt elk bereik gemakkelijk “ophopen”, omdat je dat weet. Controleer of een van zijn kinderen lager is dan die voor elk onderdeel. Zo ja, koppel een ouder en herhaal deze stap recursief met de ouder.

Opmerking: aangezien het herhalen van for-lussen in de hele array heapSort maakt) (uiteraard O (N), zou het de algehele complexiteit van Heapsort O creëren (nlog n). Heapsort heeft een type ter plaatse, wat betekent dat het O vereist ( 1) meer ruimte dan Sorteer samenvoegen, maar het heeft enkele nadelen, zoals moeilijke parallellen.

Conclusie - Sorteeralgoritmen in Java

Sorteren is een veel voorkomende procedure met gegevenssets, of voor verdere analyse, het versnellen van zoeken met effectievere algoritmen op basis van gesorteerde informatie, filteren van informatie, enz. Sorteren wordt door verschillende talen onderschreven en vaak verbergen de interfaces wat de programmeur doet.

Aanbevolen artikelen

Dit is een gids voor het sorteren van algoritmen in Java. Hier bespreken we verschillende soorten sorteren in Java, samen met hun algoritmen. U kunt ook onze andere voorgestelde artikelen doornemen -

1. Sorteeralgoritmen in Java samenvoegen
2. JComboBox in Java
3. StringBuffer in Java
4. JTextField in Java
5. Heap Sort in Python
6. Snel sorteren algoritmen in Java
7. Volledige gids voor sorteren in C # met voorbeelden
8. Sorteeralgoritmen in JavaScript
9. Handleiding voor voorbeelden van C ++ algoritme
10. Complete gids voor het sorteren van algoritmen in Python