5.4 Der Insertionsort

Allgemeines

Der Insertionsort ("Sortieren durch direktes Einfügen") ist ein weiteres einfaches Sortierverfahren. Ähnlich wie beim Selectionsort besteht der zu sortierende Array aus zwei Teilen, dem bereits sortierten Teil und dem noch unsortierten Teil.

Beim Insertionsort wird das erste Arrayelement als bereits sortiert angesehen, der sortierte Teil besteht also aus einem Element, der unsortierte aus dem Rest des Arrays.

Nun wird die erste Zahl des unsortierten Teils genommen (nicht gesucht!) und an der richtigen Position in den bereits sortierten Teil eingefügt. Danach besteht der sortierte Teil aus zwei Zahlen und der unsortierte Teil ist um ein Element geschrumpft.

Im zweiten Durchgang wird das Gleiche gemacht: Nimm die erste Zahl des unsortierten Teils und füge an der richtigen Stelle in den sortierten Teil ein. Danach wächst dieser um 1 und der unsortierte Teil schrumpft um 1.

Das Ganze wird solange wiederholt, bis der gesamte Array sortiert ist.

Im Grunde ist der Insertionsort das Sortierverfahren, das man auch bei vielen Kartenspielen benutzt. Man nimmt zunächst alle Karten in die Hand und breitet sie fächerartig aus. Dann sortiert man die Karten, indem man die jeweils nächste Karte an die richtige Stelle im bereits sortierten Teil steckt.

Übungen

  public void insertionSort()
    {
        for (int i = 1; i < numbers.length; i++)
        {
            int value = numbers[i];
            int pos = i;

            while (pos > 0 && numbers[pos - 1] > value)
            {
                numbers[pos] = numbers[pos - 1];
                pos--;
            }

            numbers[pos] = value;
        }
    }