Analisi della complessità
Lezione 5 di 11 del corso Ordinamento a bolle di Coddy.
Analisi della complessità del bubble sort.
La complessità temporale dipende dal numero di confronti & scambi effettuati.
Dobbiamo eseguire n passate e in ogni passata abbiamo (n-1) confronti. dove, n è il numero di elementi nella lista.
Confronti totali=(n-1)+(n-1)+(n-1)....n volte
=n*(n-1)
=n2-n
La complessità temporale dell'algoritmo bubble sort è O(n2).
Per quanto riguarda la complessità spaziale, nell'algoritmo non viene utilizzato spazio aggiuntivo: viene eseguito un ordinamento in-place e gli elementi vengono disposti direttamente nella lista originale.
La complessità spaziale dell'algoritmo bubble sort è O(1) (costante).
Sfida
FacileCrea una funzione chiamata count_swaps che riceve un array e la dimensione dell’array. Esegui l’algoritmo di ordinamento a bolle sull’array e conta il numero di volte in cui viene effettuato uno scambio.
Provalo tu
#include <stdio.h>
#include <stdlib.h>
int count_swaps(int* arr, int arr_size, int n) {
// Scrivi il codice qui
return 0;
}
Tutte le lezioni di Ordinamento a bolle
1Nozioni di base dell'ordinamento a bolle
IntroduzioneCome funziona l'ordinamento a bolleScambiare elementi adiacentiAlgoritmo di ordinamento a bolleEsercitati da solo: Compilatore C online