SelectionSort

SelectionSort (von engl. selection - Auswahl), auch MinSort (von Minimum) genannt, ist ein naiver Sortieralgorithmus, der in-place, aber instabil arbeitet.

Prinzip

Um ein Array der Länge n zu sortieren, wird das Minimum gesucht.

Das Minimum wird dann mit dem ersten Element des Arrays vertauscht. Somit erhält man links ein sortiertes Teilarray der Länge 1 und rechts ein unsortiertes der Länge n-1.

Anschließend wird der Algorithmus auf das unsortierte Teilarray angewendet.

Beispiel

1 2 3 4 5 6
M D A Z G Q   Das Minimum ist A. Vertausche also das 1. und das 3.
^   ^         Element.
A|D M Z G Q   Das Minimum des rechten Teilarrays ist D. Da es bereits
  ^           an 2. Position ist, muss praktisch nicht getauscht werden.
A D|M Z G Q   Wir haben jetzt bereits ein sortiertes Teilarray der 
    ^   ^     Länge 2. Wir vertauschen nun M und das Minimum G.
A D G|Z M Q   Wir vertauschen Z und M.
      ^ ^
A D G M|Z Q   Wir vertauschen Z und Q.
        ^ ^
A D G M Q Z   Das Array ist jetzt fertig sortiert.

Implementation

/*
* SELECTION SORT
* hier implementiert zur Sortierung eines int-Arrays
*
* @param ein zu sortierendes int-Array
*/
public void selectionSort(int[] array){
  int min, temp;

  for(int i = 0; i<array.length - 1; i++){
    min = i;

    // Minimum finden
    for(int k = i+1; k<array.length; k++){
      if(array[k] < array[min]) {
        min = k;
      }
    }

    temp = array[i];
    array[i] = array[min];
    array[min] = temp;

  }

}

» drucken: pdf | html