Bitte beachten Sie, dass es hierbei sich um einen von meiner alten Seite migrierten Artikel handelt.

Einleitung

Im Folgenden werden wir die Implementierung den Algorithmus des SelectionSort in Java erläutern. Der Algorithmus selbst wurde bereits in der Veranstaltung "Algorithmen und Datenstrukturen" im Wintersemester 2010/2011 behandelt. Hier wird deshalb nur auf den Quellcode der Implementierung sowie auf Messwerte bei der Sortierung von Objekten mit diesem Quellcode eingegangen.

Implementierung in Java

Da die Ausführungsdauer der Sortierung anhand unterschiedlicher Datensätze gemessen wurde und eine Abfrage der Typen, sowie die Ausgabe jedes Sortierschrittes das Ergebnis der Messung verfälscht hätte, haben wir uns entschlossen, nicht auf generische Klassen zurückzugreifen. Unsere Klassen sind speziell für die Datentypen Student_MatNr und Student_Voll angepasst und müssen möglicherweise für eine Implementierung in einem anderen System abgeändert werden.

Die Definition der Klasse:

public class SelectionSort
{
    // Methoden werden noch aufgeführt
}

Da unsere Methoden statisch sind - d. h. von überall aus ohne vorher initialisiert worden zu sein, aufgerufen werden können - nutzen wir keinen Konstruktor. Dieser ist gültig für die Sortierung beider Datentypen.

Sortierung - Student_MatNr[] SelectionSort:

public static Student_MatNr[] SelectionSort(Student_MatNr[] array)
{
    int min;

    for(int i = 0; i < array.length - 1; i++)
    {
       min = i;
       for(int j = i + 1; j < array.length; j++)
           if(array[j].getMatNr() < array[min].getMatNr())
               min = j;

        array = Swap(array, i, min);
     }
    return array;
}

Die Funktion sortiert einen Array vom Typ Student_MatNr nach dem SelectionSort-Verfahren: Man suche in der Eingabesequenz A das kleinste Element m und setze es vorne vor die sortierte Restsequenz.

Methode Student_MatNr[] Swap:

private static Student_MatNr[] Swap(Student_MatNr[] array, int idx1, int idx2)
{
    Student_MatNr tmp = array[idx1];
    array[idx1] = array[idx2];
    array[idx2] = tmp;

    return array;
}

Die Methode Swap ist für das Tauschen zweier Elemente in einem Array zuständig. Der erste Parameter ist der Array, der Zweite und der Dritte geben die Stellen an, die getauscht werden sollen. Dabei wird eine neue temporäre Variable angelegt, die den alten Array Wert speichert. Anschließend wird einer der zu tauschenden Elemente in das andere überschrieben und die Variable in das andere Feld geschrieben.

Methode Student_Voll[] SelectionSort:

public static Student_Voll[] SelectionSort(Student_Voll[] array)
{
    int min;

    for(int i = 0; i < array.length - 1; i++)
    {
       min = i;
       for(int j = i + 1; j < array.length; j++)
           if(array[j].getMatNr() < array[min].getMatNr())
               min = j;

        array = Swap(array, i, min);
     }
    return array;
}

Methode Student_Voll[] Swap:

private static Student_Voll[] Swap(Student_Voll[] array, int idx1, int idx2)
{
    Student_Voll tmp = array[idx1];
    array[idx1] = array[idx2];
    array[idx2] = tmp;

    return array;
}

Ausführung des Codes

Die grünen Bereiche sind bereits sortiert und die gelben Zahlen werden vertauscht.

------ Original ------------------
38 39 12 36 88 15 06 61 IN OUT | Beginne bei Index 1: 06 <-> 38
----------------------------------
06 39 12 36 88 15 38 61 2 + 3 | Beginn ist nun Index 2: 12 <-> 39
06 12 39 36 88 15 38 61 1 + 3 | 15 <-> 39
06 12 15 36 88 39 38 61 2 + 3 | kein Tausch
06 12 15 36 88 39 38 61 0 + 3 | 38 <-> 88
06 12 15 36 38 39 88 61 2 + 3 | kein Tausch
06 12 15 36 38 39 88 61 0 + 3 | 61 <-> 88
06 12 15 36 38 39 61 88 1 + 3 | Liste ist fertig sortiert

Sortierung der Testdateien

Bewegungen:

Datei	Innere Bewegungen	Äußere Bewegungen	Bewegungen gesamt
studenten_mtNr_datei_50TN	133	147	280
studenten_mtNr_datei_1500TN	8.682	4.497	13.179
studenten_voll_datei_50TN	132	147	279
studenten_voll_datei_1500TN	8.756	4.497	13.253

Dauer:

Datei	Dauer Einlesen	Dauer Sortiervorgang
studenten_mtNr_datei_50TN	0,028310198	0,001531516
studenten_mtNr_datei_1500TN	0,087168954	0,02154983
studenten_voll_datei_50TN	0,031060155	0,00359258
studenten_voll_datei_1500TN	0,39625102	0,01929279

Die hier angegebenen Messwerte sind Durchschnittswerten von 3 Ausführungen. Um die Messwerte besser vergleichen zu können, wurde auf der virtuellen Maschine vom Typ DB1 sortiert.

Quellenangabe

Literatur:
- Datenstrukturen und Algorithmen von Bernd Breutmann (Arbeitsblatt)

Internet:
- http://www.stefan-baur.de/cs.algo.selectionsort.html
- http://leepoint.net/notes-java/data/arrays/31arrayselectionsort.html

Anhang: Gesamter Quellcode

Datentyp Student_MatNr:

public static Student_MatNr[] SelectionSort(Student_MatNr[] array)
{
    int min;

    for(int i = 0; i < array.length - 1; i++)
    {
       min = i;
       for(int j = i + 1; j < array.length; j++)
           if(array[j].getMatNr() < array[min].getMatNr())
               min = j;

        array = Swap(array, i, min);
     }
    return array;
}

private static Student_MatNr[] Swap(Student_MatNr[] array, int idx1, int idx2)
{
    Student_MatNr tmp = array[idx1];
    array[idx1] = array[idx2];
    array[idx2] = tmp;

    return array;
}

Datentyp Student_Voll:

public static Student_Voll[] SelectionSort(Student_Voll[] array)
{
    int min;

    for(int i = 0; i < array.length - 1; i++)
    {
       min = i;
       for(int j = i + 1; j < array.length; j++)
           if(array[j].getMatNr() < array[min].getMatNr())
               min = j;

        array = Swap(array, i, min);
     }
    return array;
}

private static Student_Voll[] Swap(Student_Voll[] array, int idx1, int idx2)
{
    Student_Voll tmp = array[idx1];
    array[idx1] = array[idx2];
    array[idx2] = tmp;

    return array;
}