faecher:informatik:oberstufe:algorithmen:sorting:lernweg:start []

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.
~~NOTOC~~

====== Lernweg Datenbanken ======

<callout>
<image shape="thumbnail">
{{ path.png |}}
</image>
Verwendung: Du kannst die Informationen zu den Lernwegabschnitten in dein Notizprogramm übernehmen oder ausdrucken und in dein Heft kleben, so dass nach jedem Schritt Raum zur Selbstreflexion und für eigene Notizen bleibt. 
</callout>

==== 1: Sortieren und Aufwandsbeurteilung ====

Sortieralgorithmen sind relativ aufwändig - an dieser Stelle kann man sich also auch damit beschäftigen, wie man den Aufwand eines Algorithmus beurteilt und vergleicht. Zum Einstieg betrachten wir die [[https://info-bw.de/faecher:informatik:oberstufe:algorithmen:binaere_suche:start|binäre Suche]], sie es ermöglicht auf sortierten Daten effizient bestimmte Elemente zu finden.

Anschließend betrachten wir die eine [[https://info-bw.de/faecher:informatik:oberstufe:algorithmen:big_o:start|vereinfachte Variante der sogenannten "O-Notation"]], mit der man den Aufwand eines Algorithmus klassifizieren kann.  

==== 2: Sortierverfahren ====

Java bietet mit dem Comparable Innterface eine Möglichkeit, auch eigene Datentypen (Klassen) sortierbar zu machen. Um die Problemstellung "Sortieren" einzuordnen, schauen wir uns das hier an:  [[..problemstellung:start|Warum sortieren - das Comparable Interface]].

Jetzt können wir in die Sortierverfahren einsteigen, zunächst betrachten (und implementieren) wir verschiedene sogenannte vergleichsbasierte Sortierverfahren:

  * [[..bubblesort:start|Bubble Sort]]
  * [[..selectionsort:start|Selection Sort]]
  * [[..insertionsort:start|Insertion Sort]]
  * [[..mergesort:start|Mergesort]]
  * [[..quicksort:start|Quicksort]]

Mergesort und Quicksort sind rekursive Verfahren, die das [[https://info-bw.de/faecher:informatik:oberstufe:algorithmen:rekursion:teile_und_herrsche:start|"Teile und herrsche Prinzip"]], das du bereits aus der Rekursion kennst, verwenden.

Von BEdeutung ist die Aufwandsbeurteilung der Sortieralgorithmen und eine Eigenschaft, die man [[faecher:informatik:oberstufe:algorithmen:sorting:insertionsort:start?s[]=stabil#a3|"stabil"]] nennt, die manche Sortieralgorithmen haben - und andere nicht. 

==== 3: Ergänzung: Nicht vergleichsbasierte Sortierverfahren ====

Unter besonderen Rahmenbedingungen kann man Sortierverfahren finden, die nicht vergleichsbasiert funktionieren, z.B. [[..:radixsort:start|Radixsort]].