null
US
Iniciar Sesión
Regístrate Gratis
Registro
Hemos detectado que no tienes habilitado Javascript en tu navegador. La naturaleza dinámica de nuestro sitio requiere que Javascript esté habilitado para un funcionamiento adecuado. Por favor lee nuestros
términos y condiciones
para más información.
Siguiente
Copiar y Editar
¡Debes iniciar sesión para completar esta acción!
Regístrate gratis
20163280
Sortieralgorithmen
Descripción
(Datenstrukturen) Informatik Mapa Mental sobre Sortieralgorithmen, creado por David Bratschke el 13/11/2019.
Sin etiquetas
datenstrukturen (ke 4)
informatik
datenstrukturen
Mapa Mental por
David Bratschke
, actualizado hace más de 1 año
Más
Menos
Creado por
David Bratschke
hace más de 4 años
36
1
0
Resumen del Recurso
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?
Recursos multimedia adjuntos
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)
Mostrar resumen completo
Ocultar resumen completo
¿Quieres crear tus propios
Mapas Mentales
gratis
con GoConqr?
Más información
.
Similar
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
Explorar la Librería