Direkt zum Inhalt
  1. Startort
  2. Quests
  3. 📖
Level 2
Level 2 setzt Schulmathematik voraus. Geeignet für Schüler.

Aufgabe mit Lösung Mergesort-Algorithmus

Führe Mergesort-Algorithmus mit dem folgenden Array durch und gib dabei nach jedem Schritt die Teilarrays an:

[14, 33, 12, 45, 42, 51, 89, 63, 80, 35]

Lösungstipps
  • Array in der Mitte aufteilen
  • Teilarrays in der richtigen Reihenfolge zusammenfügen

Lösung

Lösung zu (a) anzeigen

Als erstes wird das Array in der Mitte aufteilt:

[14, 33, 12, 45, 42] [51, 89, 63, 80, 35]

Die beien Teilarrays werden jeweils in der Mitte aufgeteilt. Da die Anzahl der Elemente in beiden Arrays ungerade ist, wird die Aufteilung abgerundet (5/2 ~ 2):

[14, 33, 12, 45, 42] [51, 89, 63, 80, 35]
[14, 33][12, 45, 42][51, 89][63, 80, 35]

Die vier entstandenen Teilarrays werden analog aufgeteilt:

[14, 33, 12, 45, 42] [51, 89, 63, 80, 35]
[14, 33][12, 45, 42][51, 89][63, 80, 35]
[14][33][12][45, 42][51][89][63][80, 35]

Die Arrays, die noch nicht einelementig sind, werden weiter aufgeteilt:

[14, 33, 12, 45, 42] [51, 89, 63, 80, 35]
[14, 33][12, 45, 42][51, 89][63, 80, 35]
[14][33][12][45, 42][51][89][63][80, 35]
[14][33][12][45][42][51][89][63][80][35]

Anschließend müssen die einelementigen Arrays in der richtigen Reihenfolge (von klein nach groß) zusammengefügt werden. Zuerst werden die zuletzt aufgespaltenen Arrays wieder zusammengefügt:

[14, 33, 12, 45, 42] [51, 89, 63, 80, 35]
[14, 33][12, 45, 42][51, 89][63, 80, 35]
[14][33][12][45, 42][51][89][63][80, 35]
[14][33][12][42, 45][51][89][63][35, 80]
[14, 33][12, 42, 45][51, 89][35, 63, 80]
[12, 14, 33, 42, 45][35, 51, 63, 80, 89]
[12, 14, 33, 35, 42, 45, 51, 63, 80, 89]

Details zum Inhalt
  • Die Quest wurde hinzugefügt von FufaeV am .
  • Die Quest wurde aktualisiert von FufaeV am .