Struttura dei dati - Algoritmo di ordinamento a bolle

Bubble sort è un semplice algoritmo di ordinamento. Questo algoritmo di ordinamento è un algoritmo basato sul confronto in cui viene confrontata ogni coppia di elementi adiacenti e gli elementi vengono scambiati se non sono in ordine. Questo algoritmo non è adatto per set di dati di grandi dimensioni poiché la sua complessità media e nel caso peggiore sono Ο (n ² ) doven è il numero di elementi.

Come funziona Bubble Sort?

Prendiamo un array non ordinato per il nostro esempio. Il Bubble sort richiede Ο (n ² ) tempo, quindi lo manteniamo breve e preciso.

Bubble sort inizia con i primi due elementi, confrontandoli per verificare quale sia il maggiore.

In questo caso, il valore 33 è maggiore di 14, quindi è già nelle posizioni ordinate. Successivamente, confrontiamo 33 con 27.

Troviamo che 27 è minore di 33 e questi due valori devono essere scambiati.

Il nuovo array dovrebbe essere simile a questo:

Successivamente confrontiamo 33 e 35. Troviamo che entrambi sono in posizioni già ordinate.

Quindi passiamo ai due valori successivi, 35 e 10.

Sappiamo allora che 10 è minore di 35. Quindi non vengono ordinati.

Scambiamo questi valori. Troviamo che abbiamo raggiunto la fine dell'array. Dopo un'iterazione, l'array dovrebbe apparire così:

Per essere precisi, ora stiamo mostrando come dovrebbe apparire un array dopo ogni iterazione. Dopo la seconda iterazione, dovrebbe apparire così:

Notare che dopo ogni iterazione, almeno un valore si sposta alla fine.

E quando non è richiesto lo scambio, l'ordinamento a bolle apprende che un array è completamente ordinato.

Ora dovremmo esaminare alcuni aspetti pratici del Bubble sort.

Algoritmo

Assumiamo list è un array di nelementi. Supponiamo inoltre cheswap funzione scambia i valori degli elementi dell'array dati.

begin BubbleSort(list)

   for all elements of list
      if list[i] > list[i+1]
         swap(list[i], list[i+1])
      end if
   end for
   
   return list
   
end BubbleSort

Pseudocodice

Osserviamo nell'algoritmo che Bubble Sort confronta ogni coppia di elementi dell'array a meno che l'intero array non sia completamente ordinato in ordine crescente. Ciò potrebbe causare alcuni problemi di complessità come se l'array non avesse più bisogno di essere scambiato poiché tutti gli elementi sono già in ascesa.

Per facilitare il problema, utilizziamo una variabile flag swappedche ci aiuterà a vedere se è avvenuto o meno uno scambio. Se non si è verificato alcuno scambio, ovvero l'array non richiede più elaborazioni per essere ordinato, uscirà dal ciclo.

Lo pseudocodice dell'algoritmo BubbleSort può essere scritto come segue:

procedure bubbleSort( list : array of items )

   loop = list.count;
   
   for i = 0 to loop-1 do:
      swapped = false
		
      for j = 0 to loop-1 do:
      
         /* compare the adjacent elements */   
         if list[j] > list[j+1] then
            /* swap them */
            swap( list[j], list[j+1] )		 
            swapped = true
         end if
         
      end for
      
      /*if no number was swapped that means 
      array is sorted now, break the loop.*/
      
      if(not swapped) then
         break
      end if
      
   end for
   
end procedure return list

Implementazione

Un altro problema che non abbiamo affrontato nel nostro algoritmo originale e nel suo pseudocodice improvvisato è che, dopo ogni iterazione, i valori più alti si depositano alla fine dell'array. Quindi, l'iterazione successiva non deve includere elementi già ordinati. A tale scopo, nella nostra implementazione, restringiamo il ciclo interno per evitare valori già ordinati.

Per conoscere l'implementazione del bubble sort nel linguaggio di programmazione C, fare clic qui .