SortieralgorithmenIntermediate

Shell Sort

Eine Optimierung von Insertion Sort, die den Austausch von weit entfernten Elementen erlaubt. Verwendet eine Luckensequenz, die auf 1 abnimmt, wodurch der Algorithmus Elemente schneller naher an ihre endgultigen Positionen bewegen kann. Benannt nach Donald Shell, der ihn 1959 erfand.

#sorting#gap-sequence#insertion-sort-variant#in-place

Complexity Analysis

Time (Average)

O(n^1.25)

Expected case performance

Space

O(1)

Memory requirements

Time (Best)

O(n log n)

Best case performance

Time (Worst)

O(n²)

Worst case performance

Input Array

Presets

Custom Array (comma-separated)

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