Informatik Präsentationsleistung

Bubble Sort

Der klassische Bubble Sort ist wie ein geduldiger Lehrer, der immer wieder durch die Liste geht und benachbarte Elemente vertauscht, wenn sie in der falschen Reihenfolge stehen. Obwohl er langsam ist, ist er einfach zu verstehen und zu implementieren.

Shaker Sort

Shaker Sort ist die clevere Weiterentwicklung von Bubble Sort. Er arbeitet bidirektional - erst von links nach rechts, dann von rechts nach links. Diese Hin- und Her-Bewegung macht ihn effizienter als seinen einfacheren Verwandten.

Insertion Sort

Insertion Sort arbeitet wie ein Kartenspieler, der seine Karten sortiert. Er nimmt jedes Element und fügt es an der richtigen Stelle in den bereits sortierten Teil ein. Besonders effizient bei kleinen oder fast sortierten Listen.

Selection Sort

Selection Sort ist der methodische Perfektionist. Er sucht systematisch das kleinste Element und platziert es an der ersten Position, dann das zweitkleinste an die zweite Position und so weiter. Konstante Leistung, aber nicht die schnellste.

Merge Sort

Merge Sort folgt dem "Teile und Herrsche"-Prinzip. Er teilt die Liste rekursiv in kleinere Teile auf, sortiert diese und fügt sie dann geschickt wieder zusammen. Garantiert O(n log n) Leistung in allen Fällen.

Quick Sort

Quick Sort ist der Sprinter unter den Sortieralgorithmen. Er wählt ein Pivot-Element und partitioniert die Liste um dieses Element herum. Im Durchschnitt sehr schnell, aber im schlimmsten Fall kann er langsamer werden.

Live-Visualisierung

Editierbarer Code

Leistungsvergleiche

Bubble Sort

Der klassische Sortieralgorithmus

Zeitkomplexität

Bester Fall: O(n)

Durchschnitt: O(n²)

Schlechtester Fall: O(n²)

Speicherplatz: O(1)

Verwendung

Lernzwecke und Algorithmus-Verständnis
Sehr kleine Datensätze (< 10 Elemente)
Situationen wo Einfachheit wichtiger als Effizienz ist
Erkennung ob Liste bereits sortiert ist

Funktionsweise

Vergleiche benachbarte Elemente von links nach rechts

Vertausche sie, wenn das linke Element größer ist

Das größte Element "blubbert" nach rechts

Wiederhole für die verbleibenden Elemente

Python Implementation

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

# Test the algorithm
test_array = [64, 34, 25, 12, 22, 11, 90]
print("Original:", test_array)
sorted_array = bubble_sort(test_array.copy())
print("Sortiert:", sorted_array)

Output:

Klicken Sie auf "Code ausführen" um das Ergebnis zu sehen...

Live Visualisierung

Vergleiche: 0 Vertauschungen: 0

Shaker Sort

Bidirektionale Bubble Sort Variante

Zeitkomplexität

Bester Fall: O(n)

Durchschnitt: O(n²)

Schlechtester Fall: O(n²)

Speicherplatz: O(1)

Verwendung

Verbesserung gegenüber Standard Bubble Sort
Listen mit Elementen an beiden Enden unsortiert
Kleine Datensätze mit bidirektionaler Unordnung
Lehrbeispiel für Algorithmus-Optimierung

Funktionsweise

Durchlaufe die Liste von links nach rechts

Dann durchlaufe sie von rechts nach links

Große Elemente wandern nach rechts, kleine nach links

Wiederhole bis keine Vertauschungen mehr nötig

Python Implementation

def shaker_sort(arr):
    n = len(arr)
    left = 0
    right = n - 1
    
    while left < right:
        # Von links nach rechts
        for i in range(left, right):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
        right -= 1
        
        # Von rechts nach links
        for i in range(right, left, -1):
            if arr[i] < arr[i - 1]:
                arr[i], arr[i - 1] = arr[i - 1], arr[i]
        left += 1
    
    return arr

# Test the algorithm
test_array = [64, 34, 25, 12, 22, 11, 90]
print("Original:", test_array)
sorted_array = shaker_sort(test_array.copy())
print("Sortiert:", sorted_array)

