Sortieren durch Einfügen (Insertionsort)

Verfahren

Das Sortieren durch Einfügen ist ein intuitives und elementare Verfahren:

Man teilt die zu sortierende Folge f mit N Elementen in eine bereits sortierte Teilfolge f[0] bis f[s-1] und in eine unsortierte Teilfolge f[s] bis f[n].
- Zu Beginn ist die sortierte Teilfolge leer.
- Der Beginn der unsortierten Folge f[s] wird die Sortiergrenze genannt.
Man setzt eine Sortiergrenze hinter der bereits durch Zufall sortierte Teilfolge f[1] bis f[s-1]
Vergleiche f[s] mit f[s-1] und vertausche die beiden Elemente falls f[s]<f[s-1]
- Führe weitere Vergleiche und absteigende Vertauschungen durch bis man ein f[s-j] gefunden hat für das gilt f[s-j-1]<f[s-j]
Erhöhe die Sortiergrenze von f[i] auf f[i+1] und wiederhole die Vergleichs- und Vertauschungsschritte wie im vorhergehenden Schritt beschrieben.
Die Folge ist sortiert wenn die Sortiergrenze das Ende des Folge erreicht hat.

Beispiel

	Gegeben sei eine Folge in einem Feld mit sieben Elementen. Die ersten drei Elemente sind bereits sortiert und die Sortiergrenze wird mit 4 belegt. Die unsortierte Folge beginnt auf dem Feldindex vier.
	Als erstes wird der Wert f[4]=20 mit f[3]=35 verglichen. Da f[4] größer als f[3] ist, werden die beiden Werte getauscht.
	Anschließend folgt der Vergleich von f[3]=20 mit f[2]=23. Der Wert von f[3] ist größer als f[2]. Die beiden Werte werden getauscht.
	Der Vergleich von f[2] mit f[1] zeigt, dass f[2] größer als f[1] ist. f[2]=20 hat also seine korrekte Position in der sortierten Teilfolge gefunden.
	Der aktuelle Durchlauf ist hiermit beendet. Die Sortiergrenze wird um eins erhöht und erhält den Wert 5.
	Die sortierte Teilfolge ist um eins größer geworden. Es wird wieder f[5]=17 mit f[4]=35 verglichen. Da f[5] größer als f[4] ist, werden die beiden Werte getauscht. Jeder Durchlauf endet, wenn der Wert nicht mehr getauscht werden muss. Der Algorithmus endet wenn die Sortiergrenze die gesamt Folge umfasst.

Aufwand

Das Sortieren durch Einfügen braucht im günstigsten Fall nur N-1 Vergleiche für eine bereits sortierte Folge. Im ungünstigsten Fall (fallend sortiert) ist aber ein quadratisches Aufwand nötig.

Das gleiche gilt für die Vertauschungen. Hier müssen im ungünstigsten Fall Vertauschungen in einer quadratischen Größenordnung durchgeführt werden.

Implementierung

Die Implementierung der Klasse InsertionSort.java ist bei Github zu finden.

Stefan Schneider Wed, 01/19/2011 - 22:39

13888 views

Insertionsort: Implementierung in Java

Die folgende Implementierung implementiert die abstrakte Klasse Sortierer die in den Beispielprogrammen zum Sortieren zu finden sind.

Implementierung: Klasse InsertionSort

package s2.sort;
/**
 *
 * @author sschneid
 * @version 2.0
 */
public class InsertionSort extends Sortierer {
    /**
     * Konstruktor: Akzeptiere ein Feld von int. Reiche
     * das Feld an die Oberklasse weiter.
     * Der Algorithmus ist nicht parallel (false Argument)
     * @param s
     */
    public InsertionSort(int[] s) {
        super(s,false);
    }
    /**
     * sortiert ein Feld im Bereich startIndex bis endeIndex
     * @param startIndex
     * @param endeIndex
     */
    public void sortieren(int startIndex, int endeIndex) {
        for (int sortierGrenze = startIndex;sortierGrenze < endeIndex;
                sortierGrenze++) {
            int probe = sortierGrenze + 1;
            int j = startIndex;
            while (istKleiner(j, probe)) {
                j++;
            }
            // Verschiebe alles nach rechts.
            // Tausche den Probenwert gegen den unteren Nachbarn
            // bis man bei der Position j angekommen ist
            for (int k = probe - 1; k >= j; k--) {
                tausche(k, k + 1);
            }
        }
    }
    /**
     * Liefert den Namen des Insertion Sorts
     * @return
     */
    public String algorithmus() {
        return "Sortieren durch Einfuegen";
    }
}

Stefan Schneider Thu, 02/10/2011 - 11:02

6387 views