Invoegsortering in Java

Het sorteren van arrays is een van de meest voorkomende bewerkingen die een Java-beginner moet weten. Hoewel arrays niet altijd de handigste manier zijn om gegevens te rangschikken en dit vooral van toepassing is op kleine aantallen, heeft het concept achter arraysortering tal van toepassingen in complexe software en datawetenschap. In dit bericht gaan we dieper in op wat invoegsortering is. We hebben enkele voorbeelden en oefenopgaven toegevoegd om u te helpen dit concept volledig onder de knie te krijgen.

Wat is invoegsortering?

Kortom, invoegsortering is een algoritme dat ontwikkelaars gebruiken om reeksen van kleine getallen te ordenen. Het verdeelt alle waarden in twee stapels - een gesorteerde en een ongesorteerde. Een voor een worden de nummers in de "ongesorteerde" stapel eruit gehaald en in de juiste volgorde gelegd. Laten we de invoer en uitvoer van invoegsortering eens nader bekijken:

• Invoer: een array A met ongesorteerde numerieke elementen: A[0,1, n, n-2...].
• Uitvoer: een array met dezelfde getallen maar volledig gesorteerd. Deze wordt typisch aangeduid als B: B[0]B[1]...B[n-1].

Er zijn een handvol manieren om invoegsortering te gebruiken - hier zijn de meest populaire:

• Numerieke sortering (oplopende volgorde): [1, 2, 3, 4, 5]
• Numerieke sortering (aflopende volgorde): [5, 4, 3, 2, 1]
• Alfabetische sortering: [a, b, c, d]

Opmerking: als u een lege array of een singleton heeft, worden deze standaard als gesorteerd beschouwd.

De theorie van invoegsortering begrijpen

Laten we, voordat we de code achter invoegsortering onderzoeken, het algoritme opsplitsen in niet-technische taal. Omdat we de code voor het sorteren in oplopende volgorde zullen laten zien, is het logisch om het algoritme in dit bericht stap voor stap uit te leggen. Stap 1. Itereren tussen arr[1]en arr[n]waar nis een numerieke waarde die doorgaans kleiner is dan 10. Stap 2. Vergelijk het gekozen element (bekend als de key) met het vorige nummer in de reeks met behulp van de sort()methode. Stap 3. Als alle elementen kleiner zijn dan hun opvolgers, herhaalt u de vergelijking totdat u een grotere waarde vindt. Stap 4. Verwissel een grotere waarde één positie verder dan de kleinere om een ​​geordende reeks te creëren. Stap 5. Herhaal het proces totdat u een gesorteerde reeks tekens krijgt

Primitieve arrays sorteren

Aangezien het algoritme een van de meest eenvoudige Java-bewerkingen is, zouden zelfs complete beginners er niet veel moeite mee moeten hebben om het te implementeren. Hier is een stapsgewijze handleiding voor het sorteren van een array

1. Declareer een array voor de sortering

Laten we om te beginnen een reeks waarden maken die we later met Java zullen weergeven. Om invoegsortering te gebruiken, moet u een array maken. Gebruik daarvoorint[]

int[] arrayA = {10, 14, 20, 30};

2. Gebruik sort_arr om het algoritme te implementeren

De methode sort_arr is een van de meest gebruikelijke manieren om invoegsortering te implementeren. In de praktijk ziet het er zo uit:

