null
US
Anmelden
kostenlos registrieren
Registrieren
Wir haben festgestellt, dass Javascript in deinem Browser nicht aktiviert ist. Aufgrund des dynamischen Charakters unserer Website muss Javascript allerdings entsprechend aktiviert sein. Bitte lese dir unsere
Geschäftsbedingungen
durch, um mehr Informationen zu erhalten.
Nächster
Kopieren und bearbeiten
Sie müssen sich anmelden, um diese Aktion abzuschließen!
Kostenlos registrieren
20163280
Sortieralgorithmen
Beschreibung
Informatik (Datenstrukturen) Mindmap am Sortieralgorithmen, erstellt von David Bratschke am 13/11/2019.
Keine Merkmale angegeben
datenstrukturen (ke 4)
informatik
datenstrukturen
Mindmap von
David Bratschke
, aktualisiert more than 1 year ago
Mehr
Weniger
Erstellt von
David Bratschke
vor mehr als 4 Jahre
36
1
0
Zusammenfassung der Ressource
Sortieralgorithmen
Einfache Verfahren
SelectionSort
intern/extern?
intern
Effizienz
O(n²)
in situ
ja
Methode
Auswahl
des jeweils kleinsten Elements
stabil?
Grundform Nein
InsertionSort
Methode
durch Einfügen
des jeweiligen Elements an der richtigen Stelle
intern/extern
intern
Effizienz
O(n²)
in situ?
ja
stabil?
ja
BubbleSort
Vertauschen
benachbarter Elemente
Divide and Conqr
MergeSort
Methode
Divide
Array mittig in zwei Hälften teilen
Conquer
rekursiver Aufruf von Merge-Sort
Merge
beide Teile (wie ein Reißverschluss) zusammenführen
aus beiden sortierten Teillisten vom Beginn an
immer das Element wählen, das kleiner ist
dieses dann an Ergebnisliste anhängen
Anfangszeiger dieser Teil-Liste eins weiter setzen
intern/extern
eher extern
Effizienz
worst
O (n log n)
avg
O (n log n)
in situ?
nein
stabil?
ja
Quicksort
Methode
Divide
Pivotelement "x" wählen
dann Array Aufteilen in
Teil < x
Teil >= x
Conquer
für jeden Teil wieder rekursiv Algorithmus anwenden
Merge
sortiere Teillisten concatenieren
intern / extern?
ja
Effizienz
worst-case
O(n²)
Avg-Case
O (n log n)
in situ?
Ja
stabil?
Nein
clever-Quicksort
Fachverteilen
Bucket-Sort
Methode
jedes Fach sortieren
z.B. mit Merge-Sort
danach Fächer konkatenieren
Partitionieren
Verteilen der Elemente auf n Fächer
Laufzeit
O(n), wenn gleichverteilt
in situ?
nein
intern/extern?
intern
stabil?
abhängig vom Sortierfahren der einzelnen Buckets
Radix-Sort
Methode
wiederholtes stellenweises Bucketsort
Für jede Stelle
Partitionierungsphase
Elemente auf Buckets verteilen
Sammelphase
Fächer der Reihe nach wieder einsammeln
MSD Radixsort
Bucketsort, bei dem jedes Bucket mit Bucketsort sortiert wird
Voraussetzungen
Elemente möglichst gleich verteilt
wenig Elemente mit gleichem Schlüssel
Allgemeines
Klassifizierungen
intern/extern ?
intern
kann komplett im Hauptspeicher gehalten werden
extern
nur Teile im Hauptspeicher gehalten
methodisch
Einfügen / Auswählen
Divide and Conquer
Fachverteilen
Effizienz / Laufzeit
quadratisch
O(n²)
linear
O(n)
gute Sortierverfahren
O(n log(n))
in situ (place)
direkt im Array möglich
oder nicht
Sortierverfahren stabil
wenn Werte mit gleichem Schlüssel
Position behalten
verfeinerte Verfahren
Auswählen
Heapsort
stabil?
Nein
Methode
Aufbau eines Heaps
nacheinander Wurzel entnehmen
danach Heap wieder herstellen
letztes Element kommt in Wurzel
reheap: bis zur richtigen Position einsickern lassen
Effizienz
O (n log n)
in situ?
möglich
mit Arrays
bottom-up Heapsort
Einfügen
Baumsortieren
stabil?
nein
Methode
Binären Suchbaum erstellen
danach In-Order-Durchlauf
leftChild, aktuelles Element, right Child
Effizienz
O(n log n)
in situ?
Medienanhänge
300px Merge Sort Algorithm Diagram.Svg (image/png)
Quick Sort (image/png)
200px Heap Array (image/jpeg)
Heapsort5 (image/png)
Heapsort6 (image/png)
Radix Sort (binary/octet-stream)
600px Bucket Sort (image/jpeg)
311px Bucket Sort 1.Svg (image/png)
311px Bucket Sort 2.Svg (image/png)
Partition (binary/octet-stream)
Zusammenfassung anzeigen
Zusammenfassung ausblenden
Möchten Sie
kostenlos
Ihre eigenen
Mindmaps
mit GoConqr erstellen?
Mehr erfahren
.
ähnlicher Inhalt
ein kleines Informatik Quiz
AntonS
Informatik
Tom Kühling
PHP Grundlagen
chrisi.0605
Wirtschaftsinformatik Teil 2
Sabrina Heckler
Informatik 1 - Einführung
Svenja
Codierung
Tom Kühling
Wirtschaftsinformatik Teil 1
Sabrina Heckler
Einführung in das Studium Informatik
Daniel Doe
Lernplan
Sandra K
Netzwerke
Ann-Kathrine Buchmakowsky
Datenstrukturen
Ann-Kathrine Buchmakowsky
Bibliothek durchsuchen