¶ Sortierverfahren
Sortierverfahren lösen das Sortierproblem. Wer hätte das gedacht 
. Sortierung ist häufig die Voraussetzung für andere Verfahren wie zum Beispiel Suchalgorithmen.
Sortierproblem
Menge von Elementen (z. B. Zahlen, Wörter) soll nach einer bestimmten Reihenfolge sortiert werden soll.
Voraussetzung: Liste, Vergleichsoperation
¶ Übersicht gängiger Verfahren
Für das Sortierproblem existieren u.a. folgende Algorithmen
| Algorithmus | Beschreibung |
|---|---|
| Bubble Sort | Vergleicht benachbarte Elemente und vertauscht sie, bis alles sortiert ist. Link |
| Selection Sort | Wählt das kleinste Element und setzt es an die richtige Position. Link |
| Insertion Sort | Fügt jedes Element an der richtigen Stelle in die sortierte Teilliste ein. Link |
| Merge Sort | Teilt die Liste rekursiv, sortiert Teilstücke und fügt sie wieder zusammen. Link |
| Quick Sort | Wählt ein Pivot-Element, teilt in kleinere/größere Teile und sortiert rekursiv. Link |
Folgendes Video zeigt 15 Verfahren nacheinander.
Folgendes Video zeigt 9 Verfahren parallel.
¶ Effizienz von Sortieralgorithmen
Die Effizienz kann experimentell gemessen oder systematisch untersucht werden.
Siehe Komplexitaet
Quelle: https://kmcompsci.weebly.com/big-o-notation.html
¶ Code aller Sortierverfahren aus Experiment
Hinweis: Ihr müsst kein ganzes Verfahren implementieren können, solltet aer am Code grob den Ablauf nachvollziehen können
import random
def selection_sort(liste):
m = 0
for links in range(0, len(liste)):
m = links
for k in range(links, len(liste)):
if liste[k] < liste[m]:
m = k
liste[m], liste[links] = liste[links], liste[m]
return liste
# Bubble Sort
def bubble_sort(liste):
tausch = True
i = 0
while tausch:
tausch = False
for j in range(len(liste) - 1 - i):
if liste[j] > liste[j + 1]:
liste[j], liste[j + 1] = liste[j + 1], liste[j]
tausch = True
i += 1
return liste
# Insertion Sort
def insertion_sort(liste):
for index in range(1, len(liste)):
c = liste[index]
position = index
while position > 0 and liste[position - 1] > c:
liste[position] = liste[position - 1]
position = position - 1
liste[position] = c
return liste
# Quick Sort
def quick_sort(liste):
if not liste:
return []
pivot = liste[0] # Erstes Element ist Pivot-Element
# pivot = liste[random.randint(0, len(l)-1)] # Zufälliges Element ist Pivot-Element
# Divide and Conquer
smaller = [x for x in liste[1:] if x < pivot]
greater = [x for x in liste[1:] if x >= pivot]
try:
return quick_sort(smaller) + [pivot] + quick_sort(greater)
except RecursionError:
return []