CodeUtility
Facilitiamo la vita agli sviluppatori!
Algoritmi C/C++

L'ordinamento per fusione (merge sort) in C e C++

In questa lezione implementerai il merge sort con la strategia divide et impera, che richiede sempre tempo O(n log n).

Introduzione

Il merge sort divide l'array in due metà, ordina ciascuna con chiamate ricorsive e poi fonde le due metà ordinate in una sequenza ordinata. Il grande vantaggio è che il tempo di esecuzione resta sempre O(n log n), qualunque sia l'ordine dei dati in ingresso.

Punti importanti

  • Prova con input vuoti, con un solo elemento, con valori ripetuti e già ordinati.
  • Prima fai funzionare il codice correttamente, poi ottimizza.
  • Nel codice reale preferisci le funzioni pronte della libreria standard.

Visualizzatore di L'ordinamento per fusione (merge sort) in C e C++

O(n)

Usa Avvia o Passo per seguire ogni confronto e spostamento dei dati.

Esempi di codice C e C++

C
Esegui →
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]);
    }
}
Risultato dell'esecuzione
2 3 6 7 8
C++
Esegui →
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 << ' ';
    }
}
Risultato dell'esecuzione
2 3 6 7 8

Confronto tra C e C++

La funzione merge_sort in C si ferma quando il tratto ha meno di 2 elementi. Dopo aver ordinato le due metà, il ciclo while sceglie l'elemento più piccolo all'inizio di ciascuna metà e lo copia nell'array temporaneo temporary, poi copia ciò che resta. Entrambe le versioni richiedono O(n) di memoria aggiuntiva. La versione in C gestisce a mano l'array temporaneo, quella in C++ usa vector e gli algoritmi standard per rendere il codice più chiaro.

C

Cicli, puntatori, lunghezze e buffer temporanei sono scritti esplicitamente.

C++

Iteratori e algoritmi standard separano l'elaborazione dal modo in cui i dati sono memorizzati.

Esercizi di approfondimento

Esegui entrambe le versioni e poi modifica il codice per osservare la differenza di sicurezza che offre ciascun linguaggio.

  • Simula ogni confronto su carta.
  • Prova con valori ripetuti e con valori molto grandi e molto piccoli.
  • Misura il tempo del tuo codice e confrontalo con la libreria standard.

Esercitati con una sfida

Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.

Tutte le sfide