I programmatori che passano dallo sviluppo per PC e Web alla codifica per dispositivi mobili o sistemi embedded scoprono che viene dedicato più tempo alla selezione e alla codifica delle proprie strutture dati e algoritmi. Con meno memoria e un'archiviazione dei dati limitata, non c'è spazio per librerie o framework predefiniti. Quindi, per coloro che hanno bisogno di scrivere le proprie routine di ordinamento, ecco alcune considerazioni sulla scelta dell'umile bubble sort.
Sfondo
Il bubble sort è un semplice algoritmo che ordina un elenco 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 si verificano più scambi. Se fosse possibile visualizzare l'array mentre l'ordinamento è in corso, i valori bassi "bollerebbero" verso l'alto mentre i valori grandi affonderebbero verso il basso. Ecco il codice pertinente in Visual Basic 2010:
Video del giorno
Mentre swap = True swap = False For i = 0 To tbl.length - 2 Se tbl (i) > tbl (i + 1) Allora tmp = tbl (i) tbl (i) = tbl (i + 1) tbl (i + 1) = tmp swap = True End If Next End While
Quando scegliere l'ordinamento a bolle?
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 sovraccarico di memoria e, una volta ordinati, i dati sono in memoria, pronti per l'elaborazione. Lo svantaggio principale è la quantità di tempo necessaria per l'ordinamento. Il tempo medio aumenta in modo quasi esponenziale all'aumentare del numero di elementi della tabella. Dieci volte il numero di elementi richiede quasi cento volte il tempo per l'ordinamento.
Altri tipi di array
Gli algoritmi di ordinamento variano in complessità, velocità e sovraccarico. Il bubble sort è il meno complesso ma anche uno dei più lenti. Altri ordinamenti basati su array come l'ordinamento per inserimento e l'ordinamento per scambio sono un po' più veloci ma richiedono più codice (vedere i riferimenti di seguito). Il vantaggio principale degli ordinamenti basati su array è che utilizzano il minor codice e occupano la minor quantità di memoria di lavoro. Considera questi tipi per array semplici con meno di poche centinaia di elementi.
Algoritmi di ordinamento complessi
Set di dati più grandi richiedono codice più complesso e più memoria. L'ordinamento rapido e l'ordinamento heap dividono e copiano i set di dati per ottimizzare il numero di confronti. L'ordinamento rapido divide continuamente l'elenco, quindi lo riassembla in ordine ordinato. L'ordinamento dell'heap copia i dati in una struttura ad albero, quindi attraversa l'albero per ricopiare i dati in ordine. Entrambi sono veloci ed efficienti, ma richiedono più codice e molto più spazio di archiviazione. Scegli questi algoritmi per set di dati di grandi dimensioni.