Output:

Klicken Sie auf "Code ausführen" um das Ergebnis zu sehen...

Live Visualisierung

Vergleiche: 0 Vertauschungen: 0

Insertion Sort

Einfügen in sortierte Sequenz

Zeitkomplexität

Bester Fall: O(n)

Durchschnitt: O(n²)

Schlechtester Fall: O(n²)

Speicherplatz: O(1)

Verwendung

Kleine Datensätze (< 50 Elemente)
Fast sortierte Listen
Online-Algorithmus (sortiert während Eingabe)
Hybrid-Algorithmen als Basis

Funktionsweise

Beginne mit dem zweiten Element

Vergleiche es mit Elementen links davon

Verschiebe größere Elemente nach rechts

Füge das Element an der richtigen Position ein

Python Implementation

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        
        # Verschiebe Elemente die größer als key sind
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        # Füge key an der richtigen Position ein
        arr[j + 1] = key
    
    return arr

# Test the algorithm
test_array = [64, 34, 25, 12, 22, 11, 90]
print("Original:", test_array)
sorted_array = insertion_sort(test_array.copy())
print("Sortiert:", sorted_array)

Output:

Klicken Sie auf "Code ausführen" um das Ergebnis zu sehen...

Live Visualisierung

Vergleiche: 0 Vertauschungen: 0

Selection Sort

Auswahl des Minimums

Zeitkomplexität

Bester Fall: O(n²)

Durchschnitt: O(n²)

Schlechtester Fall: O(n²)

Speicherplatz: O(1)

Verwendung

Minimale Anzahl von Vertauschungen gewünscht
Speicher ist sehr begrenzt
Einfache Implementierung erforderlich
Kleine Datensätze mit konstanter Leistung

Funktionsweise

Finde das kleinste Element im unsortierten Teil

Vertausche es mit dem ersten unsortierten Element

Erweitere den sortierten Bereich um eine Position

Wiederhole bis alle Elemente sortiert sind

Python Implementation

def selection_sort(arr):
    n = len(arr)
    
    for i in range(n):
        # Finde das Minimum im unsortierten Teil
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        # Vertausche das gefundene Minimum mit dem ersten Element
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr

# Test the algorithm
test_array = [64, 34, 25, 12, 22, 11, 90]
print("Original:", test_array)
sorted_array = selection_sort(test_array.copy())
print("Sortiert:", sorted_array)

Output:

Klicken Sie auf "Code ausführen" um das Ergebnis zu sehen...

Live Visualisierung

Vergleiche: 0 Vertauschungen: 0

Merge Sort

Teile und Herrsche Prinzip

Zeitkomplexität

Bester Fall: O(n log n)

Durchschnitt: O(n log n)

Schlechtester Fall: O(n log n)

Speicherplatz: O(n)

Verwendung

Große Datensätze mit garantierter Leistung
Stabile Sortierung erforderlich
Externe Sortierung (Dateien)
Parallelisierung möglich

Funktionsweise

Teile die Liste rekursiv in zwei Hälften

Sortiere jede Hälfte rekursiv

Füge die sortierten Hälften zusammen

Wiederhole bis die gesamte Liste sortiert ist

Python Implementation

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    # Teile die Liste in zwei Hälften
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    # Füge die sortierten Hälften zusammen
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Test the algorithm
test_array = [64, 34, 25, 12, 22, 11, 90]
print("Original:", test_array)
sorted_array = merge_sort(test_array.copy())
print("Sortiert:", sorted_array)

Output:

Klicken Sie auf "Code ausführen" um das Ergebnis zu sehen...

Live Visualisierung

Vergleiche: 0 Vertauschungen: 0

Quick Sort

Pivot-basierte Partitionierung

Zeitkomplexität

Bester Fall: O(n log n)

Durchschnitt: O(n log n)

Schlechtester Fall: O(n²)

Speicherplatz: O(log n)

Verwendung

Allgemeine Sortierung (Standard in vielen Bibliotheken)
In-Place Sortierung gewünscht
Durchschnittlich sehr schnelle Leistung
Cache-effiziente Implementierung

