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;
        }
    }    

Eine Klasse ArrayTools

Natürlich gibt es für den Umgang mit Arrays die sehr umfangreiche Klasse Arrays mit vielen Methoden zum Kopieren, Sortieren, Suchen etc. Später können Sie diese Methoden auch gerne in ihren Projekten einsetzen, aber im ersten und zweiten Semester sollte man lernen, wie man selbst solche Methoden schreiben kann.

Beginnen wir mit der Basis-Version der Klasse. Es soll ein Array beliebiger Länge erzeugt werden können, dann soll der Array ganz oder teilweise mit Zufallszahlen gefüllt werden können, und schließlich soll der Array ganz oder teilweise angezeigt werden können.

Hier ein Screenshot der ersten Version der Bluej-Klasse ArrayTools:

Die erste Version der Klasse ArrayTools
Hier können Sie den Quelltext herunterladen

Methode erzeugeArray()

Die Methode erzeugeArray(int laenge) erzeugt ein neues int-Array mit der angegebenen Länge und gibt dieses Array zurück. Sie dient dazu, ein Array in einer gewünschten Größe anzulegen, das später mit Zahlen gefüllt und weiterverarbeitet werden kann. Ist die übergebene Länge ungültig (z. B. ≤ 0), liefert die Methode in den Zeilen 11/12 ein leeres Array zurück, damit das Programm nicht mit einer Ausnahme abbricht. In Zeile 14 wird das erzeugte aber noch leere Array als Wert zurückgegeben.

Methode fuelleArrayMitZufallszahlen()

Die Methode fuelleArrayMitZufallszahlen(int[] array, int anzahl, int min, int max) füllt die ersten anzahl Elemente eines vorhandenen int-Arrays mit Zufallszahlen. Die erzeugten Werte liegen im Bereich von min bis max (jeweils einschließlich). Dabei wird nur so viele Werte eingetragen, wie sowohl im Array Platz ist als auch durch anzahl vorgegeben werden. Auf diese Weise lassen sich beliebige Arrays schnell mit Testdaten versehen.

Was bedeutet static?

Die Methode ist mit dem Schlüsselwort static versehen. Das bedeutet, dass sie zur Klasse ArrayTools gehört und nicht zu einem einzelnen Objekt dieser Klasse. Man muss also kein Objekt erzeugen, um die Methode aufzurufen, sondern kann sie direkt über den Klassennamen verwenden, zum Beispiel:

ArrayTools.fuelleArrayMitZufallszahlen(zahlen, 50, 1, 100);

Dies ist typisch für sogenannte Utility-Klassen, die eine Sammlung nützlicher Funktionen bereitstellen, ohne eigenen Zustand zu besitzen. Auch die Klasse Math ist eine solche Utility-Klasse, deren Methoden man aufrufen kann, ohne dass man vorher ein Objekt der Klasse erzeugen muss.

Methode zeigeArray()

Die Methode zeigeArray(int[] array, int anzahl) gibt die ersten anzahl Elemente eines int-Arrays formatiert in der Konsole aus. Dabei werden pro Zeile genau zehn Werte dargestellt, um eine übersichtliche, tabellarische Struktur zu erzeugen. Ist die angegebene Anzahl größer als die tatsächliche Arraylänge, werden nur so viele Elemente ausgegeben, wie im Array vorhanden sind.

Einbau der Sortieralgorithmen in ArrayTools

Wir wollen nun eine Bubblesort-Methode in die Klasse ArrayTools einbauen. Das geht so:

   public static void bubblesort(int[] array)
    {
        if (array == null || array.length < 2)
            return;

        int n = array.length;

        for (int durchgang = 0; durchgang < n - 1; durchgang++)
        {
            for (int i = 0; i < n - 1 - durchgang; i++)
            {
                if (array[i] > array[i + 1])
                {
                    tausche(array, i, i + 1);
                }
            }
        }
    } 

Die Methode tausche() ist eine private statische Methode, die Sie selbst noch in die Klasse einfügen müssen.

Weitere Übungen zur Klasse ArrayTools

Die Klasse ArrayTools soll um weitere Methoden erweitert werden, die man beim Umgang mit int-Arrays immer wieder gebrauchen kann. Einige dieser Übungen haben Sie bereits in der Folge 4 kennen gelernt.

public static void delete(int[] array, int index)

public static void insert(int[] array, int index, int value)

Jetzt noch ein paar leichtere Übungen

public static boolean enthaeltWert(int[] array, int value)

public static int enthaeltWertWieOft(int[] array, int value)