Welcher der vier Algorithmen eignet sich am besten, um Daten zu sortieren, die Stück für Stück nacheinander, z. B. in einem Netzwerk, ankommen?
Ist die Folge nicht komplett bekannt und die Elemente kommen einzeln an, eignet sich einzig der
…. Algorithmus zur Sortierung.
Insertionsort
ist die einzige dieser Möglichkeiten, die ihre Operation mit unvollständigem Wissen durchführen kann.
Mergesort, Quicksort und Selectionsort müssen jeweils in der Lage sein, alle Elemente von Anfang an zu verschieben.
Ein Mergesort teilt eine Folge zunächst mehrmals in zwei Hälften auf, so dass er rekursiv mit kleineren Teilen arbeitet. Wann hört er auf, die Folge in Unterfolgen aufzuteilen (in seiner einfachsten Version)?
Wenn jede Teilliste ein Element enthält
Mergesort, in seiner einfachsten Version, zerlegt die Liste in immer kleinere Unterlisten, bis jede nur noch ein Element enthält.
Warum? Weil eine Liste, die ein Element enthält, sortiert ist!
(Falsche Antworten
Wenn jede Teilliste aus zwei Elementen besteht
Nach vier Teilungen
Es kommt nicht auf die Größe an, sondern darauf, wie man sie nutzt!
Einer der einfachsten Sortieralgorithmen heißt Bubble Sort. Wissen Sie, warum?
Größere (oder kleinere) Elemente "blubbern" nach oben wie eine Blase im Wasser
Falsche Antworten, die angegeben wurden
Das ist immer noch ein Rätsel. Warum heißt eigentlich etwas so, wie es heißt?
Jedes Element wird in eine "Blase" eingeschlossen, bevor es sortiert wird.
Der Entwickler hoffte, dass mehr Leute seine Sortierung benutzen würden, wenn sie einen netten Namen hätte
Bei Quicksort wird ein Pivot-Element gewählt und die Listenelemente werden verschoben. Hard-Split!
Jedes Element, das kleiner als der Pivot-Wert ist, befindet sich näher am Anfang der Liste als der Pivot-Wert, und jedes Element, das größer als der Pivot-Wert ist, befindet sich näher am Ende der
Liste.
Durch mehrmaliges, rekursives Aufteilen mit verschiedenen Pivot-Elementen wird die Liste sortiert.
Welches wäre der beste Pivot-Wert für die schnellste Operation?
Ein Wert in der Mitte der aktuellen Teilliste
Falsche Antwort:
Der kleinste Wert in der aktuellen Teilliste
Das spielt keine Rolle, es dauert in jedem Fall genauso lange.
Der größte Wert in der aktuellen Teilliste
Last changed9 months ago