Edizione didattica italiana
Bubble sort in C: scambi adiacenti
Ordina confrontando vicini e interrompi quando non avvengono scambi.
A ogni passaggio confronta elementi adiacenti e scambiali se necessario. Il maggiore della parte rimasta arriva in fondo, quindi il passaggio successivo può essere più corto.
Un indicatore consente di fermarsi se non ci sono scambi. Con questa ottimizzazione, input ordinati costano O(N), ma casi generali e peggiori restano O(N²). Lo spazio ausiliario è O(1).
Non usare arr[j + 1] se j è già l’ultimo indice. Prova duplicati e ordine inverso. Scambiare soltanto se il valore sinistro è strettamente maggiore preserva l’ordine degli uguali.
Codice sorgente
#include <stdio.h>
#include <stdbool.h>
void bubble_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
bool swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break; // Array is already sorted
}
}
void print_array(const int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main(void) {
int data[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(data) / sizeof(data[0]);
printf("Original array: ");
print_array(data, n);
bubble_sort(data, n);
printf("Sorted array: ");
print_array(data, n);
return 0;
}Risultato atteso
Original array: 64 34 25 12 22 11 90 Sorted array: 11 12 22 25 34 64 90
Domande frequenti
Perché il codice e alcuni risultati restano in inglese?
Parole chiave C, identificatori, commenti del programma e output attesi restano quelli originali per preservare codice eseguibile e test coerenti. Spiegazioni e istruzioni sono tradotte.