Introductie over invoegsortering in Java
Als je een programmeur bent, moet je waarschijnlijk al veel gehoord hebben over sorteren. Sorteren is in feite het rangschikken van de elementen in oplopende volgorde of in aflopende volgorde. Er zijn zoveel sorteeralgoritmen beschikbaar om de elementen te sorteren en elk algoritme heeft verschillende manieren om te sorteren, verschillende complexiteit. Het hangt dus af van het specifieke scenario en het aantal elementen over welk algoritme moet worden gebruikt. Het inbrengen is ook een van de meest gebruikte sorteeralgoritmen met de complexiteit van O (n 2) in het algemeen en wordt uitgevoerd alsof we de speelkaarten in onze handen sorteren. In dit onderwerp gaan we meer te weten over Insertion Sort in Java.
Hoe werkt invoegsortering in Java?
Laten we de werking van Invoegsortering begrijpen aan de hand van een voorbeeld. Stel dat er een array is met de naam arr met de onderstaande elementen:
10 5 8 20 30 2 9 7
Stap # 1 - Invoegsortering begint met het 2e element van de array, dat wil zeggen 5, rekening houdend met het 1e element van de array op zichzelf. Nu wordt het element 5 vergeleken met 10, omdat 5 minder is dan 10, dus 10 wordt 1 positie vooruit verplaatst en 5 wordt er vóór ingevoegd.
Nu is de resulterende array:
5 10 8 20 30 2 9 7
Stap # 2 - Nu wordt het element arr (2), dwz 8 vergeleken met het element arr (1), dwz 10. Omdat 8 kleiner is dan het voorgaande element 10, wordt het een stap vooruit van zijn positie verschoven en dan is het vergeleken met 5. Omdat 8 groter is dan 5, wordt het erachter ingevoegd.
Dan is de resulterende array:
5 8 10 20 30 2 9 7
Stap # 3 - Nu wordt het element 20 vergeleken met 10, aangezien het groter is dan 10, blijft het op zijn plaats.
5 8 10 20 30 2 9 7
Stap # 4 - Element 30 wordt vergeleken met 20, en aangezien het groter is dan 20, zullen er geen wijzigingen worden aangebracht en blijft de array ongewijzigd. Nu zou de array zijn
5 8 10 20 30 2 9 7
Stap # 5 - Element 2 wordt vergeleken met 30, omdat het kleiner is dan 30, wordt het één positie vooruit verschoven en vervolgens wordt het vergeleken met 20, 10, 8, 5, één voor één en worden alle elementen naar 1 positie vooruit verschoven en 2 wordt vóór 5 ingevoegd.
De resulterende array is:
2 5 8 10 20 30 9 7
Stap # 6 - Element 9 wordt vergeleken met 30 omdat het kleiner is dan 30, het wordt één voor één vergeleken met 20, 10 en het element wordt 1 positie vooruit geschoven en 9 wordt vóór 10 en na 8 ingevoegd. De resulterende array is:
2 5 8 9 10 20 30 7
Stap # 7 - Element 7 wordt vergeleken met 30, en aangezien het kleiner is dan 30, wordt het vergeleken met 30, 20, 10, 9, 8 en worden alle elementen één positie één voor één verschoven en wordt 7 vóór 8 ingevoegd De resulterende array zou worden:
2 5 7 8 9 10 20 30
Op deze manier worden alle elementen van de array gesorteerd met behulp van de invoegsortering die de vergelijking met het voorgaande element begint.
Voorbeelden om invoegsortering in Java te implementeren
Insertion Sort in Java is een eenvoudig sorteeralgoritme dat geschikt is voor alle kleine gegevenssets.
public class InsertionSort (
public static void insertionSort(int arr()) ( for (int j = 1; j < arr.length; j++) ( int key = arr(j); int i = j-1;
while ( (i > -1) && ( arr(i) > key ) ) ( arr(i+1) = arr(i); i--; )
arr(i+1) = key;
)
)
static void printArray(int arr()) ( int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i System.out.print(arr(i) + " " );
System.out.println();
)
public static void main(String args())( int() arr1 = (21, 18, 15, 23, 52, 12, 61);
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
)
)public class InsertionSort (
public static void insertionSort(int arr()) ( for (int j = 1; j < arr.length; j++) ( int key = arr(j); int i = j-1;
while ( (i > -1) && ( arr(i) > key ) ) ( arr(i+1) = arr(i); i--; )
arr(i+1) = key;
)
)
static void printArray(int arr()) ( int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i System.out.print(arr(i) + " " );
System.out.println();
)
public static void main(String args())( int() arr1 = (21, 18, 15, 23, 52, 12, 61);
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
)
)
Output:
12 15 18 21 23 52 61
Uitleg:
In het bovenstaande programma van Insertion Sort wordt de functie insertionSort () gebruikt om de elementen van de oorspronkelijke array te sorteren. Het sorteren begint bij het tweede element, aangezien het eerste element op zichzelf als gesorteerd beschouwt. De lus van 'j' begint dus bij index 1 van de array. 'i' is de variabele die de index bijhoudt net voor de 'j' om de waarde te vergelijken. ' key 'is de variabele met de waarde van het huidige element dat in gesorteerde positie moet worden gerangschikt. terwijl () lus wordt uitgevoerd als de huidige waarde kleiner is dan de meest linkse waarde, zodat het verschuiven van elementen kan worden verwerkt en aan het eind het invoegen van het huidige element op de juiste positie kan worden uitgevoerd. De functie printArray () wordt gebruikt om de gesorteerde array eindelijk af te drukken.
1. Beste geval
In het invoegtype zou het beste zijn als alle elementen van de array al zijn gesorteerd. Dus wanneer een element wordt vergeleken met het meest linkse element, is het altijd groter en daarom worden geen verschuivingen en invoegingen van elementen verwerkt. In dit geval zou de complexiteit van het beste geval lineair zijn, dat wil zeggen O (n).
2. Slechtste geval
In de bovenstaande code voor het invoegen is het slechtste geval wanneer de array in omgekeerde volgorde is, dus elke keer wanneer het element wordt vergeleken met het meest linkse element, is het altijd kleiner en vervolgens vergeleken met alle lopende elementen die plaatsvinden en verschuiven en het invoegen is voltooid. In dit geval is de complexiteit van de invoegsoort O (n 2).
3. Gemiddeld geval
Zelfs in een gemiddeld geval heeft de invoegsoort O (n 2) complexiteit waarbij sommige elementen niet hoeven te worden verschoven, terwijl sommige elementen van hun positie worden verschoven en invoeging op de juiste positie wordt uitgevoerd.
4. Beste gebruik
Invoegsortering is het beste te gebruiken wanneer de grootte van een array niet erg groot is of slechts een klein aantal elementen moet worden gesorteerd waarin bijna alle elementen worden gesorteerd en slechts enkele wijzigingen moeten worden aangebracht. Invoegsortering is een van de snelste algoritmen voor een array met kleine afmetingen, nog sneller dan de Quick Sort. Quicksort maakt zelfs gebruik van de functie Invoegen bij het sorteren van de kleine delen van de array.
Conclusie
De bovenstaande uitleg toont duidelijk de werking en de implementatie van Insertion Sort in Java. Ook in andere programmeertalen blijft de logica om de invoegsortering uit te voeren hetzelfde, alleen de syntaxis verandert. Voordat u een sorteeralgoritme implementeert, is het erg belangrijk om een analyse te maken van het scenario waarin moet worden gesorteerd, omdat niet elk sorteeralgoritme in alle scenario's past.
Aanbevolen artikelen
Dit is een gids voor Insertion Sort in Java. Hier bespreken we hoe Invoegsortering in Java werkt met Voorbeelden om Invoegsortering in Java te implementeren. U kunt ook de volgende artikelen bekijken voor meer informatie -
- Vierkantswortel in Java
- BorderLayout in Java
- Omgekeerd nummer in Java
- StringBuffer in Java
- Vierkantswortel in PHP
- Vierkantswortel in JavaScript
- Guide to Top 6 Sorteeralgoritmen in Python