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

L'ordinamento a bolle (bubble sort) in C e C++

In questa lezione implementerai il bubble sort scambiando ripetutamente le coppie di elementi vicini che sono nell'ordine sbagliato.

Introduzione

Il bubble sort scorre l'array più volte, confrontando ogni coppia di elementi vicini e scambiandoli se sono nell'ordine sbagliato. A ogni passata, il valore più grande non ancora ordinato si sposta gradualmente verso la fine dell'array.

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 a bolle (bubble 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>

int main(void) {
    int values[] = {5, 1, 4, 2};
    for (int end = 3; end > 0; --end) {
        int changed = 0;
        for (int index = 0; index < end; ++index) {
            if (values[index] > values[index + 1]) {
                int temporary = values[index];
                values[index] = values[index + 1];
                values[index + 1] = temporary;
                changed = 1;
            }
        }
        if (!changed) break;
    }
    for (int index = 0; index < 4; ++index) {
        printf("%d ", values[index]);
    }
}
Risultato dell'esecuzione
1 2 4 5
C++
Esegui →
main.cpp
#include <iostream>
#include <vector>

int main() {
    std::vector values{5, 1, 4, 2};
    for (auto end = values.end(); end != values.begin(); --end) {
        bool changed = false;
        for (auto item = values.begin(); item + 1 != end; ++item) {
            if (*item > *(item + 1)) {
                std::iter_swap(item, item + 1);
                changed = true;
            }
        }
        if (!changed) break;
    }
    for (int value : values) {
        std::cout << value << ' ';
    }
}
Risultato dell'esecuzione
1 2 4 5

Confronto tra C e C++

La variabile changed registra se nella passata c'è stato almeno uno scambio. Se non ce n'è stato nessuno, l'array è già ordinato e il ciclo si ferma prima, quindi un array già ordinato costa solo O(n). Nel caso peggiore l'algoritmo richiede O(n²), per questo si usa soprattutto per imparare. Nella pratica il codice C++ usa di solito std::sort.

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