SortieralgorithmenAdvanced

Bucket Sort

Ein verteilungsbasierter Sortieralgorithmus, der Elemente in eine Anzahl von Eimern verteilt. Jeder Eimer wird dann einzeln mit einem anderen Sortieralgorithmus sortiert. Funktioniert am besten, wenn die Eingabe gleichmassig uber einen Bereich verteilt ist. Durchschnittliche Zeitkomplexitat ist O(n+k).

#sorting#distribution-sort#linear-time#non-comparison

Complexity Analysis

Time (Average)

O(n + k)

Expected case performance

Space

O(n + k)

Memory requirements

Time (Best)

O(n + k)

Best case performance

Time (Worst)

O(n²)

Worst case performance

📚 CLRS Reference

Introduction to Algorithms•Chapter 8•Section 8.4

Input Array

Presets

Custom Array (comma-separated, non-negative integers)

Implementation

Related Algorithms

View all in Sortieralgorithmen

Bubble Sort

Beginner

Der grundlegendste Sortieralgorithmus, der wiederholt benachbarte Elemente vergleicht und sie austauscht, wenn sie in falscher Reihenfolge sind. Wie Blasen, die an die Oberflache steigen, bewegen sich grossere Werte allmahlich zum Ende des Arrays. Am besten geeignet fur kleine Datensatze oder Bildungszwecke, um Sortiergrundlagen zu verstehen.

Selection Sort

Beginner

Findet wiederholt das kleinste Element und verschiebt es nach vorne. Jede Iteration 'wahlt' das Minimum aus den verbleibenden Elementen und platziert es nach dem sortierten Teil. Einfach zu implementieren mit minimalem Speicherverbrauch, benotigt aber immer O(n^2) Zeit unabhangig von der Eingabe.

Quick Sort

Intermediate

Ein hocheffizienter Sortieralgorithmus, der ein Pivot-Element auswahlt und das Array mit kleineren Werten links und grosseren rechts partitioniert. Durchschnittlich O(n log n) und die am weitesten verbreitete Sortiermethode in der Praxis. Bildet die Grundlage der eingebauten Sortierfunktionen in den meisten Programmiersprachen.

O(n log n)

O(log n)

sortingdivide-and-conquer

Start Learning

Back to Sortieralgorithmen