[Algoritmi di ordinamento] Bubble Sorting

Aleandro Prudenzano/ ottobre 31, 2017/ Developing/ 0 comments

Nella vita di ogni programmatore o appassionato di programmazione che sia, almeno una volta è sorto il problema di ordinare un array (o ArrayList). 

In questo articolo quindi inizieremo a vedere gli algoritmi di Sorting (ordinamento) degli array monodimensionali.

Come funziona?

Il bubble sorting è l’algoritmo di ordinamento degli array più semplice da immaginare ed implementare, si compone di soli due cicli annidati.
Non sfrutta la ricorsione ma ha la più bassa efficienza in termini di tempi (nel caso peggiore, cioè un array ordinato al contrario rispetto al nostro criterio ci metterà la bellezza di n2 scambi di valori con n come lunghezza dell’array).

Dato un array di esempio di 5 elementi che definiremo come {3,1,5,2,4}, iniziamo con le comparazioni partendo dal primo elemento: 3.
Andiamo a scorrere in avanti finché non troviamo un valore minore di esso.
In questo caso abbiamo 1 subito dopo che essendo minore di 3, verrà permutato, ottenendo quindi il vettore {1,3,5,2,4}.
Continuiamo tenendo fermo 1 e cercando qualsiasi numero minore.
Nella sequenza di esempio non ce ne sono, quindi procederemo puntando il numero successivo: teniamo fermo il 3 e scorriamo la lista cercando un numero minore con cui permutarlo.
Due numeri dopo abbiamo 2 che essendo minore di 3 verrà permutato, ottenendo {1,2,5,3,4}, ora possiamo continuare con questa serie di passaggi fino ad ottenere l’array ordinato {1,2,3,4,5}.

Gli step essenziali di questo ordinamento sono:

  1. Fissare l’elemento all’inizio della sequenza
  2. Cercare un numero minore di esso avanti a lui con cui permutarlo
  3. Se non esiste nessun numero che soddisfi la richiesta, fissare il numero successivo e torna al passo 2

Implementazione in C

Spiegazione del codice

Iniziamo con un for che faccia ciclare tutti i valori dell’array partendo dal primo, ma evitando l’ultimo (per evitare di richiedere l’accesso ad una casella vuota nel for successivo).
All’interno di questo for ne inseriamo un altro che inizia la sua corsa a partire dall’elemento dopo rispetto a quello selezionato dal primo ciclo, che tuttavia scorre fino alla fine dell’array.
Ora abbiamo due cicli che scorreranno tutti i valori uno ad uno e possiamo procedere a comparare i valori: se l’elemento selezionato dal secondo ciclo è minore dell’elemento selezionato dal primo ciclo, procediamo a scambiare i due tramite l’ausilio di una variabile d’appoggio.

Conclusione

Per qualsiasi dubbio potete contattarci utilizzando i commenti o le nostre pagine social.

About Aleandro Prudenzano

17 anni passati tra scienza, computer, elettronica e serie tv. Ora provo a raccontare a voi un po' delle cose che ho imparato negli anni nell'attesa di impararne altre. Enjoy the culture!

Facci sapere cosa ne pensi con un commento!