Funktionsweise

Wähle ein Pivot-Element aus der Liste

Partitioniere die Liste um das Pivot

Sortiere die Teilbereiche rekursiv

Kombiniere die Ergebnisse

Python Implementation

def quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    
    if low < high:
        # Partitioniere und erhalte Pivot-Index
        pi = partition(arr, low, high)
        
        # Sortiere Elemente vor und nach der Partition
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)
    
    return arr

def partition(arr, low, high):
    pivot = arr[high]  # Letztes Element als Pivot
    i = low - 1
    
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# Test the algorithm
test_array = [64, 34, 25, 12, 22, 11, 90]
print("Original:", test_array)
sorted_array = quick_sort(test_array.copy())
print("Sortiert:", sorted_array)

Output:

Klicken Sie auf "Code ausführen" um das Ergebnis zu sehen...

Live Visualisierung

Übersicht der letzten 50 Vergleichstests mit detaillierten Leistungsmetriken

Gesamt: 0 Tests Heute: 0 Tests

Datum/Zeit	Vergleich	Algorithmus 1	Vergleiche 1	Vertauschungen 1	Algorithmus 2	Vergleiche 2	Vertauschungen 2	Gewinner
Noch keine Tests durchgeführt. Starten Sie einen Vergleich, um Daten zu sammeln.

Seite 1 von 1

Adaptive Hybrid Sort

Ein theoretischer Algorithmus für große, teilweise sortierte Listen mit vielen gleichen Werten und begrenztem Speicherplatz

Problemstellung

Riesige Liste mit Millionen von Elementen
Liste ist teilweise bereits sortiert
Viele gleiche Werte (hohe Redundanz)
Stark begrenzter Speicherplatz verfügbar
Stabilität der Sortierung erforderlich

Adaptive Hybrid Sort - Lösungsansatz

Analyse-Phase

Durchlaufe die Liste einmal und analysiere: Sortierungsgrad, Häufigkeit der Werte, und identifiziere bereits sortierte Bereiche (Runs).

Adaptive Strategie-Auswahl

Basierend auf der Analyse: Nutze Insertion Sort für kleine Runs, Tim Sort für teilsortierte Bereiche, und Counting Sort für Bereiche mit vielen Duplikaten.

Speicher-optimierte Verarbeitung

Verarbeite die Liste in Blöcken, die in den verfügbaren Speicher passen. Nutze externe Sortierung mit minimalen Merge-Operationen.

Intelligente Duplikat-Behandlung

Komprimiere gleiche Werte temporär zu (Wert, Anzahl)-Paaren, sortiere diese effizient und expandiere sie wieder.

Finale Merge-Phase

Führe die sortierten Blöcke mit einem k-way Merge zusammen, wobei ein Heap für die Merge-Reihenfolge verwendet wird.

Komplexitätsanalyse

Zeitkomplexität

O(n) bis O(n log n) je nach Eingabeeigenschaften. Bei stark vorsortierten Daten oder vielen Duplikaten nähert sich die Laufzeit O(n) an.

Speicherkomplexität

O(√n) für die Blockverarbeitung plus O(k) für den k-way Merge, wobei k die Anzahl der Blöcke ist. Konstant bezogen auf die Eingabegröße.

Stabilität

Vollständig stabil durch sorgfältige Implementierung aller Teilalgorithmen und der Merge-Operationen.

Adaptivität

Hochgradig adaptiv - passt sich automatisch an die Eigenschaften der Eingabedaten an und wählt die optimale Strategie.

Praktische Anwendungen

Big Data Processing

Sortierung großer Datensätze in verteilten Systemen mit begrenztem Arbeitsspeicher pro Knoten.

Datenbank-Systeme

Externe Sortierung für Index-Erstellung und Query-Optimierung bei großen Tabellen.

Embedded Systems

Sortierung in speicherbeschränkten Umgebungen wie IoT-Geräten oder Mikrocontrollern.

Log-File Analysis

Sortierung großer Log-Dateien mit vielen zeitlich geordneten Einträgen und wiederkehrenden Mustern.