for(int i=0; i< sort_arr.length; ++i){
        int j = i;

3. Maak een lus en een iterator

Door een lus te gebruiken in het invoegsorteeralgoritme hoeven ontwikkelaars de logica niet voor elk element te herhalen. Hoewel het maken van loops complex lijkt, is het vrij eenvoudig - hier is een voorbeeld:

for(int i=0; i< sort_arr.length; ++i){

Nu je een werkende lus hebt, is het tijd om een ​​iterator te maken die alle elementen in de gewenste volgorde sorteert. Vanaf nu zullen we naar de iterator verwijzen als " j".

        int j = i;

4. Een "while-lus" maken

Als het gaat om invoegsortering, is een "while"-lus essentieel voor een nieuwe, gesorteerde array. Een ontwikkelaar moet aan twee voorwaarden voldoen om het in te stellen voor invoegsortering in oplopende volgorde:

• De aan j toegewezen waarde moet groter zijn dan 0
• De waarde die wordt toegewezen aan j-1moet groter zijn dan de jindex

Zodra beide voorwaarden in de while-lus waar zijn, is de sleutelwaarde van de array gelijk aan de jindex.

5. De reeks sorteren

Nadat u de while-lus hebt ingesteld, worden de waarden jen j-1verwisseld totdat een of beide voorwaarden in de while-lus mislukken. Op dezelfde manier wordt het sorteren herhaald voor elke waarde in de for-lus totdat ook de for-lusvoorwaarden mislukken. Hier is hoe het proces van invoegsortering in de praktijk werkt:

int key = sort_arr[j];
          sort_arr[j] = sort_arr[j-1];
          sort_arr[j-1] = key;
          j = j-1;

Een ArrayList sorteren

Hoewel het begrijpen van de wiskunde achter invoegsortering belangrijk is, zult u ArrayLists veel meer sorteren als het gaat om real-life softwareontwikkeling dan sequenties in primitieve arrays. Hier is een stapsgewijze handleiding voor het sorteren van een ArrayList:

1. Maak een nieuwe Elementklasse aan voor de items die bij de collectie horen.

   
   public class Element {
       private int id;
   
       public Element(int id) {
           this.id = id;
       }
   

2. Binnen een verzameling is er een compareTo()methode - we zullen deze gebruiken om de id's van twee elementen te vergelijken.

   
       public int compareTo(Element element) {
           int res = 0;
           if (this.id < element.getId()) {
               res = -1;
           }
           if (this.id > element.getId()) {
               res = 1;
           }
           return res;
       }
   }
   

3. Pas het algoritme toe en maak enkele lussen om de objecten te sorteren ArrayListin plaats van ze te vergelijken.

   
   public static void insertionSortArrayList(List<element> list) {
       for (int j = 1; j < list.size(); j++) {
           Element current = list.get(j);
           int i = j-1;
           while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
               list.set(i+1, list.get(i));
               i--;
           }
           list.set(i+1, current);
       }
   }
   

4. ArrayListU kunt ook meer elementen toevoegen , zoals hieronder weergegeven:

   
   List<element> list = new ArrayList<>();
   
   // Create elements w/ IDs 0-24
   for (int i = 0; i < 25; i++) {
       list.add(new Element(i));
   }
   
   // To use insertion sort, shuffle the values
   Collections.shuffle(list);
   

5. Nu is het tijd om te sorteren:

   
   // This helps print values before sorting
   list.forEach(e -> System.out.print(e.getId() + ", "));
   
   // Sort the list
   insertionSortArrayList(list);
   
   System.out.println();
   
   // Display a sorted array 
   list.forEach(e -> System.out.print(e.getId() + ", "));
   

6. Laten we nu de invoer en de uitvoer vergelijken om er zeker van te zijn dat we geen fouten hebben gemaakt. Hier is de vergelijking van de string die we als voorbeeld hebben gebruikt.

   
   4, 2, 6, 7, 0, 5, 9, 1, 8, 3,
   0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
   

Invoegsorteeroefeningen

Nu je dit sorteeralgoritme onder de knie hebt, is het tijd om je theoretische en praktische vaardigheden op de proef te stellen. Theoriequiz #1 Je krijgt een array [1, 4, 6, 8] en voegt er een nieuw element n = 7 aan toe. Hoeveel vergelijkingen moet u maken om een ​​gesorteerde reeks getallen te krijgen? Geef de uiteindelijke waarde van index n in de array aan. Theoriequiz #2 Bij een sollicitatiegesprek vraagt ​​een teamleider je om te bewijzen dat sorteerinvoeging een inefficiënte methode is. Gegeven een numerieke reeks van [0, 3, 6, 8, 9], wat moet de volgorde van uw invoerreeks zijn om de looptijd die nodig is voor het sorteren te maximaliseren? Oefenprobleem Sorteer de array [0, 1, 4, 5, 2, 3, 7, 9, 8] in oplopende volgorde met behulp van invoegsortering voor Java.

Conclusie

De grootste uitdaging bij het begrijpen van invoegsortering is begrijpen hoe het proces werkt. Als je het eenmaal onder de knie hebt, is het omzetten van de sjabloon in code een fluitje van een cent. Zolang je relevante oefenproblemen in de loop van de tijd oefent en opnieuw bekijkt, zul je snel je sorteersnelheid verbeteren.