Selection-sort: Unterschied zwischen den Versionen

(2 dazwischenliegende Versionen von einem anderen Benutzer werden nicht angezeigt)

Zeile 1:

== Einführung ==

Ein ~~simpler~~ Sortieralgorithmus ist der Selection Sort. Dieser Algorithmus sucht ~~sich als erstes~~ das kleinste Element in der Liste, merkt es sich und tauscht es ~~gegen das~~ Element am Anfang aus, sodass sich ~~dann~~ das kleinste Element ~~ganz am Anfang~~ befindet. ~~Als Nächstes~~ wird das zweitkleinste Element ~~in der Liste~~ gesucht und ~~wird gegen das~~ an zweiter Stelle ~~platzierte Element der Liste ausgetauscht~~ usw. Auf diese Weise ~~haben immer~~ die Elemente auf der linken Seite der aktuellen Position ~~einen~~ festen Platz und werden nicht mehr ~~geändert~~.

Ein einfacher [[Sortieren|Sortieralgorithmus]] ist der Selection Sort. Dieser Algorithmus sucht zunächst das kleinste Element in der Liste, merkt es sich und tauscht es mit dem Element am Anfang aus, sodass sich das kleinste Element an erster Stelle befindet. Anschließend wird das zweitkleinste Element gesucht und mit dem Element an zweiter Stelle vertauscht usw. Auf diese Weise erhalten die Elemente auf der linken Seite der aktuellen Position schrittweise ihren festen Platz und werden nicht mehr verändert.

== Beispiel ==

[[Datei:Array Selectionsort.gif|mini]]

Es soll eine Liste mit dem Inhalt [4|3|1|5|2] sortiert werden.

Im ersten Durchlauf wird die komplette Liste ~~durchlaufen~~, um das kleinste Element auszuwählen (Select) und an den Beginn der Liste zu stellen. In diesem Beispiel der Wert 1. Der ursprüngliche Wert der Startposition (hier 4) wird mit dem Wert der ~~Stelle~~ des kleinsten ~~Wertes~~ (hier ~~Wert~~ 1 im Index 2) ~~getauscht~~.

Im ersten Durchlauf wird die komplette Liste durchsucht, um das kleinste Element auszuwählen (Select) und an den Beginn der Liste zu stellen. In diesem Beispiel ist das der Wert 1. Der ursprüngliche Wert der Startposition (hier 4) wird mit dem Wert an der Position des kleinsten Elements (hier 1 an Index 2) vertauscht.

[[Datei:Animation Selectionsort.gif|mini]]

Im zweiten Durchlauf beginnt die Suche nach dem kleinsten Element nun im Index 1. Im Index 0 befindet sich bereits das kleinste Element, daher ist ~~eine~~ Suche ~~an der ersten Stelle nicht~~ mehr erforderlich. Der ~~Rest~~ der Liste wird ~~durchlaufen~~. Das kleinste Element befindet sich hier ~~zufällig~~ am Ende der Liste. Es wird die 2 als kleinstes Element ausgewählt und ~~die Werte werden~~ mit der neuen Startposition ~~getauscht~~.

Im zweiten Durchlauf beginnt die Suche nach dem kleinsten Element nun bei Index 1. An Index 0 befindet sich bereits das kleinste Element, daher ist dort keine Suche mehr erforderlich. Der restliche Teil der Liste wird durchsucht. Das kleinste Element befindet sich hier am Ende der Liste. Es wird die 2 als kleinstes Element ausgewählt und mit der neuen Startposition vertauscht.

Die Suche wiederholt sich nach ~~dieser Logik~~ bis alle Elemente sortiert ~~wurden~~. Der Suchbereich ~~sinkt~~ Schritt für Schritt. ~~Folgende~~ Animation visualisiert den Algorithmus.

Die Suche wiederholt sich nach diesem Prinzip, bis alle Elemente sortiert sind. Der Suchbereich verkleinert sich Schritt für Schritt. Die folgende Animation visualisiert den Algorithmus.

== ~~Pseudo Code~~ ==

== Pseudocode ==

Der Algorithmus sieht im Pseudocode so aus:

prozedur ~~SelectionSort~~( A : Liste sortierbarer Elemente)

