Vantaggi e Svantaggi del Bubble Sort

I programmatori che passano dallo sviluppo PC e web alla codifica per dispositivi mobili o sistemi embedded scoprono che più tempo viene speso nella selezione e codifica delle proprie strutture dati e algoritmi. Con meno memoria e spazio di archiviazione dati limitato, non c'è spazio per librerie o framework pre-costruiti. Quindi per chi deve scrivere le proprie routine di ordinamento, ecco alcune considerazioni sulla scelta del umile bubble sort.

Background

Il bubble sort è un algoritmo semplice che ordina una lista di elementi in memoria. Dato un array, il codice confronta ripetutamente ogni coppia di elementi adiacenti e li scambia se non sono in ordine. Il processo si ripete finché non avvengono più scambi. Se fosse possibile visualizzare l'array mentre l'ordinamento è in corso, i valori bassi "risalirebbero" in alto mentre i valori grandi affonderebbero in basso. Ecco il codice rilevante in Visual Basic 2010:

While swap = True
  swap = False
  For i = 0 To tbl.length - 2
    If tbl(i) > tbl(i + 1) Then
      tmp = tbl(i)
      tbl(i) = tbl(i + 1)
      tbl(i + 1) = tmp
      swap = True
    End If
  Next
End While

Quando Scegliere il Bubble Sort

Questo algoritmo ha diversi vantaggi. È semplice da scrivere, facile da capire e richiede solo poche righe di codice. I dati vengono ordinati sul posto quindi c'è poco overhead di memoria e, una volta ordinati, i dati sono in memoria, pronti per l'elaborazione. Lo svantaggio maggiore è il tempo che impiega a ordinare. Il tempo medio aumenta quasi esponenzialmente all'aumentare del numero di elementi della tabella. Dieci volte il numero di elementi richiede quasi cento volte il tempo per ordinare.

Altri Ordinamenti per Array

Gli algoritmi di ordinamento variano in complessità, velocità e overhead. Il bubble sort è il meno complesso ma anche uno dei più lenti. Altri ordinamenti basati su array come l'insertion sort e l'exchange sort sono un po' più veloci ma richiedono più codice (vedi riferimenti sotto). Il vantaggio principale degli ordinamenti basati su array è che usano meno codice e richiedono la minor quantità di memoria di lavoro. Considera questi ordinamenti per array semplici con meno di qualche centinaio di elementi.

Algoritmi di Ordinamento Complessi

Set di dati più grandi richiedono codice più complesso e più memoria. Il quick sort e l'heap sort dividono e copiano entrambi i set di dati per ottimizzare il numero di confronti. Il quick sort divide continuamente la lista poi la riassembla in ordine. L'heap sort copia i dati in una struttura ad albero poi percorre l'albero per ricopiare i dati in ordine. Entrambi sono veloci ed efficienti ma richiedono più codice e molto più spazio di lavoro. Scegli questi algoritmi per grandi set di dati.