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

L'ordinamento rapido (quick sort) in C e C++

In questa lezione implementerai il quick sort partizionando l'array attorno a un elemento perno (pivot).

Introduzione

Il quick sort sceglie un elemento come perno (pivot) e riorganizza l'array in modo che gli elementi minori del pivot stiano a sinistra e gli altri a destra. A quel punto il pivot è già nella sua posizione finale, e l'algoritmo continua a ordinare le due parti con la ricorsione.

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 rapido (quick sort) in C e C++

O(n log 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>

void swap(int *left, int *right) {
    int temporary = *left;
    *left = *right;
    *right = temporary;
}

int partition(int *values, int low, int high) {
    int pivot = values[high];
    int boundary = low;
    for (int scan = low; scan < high; ++scan) {
        if (values[scan] < pivot) {
            swap(&values[boundary++], &values[scan]);
        }
    }
    swap(&values[boundary], &values[high]);
    return boundary;
}

void quick_sort(int *values, int low, int high) {
    if (low >= high) return;
    int pivot = partition(values, low, high);
    quick_sort(values, low, pivot - 1);
    quick_sort(values, pivot + 1, high);
}

int main(void) {
    int values[] = {9, 4, 7, 3, 10, 5};
    quick_sort(values, 0, 5);
    for (int index = 0; index < 6; ++index) {
        printf("%d ", values[index]);
    }
}
Risultato dell'esecuzione
3 4 5 7 9 10
C++
Esegui →
main.cpp
#include <algorithm>
#include <iostream>
#include <vector>

template<class Iterator>
void quick_sort(Iterator first, Iterator last) {
    if (last - first < 2) return;
    auto pivot = *(last - 1);
    auto middle = std::partition(first, last - 1,
        [pivot](int value) { return value < pivot; });
    std::iter_swap(middle, last - 1);
    quick_sort(first, middle);
    quick_sort(middle + 1, last);
}

int main() {
    std::vector values{9, 4, 7, 3, 10, 5};
    quick_sort(values.begin(), values.end());
    for (int value : values) {
        std::cout << value << ' ';
    }
}
Risultato dell'esecuzione
3 4 5 7 9 10

Confronto tra C e C++

La funzione partition in C sceglie l'ultimo elemento come pivot e usa la variabile boundary per segnare il confine della zona degli elementi minori. Alla fine il pivot viene scambiato nella posizione boundary. La versione in C++ usa std::partition per esprimere il partizionamento in modo più breve. La complessità media è O(n log n), ma con un pivot scelto male può arrivare a O(n²).

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