Insertionsort

Diese Seite entspricht dem Abi 17 (und folgenden)

Fachbegriffe

Insertionsort, Liste, Array

Erläuterung des Verfahrens

Insertionsort -> Sortieren durch Einfügen (des ersten Elements des unsortierten Teils an die richtige Stelle des sortierten Teils)

Insertionsort auf Listen

Bei Insertionsort wird die Ergebnisliste nach und nach aufgebaut.

Dazu wird jeweils das erste Element aus der ursprünglichen Liste genommen und gelöscht. Dann wird die Ergebnisliste von vorne bis zu der Stelle durchlaufen, an der das Element eingefügt werden muss; da wird es dann eingefügt.

Insertionsort auf Arrays

Das Array wird von vorne nach hinten durchlaufen. In jedem Schritt wird das aktuell betrachtete Element so weit im bereits sortierten vorderen Teil des Arrays nach vorne geschoben, bis es an der richtigen Stelle steht. Danach wird der nächste Eintrag betrachtet. Auf diese Weise wächst der bereits sortierte vordere Teil des Arrays in jedem Schritt um eins, bis am Ende das ganze Array sortiert ist.

Das Verfahren läuft also in place, d.h. man braucht (anders als bei einfach verketteten Listen) keine Hilfsstruktur.

Laufzeit

O(n²), d.h. der Aufwand wächst quadratisch mit der Zahl der zu sortierenden Elemente.

Implementierung

Insertionsort auf Listen in Java

Hier als Beispiel das Sortieren einer Liste, die Personen enthält. Die Personen werden nach dem Alphabet des Namens sortiert.

  public List<Person> sortierenDurchEinfuegen(List<Person> pList){
       List<Person> ergebnis = new List<>();
       pList.toFirst();
       while(pList.hasAccess()){
           Person aktuell = pList.getContent();
           anRichtigerStelleEinfugen(ergebnis, aktuell);
           pList.next();
       }
       return ergebnis;
  }
   
  public void anRichtigerStelleEinfugen(List<Person> pList, Person pPerson){
       pList.toFirst();
       while(pList.hasAccess()){
           Person aktuell = pList.getContent();
           // pPerson mit der aktuellen person vergleichen
           if(pPerson.getName().compareTo(aktuell.getName()) < 0){
               pList.insert(pPerson);
               return;
           }
           pList.next();
       }
       // pPerson wurde noch nicht eingefuegt!
       pList.append(pPerson);
   }

Insertionsort auf Arrays in Java

Wir gehen davon aus, dass es ein Array mit dem Namen zahlenFeld gibt, das mit ganzen Zahlen befüllt ist.

  // Aeussere Methode, die das Sortieren durchführt.
  // Sie nutzt die Hilfsmethode verschiebeNachVorne(int pVonWoAus)
  public void insertionSort()
  {
     for(int i = 0; i < zahlenFeld.length; i++)
     {
        verschiebeNachVorne(i);
     }
  }

  // Hilfsmethode, die eine Zahl ab der Stelle pVonWoAus so weit nach vorne im Array tauscht, bis
  // sie an der richtigen Stelle steht.
  // Sie nutzt die Hilfsmethode vertauschen(int pIndex1, int pIndex2), die
  // zwei Arrayeinträge vertauscht.
  private void verschiebeNachVorne(int pVonWoAus)
  {
     for(int j = pVonWoAus; j > 0; j--)
     {
        if( zahlenFeld[j] < zahlenFeld[j-1] )
        {
           vertauschen(j,j-1);
        }
     }
  }

  // Die Hilfsmethode vertauscht die beiden Arrayeinträge mit den Indices pIndex1 und pIndex2
  private void vertauschen(int pIndex1, int pIndex2)
  {
     int hilf = zahlenFeld[pIndex1];
     zahlenFeld[pIndex1] = zahlenFeld[pIndex2];
     zahlenFeld[pIndex2] = hilf;
  }