Materialien zum Unterricht

• Startseite
• Informatiksystem
  Grundlagen Analog und Digital Darstellung von Zahlen Binär rechnen Digitale Buchstaben Digitale Bilder Digitale Farben
• Codierung
  Grundlagen Station 1 : Caesar-Verschlüsselung Station 2 : Codierungsscheiben Station 3 : Freimaurer-Code Station 4 : Geheimschrift von Polybius Station 5 : Raster-Codierung Station 6 : Stab-Codierung
• Daten & Informationen
  Daten-Infos Datenschutz Cookies 1 Cookies 2 Einstieg Fake News Quellenbewertung Fakebilder Fakevideos
• Netzwerke
• Algorithmen
  Eigenschaften Aufbau Darstellungen KOAM-Modell Komplexität
• mBlock
  Einrichtung 1. Programm Quadrate n-Ecke Zahlenschloss
• Python
  Datentypen Operatoren Methoden Problemlöseprozess Grundlagen print() input() Selektion Zyklen break,pass,continue

Sortieralgorithmen

Grundlagen

Sortieralgorithmen sind wichtig, da sie die Effizienz und Leistung vieler Anwendungen und Systeme verbessern. Sie ermöglichen eine schnellere Datenabfrage, optimieren Datenbankoperationen, organisieren Prozesse in Betriebssystemen und dienen als Grundlage für die Analyse anderer Algorithmen.

Grundbegriffe

Begriff	Beschreibung	Beispiel
Sortieren	Prozess des Anordnens einer Menge von Elementen in einer bestimmten Reihenfolge.	Karten sortieren nach aufsteigender Reihenfolge und Farbe.
Elemente	Die zu sortierenden Datenobjekte.	Zahlenkarten
Vergleichsoperator	Ein Operator, der zwei Elemente vergleicht und angibt, ob sie in der gewünschten Reihenfolge stehen.	Zahlenkarte_1 < Zahlkarte_2
Stabilität	Ein Sortieralgorithmus ist stabil, wenn die relative Reihenfolge der Elemente mit gleichem Schlüssel erhalten bleibt.	Wenn eine Liste alphabetisch sortierter Personendateien nach dem Geburtsdatum neu sortiert wird, dann bleiben alle Personen mit gleichem Geburtsdatum alphabetisch sortiert.
In-place-Sortierung	Ein Algorithmus, der keine zusätzlichen Speicherplatz benötigt und die Sortierung direkt in der Eingabesequenz durchführt.	Karten in der Hand sortieren.

Anwendungsbereiche

• Datenbanken:
  Effiziente Speicherung, Abfrage und Analyse von Daten.
• Betriebssysteme:
  Organisation von Prozessen, Dateien und Ressourcen.
• Algorithmusanalyse:
  Grundlage für die Analyse und Bewertung von Algorithmen.
• Datenverarbeitung und -analyse:
  Verarbeitung in verschiedenen Bereichen wie Text- und Bildverarbeitung.

Klassifizierung

Man unterscheidet Sortieralgorithmen in vergleichsbasierte und nicht-vergleichbasierte Sortieralgorihtm

Vergleichsbasierte Sortieralgorithmen vergleichen die Elemente paarweise miteinander und tauschen sie entsprechend der gewünschten Reihenfolge um.

Beispiele:
Bubble Sort, Insertion Sort, Selection Sort, Merge Sort und Quick Sort

Nicht-vergleichsbasierte Sortieralgorithmen sortieren die Elemente ohne direkte Paarvergleiche, sondern basierend auf anderen Eigenschaften der Elemente.

Beispiele:
Counting Sort, Radix Sort und Bucket Sort

Komplexität von Algorithmen

Die Effizienz der Sortieralgorithmen ist in den meisten Fällen vom Ausgangszustand der Datenmenge abhängig.

Die verschiedenen Algorithmen können unterschiedlich effizient beim Sortieren der Datenmengen sein.

Welches Sortierverfahren im Endeffekt als "bester Sortieralgorithmus" bezeichnet werden kann, muss immer individuell und situativ entschieden werden.

Mehr zur Komplexität erfährst du unter:

Vergleichsbasierte Sortieralgorithmen

Auf der Webseite informatik.cc werden 5 Sortieralgorithmen vorgestellt.

Geh auf die Seite informatik.cc und teste die Verschiedenen Sortieralgorithmen aus.

Selection Sort

Beim Selection Sort Unterteilt man seine Liste in 2 Bereiche: sortiert (links) und unsortiert (rechts).
Der sortierte Bereich ist zu Beginn leer.

Ablauf:

1. Man sucht im rechten, unsortierten Teil der Liste nach dem kleinsten Element.
   Dazu merkt man sich das erste Element der unsortierten Liste und vergleicht dieses mit den folgenden Elementen
   Sollte ein kleineres Element gefunden werden, wird dieses gemerkt und damit weiter verglichen.
2. Das kleinste Element der unsortierten Liste wird nun an die 1. Stelle der unsortierten Liste gesetzt.
3. Die Grenze zwischen dem sortierten und dem unsortiertem Array wird um 1 nach rechts verschoben.
   Dadurch wächst die sortierte Liste, während die unsortierte Liste kürzer wird.

Aufgabe 1:

Programm-Name:"selectionsort.py" .

Setze den Selection Sort in Python um.

Weitere Sortierverfahren

Aufgabe 2: Steckbriefe erstellen

Sortierverfahren:

• Selectionsort
• Insertion Sort
• Quicksort
• Bubblesort
• Mergesort

Material:

• informatik.cc
• Sortieralgorithmen Reif

Aufgabe 3:

Wähle einen der folgenden Algorithmen aus und setze ihn in Python um.

Sortierverfahren:

• Insertion Sort
• Quicksort
• Bubblesort
• Mergesort

Zurück