[[algorithmen:algolektion02|Lektion 3 - Übungen]]


====== Lektion 4 - Sortieren ======

Sortierverfahren sind von großer Bedeutung für die Informatik, siehe auch 
http://de.wikipedia.org/wiki/Sortierverfahren

Vielen Sortierverfahren liegt das folgende Modell zugrunde => vgl. Abbildung:
  * zu Beginn liegt ein //**sortierter**// und ein //**unsortierter** Datenbereich// vor
  * beide Datenbereiche werden durch ein //**Grenzelement**// voneinander getrennt
  * anfangs besteht der sotrierte Haufen aus nur einem einzigen Element (hier die "7"), dem //**Grenzelement**//

{{:algorithmen:classicsort.jpg|}}

Das Grenzelement wird während des Sortiervorgangs von links nach rechts geschoben, bis das ganze Zahlenfeld durchlaufen ist


===== Tauschen von Elementen =====

{{:htmlcss:work_64.png|}}

Möchte man zwei Elemente miteinander vertauschen, so wird ein Algorithmus mit dem Ansatz

  feld[i] = feld[j];
  feld[j] = feld[i];

nicht zum gewünschten Ergebnis führen, warum?
Berichtige den Code.


===== Sortieren durch Auswahl (Selectionsort) =====
[[http://de.wikipedia.org/wiki/Selectionsort|Selectionsort]] bei Wikipedia

Beim Sortieren durch Auswahl wird das kleinste Element des unsortierten Bereichs gesucht, ausgewählt und schließlich mit dem Grenzelement vertauscht. Die Grenze wird anschließend um einen Schritt weitergeschoben, bis das Ende erreicht ist => vgl. Abbildung:

{{:algorithmen:eletausch.jpg|}}


----


Im nachstehenden Struktogramm wird eine variable Anzahl von Elementen sortiert. Die Variablen **//kleinstes//** und //**grenze**// beschreiben dabei die //Position// des kleinsten Elementes bzw. des Grenzelementes, und NICHT das Element selber. Vorteil ist, dass sich so der Algorithmus auf verschiedene Datentypen (Zeichen, Zahlen, Buchstaben) anwenden lässt.

{{:algorithmen:selectsort2.jpg|}}

[[http://www.cs.oswego.edu/~mohammad/classes/csc241/samples/sort/Sort2-E.html|Animation für einen Selectionsort]]

===== Aufgaben =====

{{:htmlcss:work_64.png|}}

  - Sortiere die Zahlen 7, 5, 3, 8, 4, 6, 1, 2, 9 auf einem Blatt Papier nach dem Auswahlverfahren.
  - Folge dem Struktogramm und programmiere einen code für diesen Sortieralgorithmus.
  - Gib den Mittelwert der Listenelemente aus.
  - Wie viele Elemente sind größer bzw. kleiner als der Mittelwert?


[[algorithmen:algolektionl1|Lösungsvorschlag]]

  
[[algorithmen:algolektion04|Lektion 5 - Pseudocode]]