Direkt zum Inhalt
  1. Startseite
  2. Quests
  3. #338

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 .

Feedback geben

Hey! Ich bin Alexander FufaeV, der Physiker und Autor hier. Es ist mir wichtig, dass du stets sehr zufrieden bist, wenn du hierher kommst, um deine Fragen und Probleme zu klären. Da ich aber keine Glaskugel besitze, bin ich auf dein Feedback angewiesen. So kann ich Fehler beseitigen und diesen Inhalt verbessern, damit auch andere Besucher von deinem Feedback profitieren können.

Wie zufrieden bist Du?