C/C++-Algorithmen

Merge Sort

Merge Sort sortiert rekursiv beide Hälften und führt sie zusammen.

Was ist Merge Sort?

Merge Sort sortiert rekursiv beide Hälften und führt sie zusammen.

Sortiere mit Teile-und-herrsche zuverlässig in O(n log n).

Wichtige Punkte

Teste leere, einzelne, doppelte und sortierte Eingaben.
Trenne Korrektheit von Optimierung.
Nutze in Produktivcode bevorzugt die Standardbibliothek.

Merge Sort visualisieren

O(n)

Mit Start oder Schritt kannst du jeden Vergleich und jede Datenbewegung verfolgen.

Codebeispiele in C und C++

Code ausführen →

main.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]);
    }
}

Erwartete Ausgabe

2 3 6 7 8

C++

Code ausführen →

main.cpp

#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 << ' ';
    }
}

Erwartete Ausgabe

2 3 6 7 8

Vergleich zwischen C und C++

Beide benötigen O(n) Hilfsspeicher; C verwaltet einen Puffer explizit, C++ verwendet vector und Standardalgorithmen.

Schleifen, Pointer, Längen und Puffer sind explizit.

C++

Iteratoren und Algorithmen trennen Operation und Speicherung.

Übungsaufgaben

Führe beide Versionen aus und untersuche die unterschiedlichen Garantien.

Verfolge jeden Vergleich manuell.
Teste Duplikate und Extremwerte.
Vergleiche die Laufzeit mit der Standardbibliothek.