L’algoritmo per il Bubble Sort richiede una coppia di cicli nidificati. Il ciclo esterno deve iterare una volta per ogni elemento nel set di dati (di dimensione n) mentre il ciclo interno itera n volte la prima volta che viene inserito, n-1 volte la seconda e così via. Considera lo scopo di ogni ciclo. Come spiegato sopra, l’ordinamento a bolle è strutturato in modo che ad ogni passaggio dell’elenco l’elemento successivo più grande dei dati venga spostato nella posizione corretta. Pertanto, per ottenere tutti gli n elementi nelle loro posizioni corrette, il ciclo esterno deve essere eseguito n volte.
Il ciclo interno viene eseguito ad ogni iterazione del ciclo esterno. Il suo scopo è mettere in atto il successivo elemento più grande. Il ciclo interno quindi esegue il confronto e lo scambio di elementi adiacenti. Per determinare la complessità di questo ciclo, calcoliamo il numero di confronti che devono essere effettuati. Sulla prima iterazione del ciclo esterno, mentre si cerca di posizionare l’elemento più grande, devono esserci n – 1 confronti: il primo confronto viene effettuato tra il primo e il secondo elemento, il secondo viene effettuato tra il secondo e il terzo elemento, e così via fino a quando non viene effettuato l’n-1 ° confronto tra l’n-1 ° e l’ennesimo elemento. Nella seconda iterazione del ciclo esterno, non è necessario confrontare il con l’ultimo elemento della lista, perché è stato messo nella posizione corretta nel passaggio precedente. Pertanto, la seconda iterazione richiede solo confronti n-2. Questo modello continua fino alla penultima iterazione del ciclo esterno quando solo i primi due elementi dell’elenco non sono ordinati; chiaramente in questo caso è necessario un solo confronto. Il numero totale di confronti, quindi, è (n – 1) + (n – 2) … (2) + (1) = n (n – 1) / 2 o O (n2).
Il caso migliore per l’ordinamento a bolle si verifica quando l’elenco è già ordinato o quasi ordinato. Nel caso in cui l’elenco sia già ordinato, il Bubble sort terminerà dopo la prima iterazione, poiché non sono stati effettuati scambi. Ogni volta che viene eseguito un passaggio nell’elenco e non sono stati effettuati scambi, è certo che l’elenco è ordinato. L’ordinamento a bolle è efficiente anche quando un elemento casuale deve essere ordinato in un elenco ordinato, a condizione che il nuovo elemento sia posizionato all’inizio e non alla fine. Quando viene posizionato all’inizio, si limiterà a bolle nella posizione corretta e la seconda iterazione nell’elenco genererà 0 scambi, terminando l’ordinamento. Ricorda che se l’elemento casuale viene posizionato alla fine, il bubble sort perde la sua efficienza perché ogni elemento maggiore di esso deve creare bolle fino in cima.
Il caso peggiore in assoluto per il bubble sort è quando il l’elemento più piccolo dell’elenco è all’estremità grande. Poiché in ogni iterazione solo l’elemento più grande non ordinato viene messo nella sua posizione corretta, quando l’elemento più piccolo è alla fine, dovrà essere scambiato ogni volta nell’elenco e non arriverà all’inizio dell’elenco fino a quando tutti gli n si sono verificate iterazioni. In questo caso peggiore, sono necessarie n iterazioni di n / 2 swap, quindi l’ordine è, di nuovo, n2.
Caso migliore: nAverage Case: n2Worst Case: n2