Ordinamento a bolle e per inserimento
Ordinamenti semplici
Ordinamento a bolle e per inserimento è una lezione C Academy gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento C Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso C Academy include 4 lezioni in totale.
Ordinamenti semplici
Bubble sort e insertion sort sono i due algoritmi di ordinamento per confronto più semplici. In entrambi i casi, il caso peggiore è O(n al quadrato), ma sono facili da comprendere e utili per array piccoli o quasi ordinati.
Come funziona il bubble sort
Il bubble sort percorre ripetutamente l'array, scambiando le coppie adiacenti fuori ordine. Dopo ogni passaggio completo, l'elemento più grande tra quelli rimanenti sale fino alla posizione finale in fondo all'array.
Scambio di due interi
Una funzione di supporto riutilizzabile per lo scambio mantiene pulito il codice dell'ordinamento.
#include <stdio.h>
void swap(int *a, int *b) {
int t = *a; *a = *b; *b = t;
}
int main(void) {
int x = 1, y = 2;
swap(&x, &y);
printf("%d %d\n", x, y);
return 0;
}Implementazione del bubble sort
Usiamo cicli annidati: il ciclo esterno conta i passaggi, quello interno confronta le coppie adiacenti ed esegue gli scambi. Dopo il passaggio i, gli ultimi i elementi sono ordinati.
#include <stdio.h>
void bubble_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
}
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
bubble_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Ottimizzazione con uscita anticipata
Se un passaggio completo non esegue alcuno scambio, l'array è già ordinato e potete interrompere l'algoritmo. In questo modo il bubble sort ha costo O(n) su un input già ordinato.
#include <stdio.h>
void bubble_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0;
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; swapped = 1;
}
if (!swapped) break;
}
}
int main(void) {
int a[] = {1, 2, 3, 4, 5};
bubble_sort(a, 5);
printf("sorted with early exit\n");
return 0;
}Come funziona l'insertion sort
L'insertion sort costruisce una regione ordinata all'inizio dell'array. Per ogni nuovo elemento, sposta a destra gli elementi ordinati più grandi e inserisce il nuovo elemento nella posizione corretta, come quando si ordinano le carte da gioco in mano.
Implementazione dell'insertion sort
Prendiamo l'elemento key = a[i], poi spostiamo di uno slot a destra ogni elemento più grande in a[0..i-1] e inseriamo key nello spazio creato.
#include <stdio.h>
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
insertion_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Insertion sort su dati quasi ordinati
L'insertion sort è particolarmente efficace quando l'array è quasi ordinato: ogni elemento si sposta di poche posizioni, avvicinandosi a O(n). Per questo viene usato come fase finale negli algoritmi di ordinamento ibridi.
#include <stdio.h>
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) { a[j+1] = a[j]; j--; }
a[j+1] = key;
}
}
int main(void) {
int a[] = {1, 2, 4, 3, 5}; /* one out of place */
insertion_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Stabilità
Entrambi gli algoritmi sono stabili: gli elementi uguali mantengono il loro ordine relativo originale, perché vengono scambiati o spostati solo in presenza di un confronto strettamente maggiore. La stabilità è importante quando si ordinano record in base a più chiavi.
Confronto della complessità
Entrambi hanno complessità media e nel caso peggiore pari a O(n al quadrato), ma nella pratica differiscono:
- Bubble sort: molti scambi, usato raramente nel codice reale
- Insertion sort: meno scritture, ottimo per array piccoli o quasi ordinati
Con le ottimizzazioni, il caso migliore per entrambi è O(n).
Conteggio delle operazioni
Contiamo i confronti eseguiti dall'insertion sort su un array ordinato al contrario, cioè nel caso peggiore.
#include <stdio.h>
int main(void) {
int a[] = {5, 4, 3, 2, 1};
int n = 5; long cmp = 0;
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && (cmp++, a[j] > key)) { a[j+1] = a[j]; j--; }
a[j+1] = key;
}
printf("comparisons = %ld\n", cmp);
return 0;
}Verifica rapida
Verifichi la Sua comprensione degli ordinamenti semplici.
Riepilogo
Ha imparato due semplici algoritmi di ordinamento O(n al quadrato).
- Il bubble sort scambia coppie adiacenti a ogni passaggio
- L'insertion sort sposta gli elementi e inserisce ciascun elemento nella parte iniziale ordinata
- Entrambi sono stabili; con l'ottimizzazione, entrambi raggiungono O(n) su input ordinati
- L'insertion sort è la scelta più pratica per dati di piccole dimensioni
Domande Frequenti
La lezione «Ordinamento a bolle e per inserimento» è gratuita?
Sì — il testo completo di «Ordinamento a bolle e per inserimento» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso C Academy, passa a CoddyKit PRO. Il corso C Academy include 4 lezioni in totale.
Cosa imparerò in «Ordinamento a bolle e per inserimento»?
Ordinamenti semplici Eserciti C Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare C Academy?
Non è richiesta alcuna esperienza precedente. C Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «Ordinamento a bolle e per inserimento»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione C Academy?
Sì. Ogni lezione C Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Ordinamento a bolle e per inserimento
- Quicksort
- Mergesort
- Usare qsort