~~hoechsterIndex~~ = ~~Elementanzahl(~~ A ~~) - 1~~

prozedur selectionSort(A ist Liste sortierbarer Elemente)

einfuegeIndex = 0

n = Länge von A

wiederhole

für einfuegeIndex von 0 bis n - 2 wiederhole

minPosition = einfuegeIndex

für ~~jeden~~ idx von (einfuegeIndex + 1) bis ~~hoechsterIndex~~ wiederhole

für idx von einfuegeIndex + 1 bis n - 1 wiederhole

falls A[ idx ] < A[ minPosition ] dann

falls A[idx] < A[minPosition] dann

minPosition = idx

ende falls

ende für

falls minPosition ≠ einfuegeIndex dann

vertausche A[minPosition] und A[einfuegeIndex]

ende falls

ende für

~~vertausche A[ minPosition ] und A[ einfuegeIndex ]~~

ende prozedur

~~einfuegeIndex~~ = ~~einfuegeIndex + 1~~

</syntaxhighlight>

~~solange einfuegeIndex~~ < ~~hoechsterIndex~~

~~prozedur ende~~

== Java-Implementierung ==

<~~/syntaxhighlight~~>

public ArrayList<Mitarbeiter> sortierenNachNachnamen() {

ArrayList<Mitarbeiter> sortierteListe = new ArrayList<>(mitarbeiterListe);

int stelle = 0;

~~== Java Implementierung ==~~

while (stelle < sortierteListe.size() - 1) {

~~<syntaxhighlight lang="java">~~

int kleinstesElement = stelle;

~~public ArrayList<Mitarbeiter> sortierenNachNachnamen(){~~

~~ArrayList<Mitarbeiter> sortierteListe = mitarbeiterListe;~~

~~int stelle = 0;~~

while(stelle < sortierteListe.size()){

int kleinstesElement = stelle;

~~for(int index = stelle+1; index < sortierteListe.size(); index++){~~

if(sortierteListe.get(index).getNachname().compareTo(sortierteListe.get(kleinstesElement).getNachname()) < 0){

for (int index = stelle + 1; index < sortierteListe.size(); index++) {

kleinstesElement = index;

if (sortierteListe.get(index).getNachname()

}

.compareTo(sortierteListe.get(kleinstesElement).getNachname()) < 0) {

kleinstesElement = index;

}

if (kleinstesElement != stelle) {

Mitarbeiter puffer = sortierteListe.get(kleinstesElement);

sortierteListe.set(kleinstesElement,sortierteListe.get(stelle)) ;

sortierteListe.set(kleinstesElement, sortierteListe.get(stelle));

sortierteListe.set(stelle,puffer);

sortierteListe.set(stelle, puffer);

~~stelle++~~;

}

return sortierteListe;

stelle++;

}

return sortierteListe;

}

</syntaxhighlight>

== Komplexität ==

Mit Hilfe der [[Laufzeitanalyse]] betrachten wir nun die Zeitkomplexität des [[Algorithmus]] SelectionSort.

Um eine Datenstruktur (z.B. ~~eine~~ [[Array]]) mit Einträgen mittels SelectionSort zu sortieren, muss n-1 mal das Minimum durch Vergleichen bestimmt werden. Bei der ersten Bestimmung des Minimums sind ~~n-1~~ Vergleiche notwendig, bei der zweiten ~~n-2~~ Vergleiche usw. Mit der [[Arithmetische-reihe|gaußschen Summenformel]] erhält man die ~~Anzahl~~ der notwendigen Vergleiche. SelectionSort liegt somit in der Komplexitätsklasse <math>O(n^2) </math>.

Um eine Datenstruktur (z. B. ein [[Array]]) mit n Einträgen mittels SelectionSort zu sortieren, muss n−1-mal das Minimum durch Vergleichen bestimmt werden. Bei der ersten Bestimmung des Minimums sind n−1 Vergleiche notwendig, bei der zweiten n−2 Vergleiche usw. Mit der [[Arithmetische-reihe|gaußschen Summenformel]] erhält man die Gesamtanzahl der notwendigen Vergleiche:

(n − 1) + (n − 2) + … + 1 = n(n − 1) / 2

SelectionSort liegt somit in der Komplexitätsklasse <math>O(n^2)</math>.

[[Kategorie:Programmierung]]

[[Kategorie:AHR_I_Informatik_LK]]

[[Kategorie:FI_I_TP2]]

@@ Zeile 1: / Zeile 1: @@
 == Einführung ==
-Ein simpler Sortieralgorithmus ist der Selection Sort. Dieser Algorithmus sucht sich als erstes das kleinste Element in der Liste, merkt es sich und tauscht es gegen das Element am Anfang aus, sodass sich dann das kleinste Element ganz am Anfang befindet. Als Nächstes wird das zweitkleinste Element in der Liste gesucht und wird gegen das an zweiter Stelle platzierte Element der Liste ausgetauscht usw. Auf diese Weise haben immer die Elemente auf der linken Seite der aktuellen Position einen festen Platz und werden nicht mehr geändert.
+Ein einfacher [[Sortieren|Sortieralgorithmus]] ist der Selection Sort. Dieser Algorithmus sucht zunächst das kleinste Element in der Liste, merkt es sich und tauscht es mit dem Element am Anfang aus, sodass sich das kleinste Element an erster Stelle befindet. Anschließend wird das zweitkleinste Element gesucht und mit dem Element an zweiter Stelle vertauscht usw. Auf diese Weise erhalten die Elemente auf der linken Seite der aktuellen Position schrittweise ihren festen Platz und werden nicht mehr verändert.
 == Beispiel ==
 [[Datei:Array Selectionsort.gif|mini]]
 Es soll eine Liste mit dem Inhalt [4|3|1|5|2] sortiert werden.
-Im ersten Durchlauf wird die komplette Liste durchlaufen, um das kleinste Element auszuwählen (Select) und an den Beginn der Liste zu stellen. In diesem Beispiel der Wert 1. Der ursprüngliche Wert der Startposition (hier 4) wird mit dem Wert der Stelle des kleinsten Wertes (hier Wert 1 im Index 2) getauscht.
+Im ersten Durchlauf wird die komplette Liste durchsucht, um das kleinste Element auszuwählen (Select) und an den Beginn der Liste zu stellen. In diesem Beispiel ist das der Wert 1. Der ursprüngliche Wert der Startposition (hier 4) wird mit dem Wert an der Position des kleinsten Elements (hier 1 an Index 2) vertauscht.
 [[Datei:Animation Selectionsort.gif|mini]]
-Im zweiten Durchlauf beginnt die Suche nach dem kleinsten Element nun im Index 1. Im Index 0 befindet sich bereits das kleinste Element, daher ist eine Suche an der ersten Stelle nicht mehr erforderlich.  Der Rest der Liste wird durchlaufen. Das kleinste Element befindet sich hier zufällig am Ende der Liste. Es wird die 2 als kleinstes Element ausgewählt und die Werte werden mit der neuen Startposition getauscht.
+Im zweiten Durchlauf beginnt die Suche nach dem kleinsten Element nun bei Index 1. An Index 0 befindet sich bereits das kleinste Element, daher ist dort keine Suche mehr erforderlich. Der restliche Teil der Liste wird durchsucht. Das kleinste Element befindet sich hier am Ende der Liste. Es wird die 2 als kleinstes Element ausgewählt und mit der neuen Startposition vertauscht.
-Die Suche wiederholt sich nach dieser Logik bis alle Elemente sortiert wurden. Der Suchbereich sinkt Schritt für Schritt. Folgende Animation visualisiert den Algorithmus.
+Die Suche wiederholt sich nach diesem Prinzip, bis alle Elemente sortiert sind. Der Suchbereich verkleinert sich Schritt für Schritt. Die folgende Animation visualisiert den Algorithmus.
-== Pseudo Code ==
+== Pseudocode ==
 Der Algorithmus sieht im Pseudocode so aus:
-<syntaxhighlight>
-prozedur SelectionSort( A : Liste sortierbarer Elemente)
+<syntaxhighlight lang="text">
-  hoechsterIndex = Elementanzahl( A ) - 1
+prozedur selectionSort(A ist Liste sortierbarer Elemente)
-  einfuegeIndex = 0
+    n = Länge von A
-  wiederhole
+    für einfuegeIndex von 0 bis n - 2 wiederhole
-    minPosition = einfuegeIndex
+        minPosition = einfuegeIndex
-    für jeden idx von (einfuegeIndex + 1) bis hoechsterIndex wiederhole
+        für idx von einfuegeIndex + 1 bis n - 1 wiederhole
-      falls A[ idx ] < A[ minPosition ] dann
+            falls A[idx] < A[minPosition] dann
-          minPosition = idx
+                minPosition = idx
-      ende falls
+            ende falls
+        ende für
+        falls minPosition ≠ einfuegeIndex dann
+            vertausche A[minPosition] und A[einfuegeIndex]
+        ende falls
      ende für
-    vertausche A[ minPosition ] und A[ einfuegeIndex ]
+ende prozedur
-    einfuegeIndex = einfuegeIndex + 1
+</syntaxhighlight>
-  solange einfuegeIndex < hoechsterIndex
-prozedur ende
+== Java-Implementierung ==
- </syntaxhighlight>
+<syntaxhighlight lang="java">
+public ArrayList<Mitarbeiter> sortierenNachNachnamen() {
+    ArrayList<Mitarbeiter> sortierteListe = new ArrayList<>(mitarbeiterListe);
+    int stelle = 0;
-== Java Implementierung ==
+    while (stelle < sortierteListe.size() - 1) {
- <syntaxhighlight lang="java">
+        int kleinstesElement = stelle;
-public ArrayList<Mitarbeiter> sortierenNachNachnamen(){
-        ArrayList<Mitarbeiter> sortierteListe = mitarbeiterListe;
-        int stelle = 0;
-        while(stelle < sortierteListe.size()){
-            int kleinstesElement = stelle;
-            for(int index = stelle+1; index < sortierteListe.size(); index++){
-if(sortierteListe.get(index).getNachname().compareTo(sortierteListe.get(kleinstesElement).getNachname()) < 0){
+        for (int index = stelle + 1; index < sortierteListe.size(); index++) {
-                    kleinstesElement = index;
+            if (sortierteListe.get(index).getNachname()
-              }
+                    .compareTo(sortierteListe.get(kleinstesElement).getNachname()) < 0) {
+                kleinstesElement = index;
              }
+        }
+        if (kleinstesElement != stelle) {
              Mitarbeiter puffer = sortierteListe.get(kleinstesElement);
-             sortierteListe.set(kleinstesElement,sortierteListe.get(stelle)) ;
+             sortierteListe.set(kleinstesElement, sortierteListe.get(stelle));
-             sortierteListe.set(stelle,puffer);
+             sortierteListe.set(stelle, puffer);
-            stelle++;
          }
-         return sortierteListe;
+         stelle++;
+    }
+    return sortierteListe;
 }
- </syntaxhighlight>
+</syntaxhighlight>
 == Komplexität ==
 Mit Hilfe der [[Laufzeitanalyse]] betrachten wir nun die Zeitkomplexität des [[Algorithmus]] SelectionSort.
-Um eine Datenstruktur  (z.B. eine [[Array]]) mit Einträgen mittels SelectionSort zu sortieren, muss n-1 mal das Minimum durch Vergleichen bestimmt werden. Bei der ersten Bestimmung des Minimums sind n-1 Vergleiche notwendig, bei der zweiten n-2 Vergleiche usw. Mit der [[Arithmetische-reihe|gaußschen Summenformel]] erhält man die Anzahl der notwendigen Vergleiche. SelectionSort liegt somit in der Komplexitätsklasse <math>O(n^2) </math>.
+Um eine Datenstruktur (z. B. ein [[Array]]) mit n Einträgen mittels SelectionSort zu sortieren, muss n−1-mal das Minimum durch Vergleichen bestimmt werden. Bei der ersten Bestimmung des Minimums sind n−1 Vergleiche notwendig, bei der zweiten n−2 Vergleiche usw. Mit der [[Arithmetische-reihe|gaußschen Summenformel]] erhält man die Gesamtanzahl der notwendigen Vergleiche:
+(n − 1) + (n − 2) + … + 1 = n(n − 1) / 2
+SelectionSort liegt somit in der Komplexitätsklasse <math>O(n^2)</math>.
+[[Kategorie:Programmierung]]
+[[Kategorie:AHR_I_Informatik_LK]]
+[[Kategorie:FI_I_TP2]]