Ordinamento a bolle

Lezione 13 di 26 del corso Gli array in C++ di Coddy.

Un altro modo di ordinare un array si chiama bubble sort. L'idea è confrontare ogni coppia di numeri adiacenti e scambiarli se il numero a destra è più piccolo di quello a sinistra, finché non raggiungiamo la fine.

1. Dichiara la variabile chiamata counter e inizializzala con 1. counter tiene il conto degli elementi ordinati.

2. Crea un while ciclo con una condizione che ripeta l'iterazione finché counter è minore di n.

int counter=1;
while(counter<n){
     
}

3. Crea un for ciclo all'interno del ciclo while e iteralo da 0 a n-counter volte. Questo perché il numero di elementi indicato da counter è già ordinato e non dobbiamo controllarli di nuovo.

int counter=1;
while(counter<n){
     for(int i=0;i<n-counter;i++){
     
     }
}

4. Poi confronta l'elemento i-esimo con quello successivo, cioè l'elemento (i+1)-esimo, e se arr[i]>arr[i+1] scambiali.

Possiamo vedere che nella prima iterazione del ciclo while esterno l'elemento più grande viene spinto all'ultima posizione, ed è per questo che ignoriamo quella parte nell'iterazione successiva e incrementiamo counter di 1.

int counter=1;
while(counter<n){
  for(int i=0;i<n-counter;i++){
    if(arr[i]>arr[i+1]){
      int temp=arr[i];
      arr[i]=arr[i+1];
      arr[i+1]=temp;
    }
  }
  counter++;
}

Analisi della complessità temporale

Eseguiamo un ciclo while n volte e in ogni ciclo while un ciclo for viene eseguito quasi n volte; pertanto, la complessità temporale diventa O(n²).

Per vedere come funziona effettivamente l'algoritmo, passo dopo passo.

Visualizzatore di bubble sort

Sfida

Ordina l'array dato usando l'algoritmo ordinamento a bolle e stampa ogni elemento il cui indice è dispari. Separa gli elementi con un singolo spazio.

Provalo tu

#include<iostream>
using namespace std;


int main(){
  
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++){
  cin>>arr[i];
}

//Code Here




return 0;

}