Selectionsort

Diese Seite entspricht dem Abi 17 (und folgenden)

Fachbegriffe

Sortieren durch Auswählen (=Selectionsort), Array, Liste

Verfahren

Selectionsort -> Sortieren durch Auswählen (des jeweils kleinsten Elements aus dem unsortierten Teil)

Selectionsort auf Listen

Bei SelectionSort wird in einer gegebenen Liste das kleinste Element gesucht, gelöscht und an die Ergebnisliste angehangen.

Das wird so oft wiederholt, bis die ursprüngliche Liste leer ist.

Selectionsort auf Arrays

Variante A: Sortieren innerhalb eines Arrays:
Bei Selectionsort wird vorne im Array begonnen und das kleinste Element im Array gesucht. Dieses wird dann mit dem ersten Element im Array vertauscht. In jedem weiteren Schritt wird dann aus dem hinteren, unsortierten Teil des Arrays das kleinste Element gesucht und mit dem ersten Element (am weitesten Links) des unsortierten Teils vertauscht. Dadurch wächst der vordere, sortierte Teil des Arrays in jedem Schritt um eins.

Variante B: Erzeugen eines neuen sortierten Arrays:

• Es wird ein Ergebnis-Array gleicher Länge erzeugt.
• dann wiederholt man n-mal:
  • im ursprünglichen Array wird das kleinste Element gesucht und durch eine SEHR große Zahl ersetzt (auf jeden Fall größer als alle Elemente des Arrays).
  • das kleinste Element wird in das Ergebnis-Array geschrieben.

Laufzeit

O(n²), d.h. der Aufwand wächst quadratisch mit der Zahl der zu sortierenden Elemente.

Implementierung

für Listen

 private List<Person> sortiereDurchAuswaehlen(List<Person> pList){ 
   List<Person> ergebnis = new List<>(); 
   while(pList.isEmpty() == false){ 
      Person p = gibUndEntferneAlphabetischErste(pList); 
      ergebnis.append(p); 
   } 
   return ergebnis;
 }

 private Person gibUndEntferneAlphabetischErste(List<Person> pList){ 
   pList.toFirst(); 
   Person ergebnis = pList.getContent(); 
   while (pList.hasAccess()){ 
      Person p = pList.getContent(); 
      if(p.getName().compareTo(ergebnis.getName())<0){ 
         ergebnis = p; 
      } 
      pList.next(); 
   } 
   // jetzt ergebnis aus pList loeschen!
   pList.toFirst(); 
   while(pList.hasAccess()){ 
      Person p = pList.getContent(); 
      if(p == ergebnis){ 
         pList.remove(); 
         break; 
      } 
      pList.next(); 
   } 
   return ergebnis; 
}

für Arrays

Hier wird die Variante B implementiert.

   public int[] selectionsort(int[] pZahlen){
       int[] ergebnis = new int[pZahlen.length];
       for (int i = 0; i < pZahlen.length; i++) {
           int indexKleinsteZahl = indexDerKleinstenZahl(pZahlen);
           int dieKleinsteZahl = pZahlen[indexKleinsteZahl];
           ergebnis[i] = dieKleinsteZahl;
           // damit dieselbe Zahl nicht nochmal "gefunden" wird
           // wird sie durch die hoechste Integerzahl ersetzt.
           pZahlen[indexKleinsteZahl] = Integer.MAX_VALUE;
       }
       return ergebnis;
   }


   private int indexDerKleinstenZahl(int[] zahlen) {
       // kleinste wird auf die groesste moegliche Int-Zahl gesetzt
       int kleinste = Integer.MAX_VALUE;
       int indexKleinste = -1;
       for (int i = 0; i < zahlen.length; i++) {
           if(zahlen[i] < kleinste){
               kleinste = zahlen[i];
               indexKleinste = i;
           }
       }
       return indexKleinste;
   }