SelectionSort Sortieren durch Auswählen
(SelectionSort)

Prinzip: Tausche das Minimum mit dem aktuellen Element der Reihung!

Algorithmus Beispiel
Das aktuelle Element ist das erste Element der zu sortierenden Reihung.
1 8 4 0 4 7
Wiederhole bis zum vorletzten Element der Reihung:
  1. Suche beginnend mit dem aktuellen Element das Minimum in der Reihung.
  2. Tausche das Minimum mit dem aktuellen Element.
  3. Erhöhe die Platznummer des aktuellen Elementes um eins.
0 8 4 1 4 7

0 1 4 8 4 7

0 1 4 8 4 7

0 1 4 4 8 7

0 1 4 4 7 8

fertig!

SelectionSort hat eine quadratische Zeitabhängigkeit (bester, mittlerer und schlechtester Fall).

Quelltext (Auszug):

/**
      Sortiert eine Reihung
 */

   public void sort()

   { 

      for (int i = 0; i < a.length - 1; i++)

      { 

         int minPos = minimumPosition(i);

         swap(minPos, i);

      }

   }



   /**
      Sucht das Minimum in der Reihung.
   */

   private int minimumPosition(int from)

   { 

      int minPos = from;

      for (int i = from + 1; i < a.length; i++)

         if (a[i] < a[minPos]) minPos = i;

      return minPos;

   }



   /**
      Tauscht zwei Elemente.
   */

   private void swap(int i, int j)

   {

      int temp = a[i];

      a[i] = a[j];

      a[j] = temp;

   }


Quelltexte im Zip-Format zum herunter laden

Aufgaben:
  1. Wieviele Vergleiche und wieviele Tauschoperationen sind bei der Sortierung der folgenden Reihung mit SelectionSort notwendig?
    1. [ 4, 3, 2, 1 ]
    2. [ 5, 4, 3, 2, 1 ]
    3. [ 1, 2, 3, 4, 5 ]
  2. Stellen Sie die Methoden sort und minimumPosition in je einem Struktogramm dar!
  3. Untersuchen Sie das Zeitverhalten des Algorithmus experimentell!
  4. Begründen Sie das Zeitverhalten des Verfahrens!