Mergesort (merge sort) in C und C++
In dieser Lektion implementierst du Mergesort nach dem Prinzip Teile und herrsche, das immer O(n log n) Zeit braucht.
Einführung
Mergesort teilt das Array in zwei Hälften, sortiert jede Hälfte durch einen rekursiven Aufruf und führt die beiden sortierten Hälften dann zu einer geordneten Folge zusammen. Der große Vorteil: Die Laufzeit liegt immer stabil bei O(n log n), egal wie die Eingabedaten aussehen.
Wichtige Punkte
- Teste mit leeren Eingaben, einem einzigen Element, doppelten Werten und bereits sortierten Daten.
- Zuerst richtig machen, dann optimieren.
- Bevorzuge in echtem Code die fertigen Funktionen der Standardbibliothek.
Mergesort (merge sort) in C und C++ visualisieren
O(n)Mit Start oder Schritt kannst du jeden Vergleich und jede Datenbewegung verfolgen.
Codebeispiele in C und C++
#include <stdio.h>
#include <stdlib.h>
void merge_sort(int *values, int *temporary, int left, int right) {
if (right - left < 2) return;
int middle = (left + right) / 2;
merge_sort(values, temporary, left, middle);
merge_sort(values, temporary, middle, right);
int first = left;
int second = middle;
int output = left;
while (first < middle && second < right) {
temporary[output++] = values[first] < values[second]
? values[first++] : values[second++];
}
while (first < middle) temporary[output++] = values[first++];
while (second < right) temporary[output++] = values[second++];
for (int index = left; index < right; ++index) {
values[index] = temporary[index];
}
}
int main(void) {
int values[] = {8, 3, 6, 2, 7};
int temporary[5];
merge_sort(values, temporary, 0, 5);
for (int index = 0; index < 5; ++index) {
printf("%d ", values[index]);
}
}
2 3 6 7 8#include <algorithm>
#include <iostream>
#include <vector>
void merge_sort(std::vector<int>& values) {
if (values.size() < 2) return;
auto middle = values.begin() + values.size() / 2;
std::vector<int> left(values.begin(), middle);
std::vector<int> right(middle, values.end());
merge_sort(left);
merge_sort(right);
std::merge(left.begin(), left.end(), right.begin(), right.end(),
values.begin());
}
int main() {
std::vector values{8, 3, 6, 2, 7};
merge_sort(values);
for (int value : values) {
std::cout << value << ' ';
}
}
2 3 6 7 8C und C++ im Vergleich
Die Funktion merge_sort in C hört auf, wenn ein Abschnitt weniger als 2 Elemente hat. Nach dem Sortieren der beiden Hälften wählt die while-Schleife jeweils das kleinere der beiden vorderen Elemente und kopiert es in das temporäre Array temporary, danach wird der Rest kopiert. Beide Versionen brauchen O(n) zusätzlichen Speicher. Die C-Version verwaltet das temporäre Array selbst, die C++-Version nutzt vector und Standardalgorithmen für klareren Code.
Schleifen, Zeiger, Längen und Zwischenpuffer werden ausdrücklich ausgeschrieben.
Iteratoren und Standardalgorithmen trennen die Verarbeitung von der Art, wie die Daten gespeichert sind.
Übungen zur Vertiefung
Führe beide Versionen aus und ändere dann den Code, um zu beobachten, welche Sicherheit jede Sprache bietet.
- Spiele jeden Vergleich auf Papier durch.
- Teste mit doppelten Werten und mit sehr großen und sehr kleinen Werten.
- Miss die Laufzeit deines Codes und vergleiche sie mit der Standardbibliothek.
Mit einer Challenge üben
Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.
Alle Challenges