Selectionsort: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
 
(3 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 5: Zeile 5:
[[Kategorie:Sortierverfahren]]
[[Kategorie:Sortierverfahren]]
<font color='red'>'''Diese Seite entspricht dem Abi 17 (und folgenden)'''</font>
<font color='red'>'''Diese Seite entspricht dem Abi 17 (und folgenden)'''</font>
=Erklärvideos=
* [https://youtu.be/oiMPMjXpVD8 Selectionsort Prinzip und Algorithmus]
* [https://youtu.be/dMbm0ZTyfmI Selectionsort Implementierung für Arrays]


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


Zeile 34: Zeile 39:
=Implementierung=
=Implementierung=
==für Listen==
==für Listen==
<code>
<code>
   '''private List<Person> sortiereDurchAuswaehlen(List<Person> pList){ '''
   '''private List<Person> sortiereDurchAuswaehlen(List<Person> pList){ '''
     List<Person> ergebnis = new List<>();  
     List<Person> ergebnis = new List<>();  
     while(pList.isEmpty() == false){  
     while(pList.isEmpty() == false){  
       Person p = gibUndEntferneAlphabetischErste(pList);  
       Person p = gibAlphabetischErste(pList);
      loeschen(p, pList);
       ergebnis.append(p);  
       ergebnis.append(p);  
     }  
     }  
Zeile 44: Zeile 50:
   }
   }
   
   
   '''private Person gibUndEntferneAlphabetischErste(List<Person> pList){ '''
   '''private Person gibAlphabetischErste(List<Person> pList){ '''
     pList.toFirst();  
     pList.toFirst();  
     Person ergebnis = pList.getContent();  
     Person ergebnis = pList.getContent();  
Zeile 54: Zeile 60:
       pList.next();  
       pList.next();  
     }  
     }  
     // jetzt ergebnis aus pList loeschen!
     return ergebnis;
  }
 
  '''private void loeschen(Person pPerson, List<Person> pList){'''
     pList.toFirst();  
     pList.toFirst();  
     while(pList.hasAccess()){  
     while(pList.hasAccess()){  
       Person p = pList.getContent();  
       Person p = pList.getContent();  
       if(p == ergebnis){  
       if(p == pPerson){  
           pList.remove();  
           pList.remove();  
           break;  
           return;  
       }  
       }  
       pList.next();  
       pList.next();  
     }  
     }  
    return ergebnis;
  }
  }
   
  </code>
</code>


==für Arrays==
==für Arrays==
Hier wird die Variante B implementiert.
Hier wird die Variante B implementiert.


<code>
<code>
     '''public int[] selectionsort(int[] pZahlen){'''
     '''public int[] selectionsort(int[] pZahlen){'''
         int[] ergebnis = new int[pZahlen.length];
         int[] ergebnis = new int[pZahlen.length];
Zeile 85: Zeile 92:
         return ergebnis;
         return ergebnis;
     }
     }
 
     '''private int indexDerKleinstenZahl(int[] zahlen) {'''
     '''private int indexDerKleinstenZahl(int[] zahlen) {'''
         // kleinste wird auf die groesste moegliche Int-Zahl gesetzt
         // kleinste wird auf die groesste moegliche Int-Zahl gesetzt
Zeile 99: Zeile 105:
         return indexKleinste;
         return indexKleinste;
     }   
     }   
 
</code>
</code>

Aktuelle Version vom 21. November 2022, 21:07 Uhr

Diese Seite entspricht dem Abi 17 (und folgenden)

Erklärvideos

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(n2), 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 = gibAlphabetischErste(pList); 
      loeschen(p, pList);
      ergebnis.append(p); 
   } 
   return ergebnis;
 }

 private Person gibAlphabetischErste(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(); 
   } 
   return ergebnis;
 }
 
 private void loeschen(Person pPerson, List<Person> pList){
   pList.toFirst(); 
   while(pList.hasAccess()){ 
      Person p = pList.getContent(); 
      if(p == pPerson){ 
         pList.remove(); 
         return; 
      } 
      pList.next(); 
   } 
}

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