Bubble sort: differenze tra le versioni

Versione delle 10:38, 10 nov 2005

Versione attuale delle 01:40, 16 lug 2025

(379 versioni intermedie di oltre 100 utenti non mostrate)

Riga 1:

{{F|programmazione|luglio 2012}}

Il '''bubble sort''' o '''bubblesort''' (letteralmente: ''ordinamento a bollicine'') è un semplice [[algoritmo]] [[algoritmo di ordinamento|di ordinamento]] particolarmente indicato per l'ordinamento di [[array]]. Pur non essendo un algoritmo particolarmente efficiente (ha una [[complessità|complessità computazionale]] (misurata in termini di numero di confronti e [[assegnamento|assegnamenti]]) ''O(n²)'', molto superiore per esempio a quella del [[quicksort]]), è piuttosto noto e utilizzato (sia in ambito didattico che da parte di programmatori professionisti) in virtù della sua semplicità. Dell'algoritmo esistono numerose varianti, in alcuni casi sufficientemente note da aver meritato un nome distinto (per esempio, lo [[shakersort]]). Come tutti gli algoritmi di ordinamento, può essere usato per ordinare dati di un qualsiasi tipo su cui sia definita una [[relazione d'ordine]]; a fini illustrativi, in questo articolo ci riferiremo all'ordinamento di un array di [[numero intero|numeri interi]]. Il nome dell'algoritmo è dovuto al fatto che, durante l'applicazione del procedimento, i valori vengono spostati all'interno dell'array con una dinamica che ricorda il movimento delle bollicine in un bicchiere di [[champagne]]. In particolare, alcuni elementi attraversano l'array velocemente (come bollicine che emergono dal fondo del bicchiere), altri più lentamente (a differenza di quanto avviene nel caso del bicchiere di champagne, tuttavia, alcuni elementi ''salgono'' ma altri ''scendono'').

{{Algoritmo

|classe = [[Algoritmo di ordinamento]]

|immagine = Sorting bubblesort anim.gif

|didascalia = Bubble sort in esecuzione

|struttura dati = [[Array]]

|tempo migliore = <math>O(n^2)</math>

Se si utilizza una guardia allora: <math>O(n)</math>

|tempo medio = <math>O(n^2)</math>

|tempo = <math>O(n^2)</math>

|spazio = <math>O(n)</math> totale, <math>O(1)</math> ausiliario

|ottimale = No

|completo =

}}

[[File:Bubblesort-edited-color.svg|alt=Bubble sort colore modificato|frame|Svolgimento dell'algoritmo Bubblesort, versione colorata]]

In [[informatica]] il '''Bubble sort''' o ''ordinamento a bolla'' è un semplice [[algoritmo di ordinamento]] di liste di dati. In esso l'insieme di dati viene scansionato, ogni coppia di elementi adiacenti viene comparata ed i due elementi vengono invertiti di posizione se sono nell'ordine sbagliato. L'algoritmo continua a ri-eseguire questi passaggi su tutta la lista fino a quando non vengono più eseguiti scambi, situazione che indica che la lista è ordinata.<ref>

{{Cita web

|url = https://stackoverflow.com/questions/tagged/bubble-sort

|titolo = Newest 'bubble sort' Questions

|sito = Stack Overflow

|citazione = Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

|lingua = en

}}</ref>

== Denominazione ed efficienza ==

==Spiegazione astratta==

L'algoritmo deve il suo nome al modo in cui gli elementi vengono ordinati: quelli più piccoli "risalgono" verso un'estremità della lista, mentre quelli più grandi "affondano" verso l'estremità opposta della lista, come le bolle in un bicchiere contenente una bevanda frizzante. In particolare, alcuni elementi attraversano la lista velocemente (in gergo detti "''lepri''"), altri invece più lentamente (detti "''tartarughe''"). I primi vengono spostati nella stessa direzione in cui scorre l'indice dell'algoritmo, mentre i secondi nella direzione opposta.

Come tutti gli algoritmi di ordinamento, può essere usato per ordinare dati di qualsiasi tipo per i quali sia definita una [[relazione d'ordine]].

Il bubblesort è un algoritmo [[algoritmo iterativo|iterativo]], ovvero basato sulla ripetizione di un procedimento fondamentale. La singola iterazione dell'algoritmo prevede che gli elementi dell'array siano confrontati a due a due, scandendo l'algoritmo in un verso stabilito (se si scandisca l'array a partire dall'inizio in avanti, o a partire dal fondo all'indietro, è irrilevante; nel seguito ipotizzeremo che lo si scandisca partendo dall'inizio; supporremo inoltre che si voglia ordinare l'array in modo crescente). Per esempio, saranno confrontati il primo e il secondo elemento, poi il secondo e il terzo, poi il terzo e il quarto, e così via fino al confronto fra penultimo e ultimo elemento. Per ogni confronto, se i due elementi confrontati non sono ordinati, essi vengono scambiati. Durante ogni iterazione, almeno un valore viene spostato rapidamente fino a raggiungere la sua collocazione definitiva; in particolare, alla prima iterazione il numero più grande raggiunge l'ultima posizione dell'array. Il motivo è semplice, e si può illustrare con un esempio. Supponiamo che l'array sia inizialmente disposto come segue:

Il Bubble sort è più efficiente rispetto al più semplice algoritmo di Ordinamento Ingenuo perché, invece di continuare ad eseguire sempre fino alla fine i due cicli annidati, si interrompe quando l'ordinamento è completo. Si tratta comunque di un algoritmo non particolarmente efficiente, presentando una [[Teoria della complessità computazionale|complessità computazionale]] dell'ordine di ''[[O-grande|O]]<math>(n^2)</math>'' confronti con ''n'' elementi da ordinare, pertanto il suo utilizzo si limita a scopi didattici in virtù della sua semplicità e per introdurre i futuri programmatori al ragionamento algoritmico e alle misure di complessità.<ref>{{Cita libro|autore = Donald Knuth|titolo = The Art of Computer Programming Vol. 3|anno = 1973|editore = Addison Wesley|città = }}</ref>

Dell'algoritmo esistono numerose [[#Varianti e ottimizzazioni|varianti]], per esempio lo [[shaker sort]].

== Spiegazione astratta ==

[[File:Bubble-sort-example-300px.gif|upright=1.6|thumb|Esempio di ''bubble sort'' che ordina gli elementi in senso crescente. Partendo dall'inizio della lista e scorrendola progressivamente, si confrontano due elementi adiacenti e si scambiano le loro posizioni se non sono nel giusto ordine (ossia se il secondo elemento è minore del primo). Dopo la prima [[iterazione]] il massimo si troverà in ultima posizione, quella sua definitiva; dopo la seconda iterazione il secondo massimo si troverà in penultima posizione, anch'essa la sua definitiva; dopo la terza iterazione il terzo massimo si troverà in terz'ultima posizione, anch'essa la sua definitiva e così via. Ad ogni iterazione almeno un elemento si va a collocare nella sua giusta posizione: la procedura termina quando non ci sono più elementi da scambiare. Si noti infine come, per esempio, l'8 sia un ''coniglio'' che si muove velocemente verso destra, mentre il 2 sia una ''tartaruga'' che si muove lentamente verso sinistra.]]

Il bubble sort è un [[algoritmo iterativo]], ossia basato sulla ripetizione di un procedimento fondamentale. La singola iterazione dell'algoritmo prevede che gli elementi dell'array siano confrontati a due a due, procedendo in un verso stabilito (che si scorra l'array a partire dall'inizio in avanti, o a partire dal fondo all'indietro, è irrilevante; d'ora in poi ipotizzeremo che lo si scorra partendo dall'inizio).

Per esempio, saranno confrontati il primo e il secondo elemento, poi il secondo e il terzo, poi il terzo e il quarto e così via fino al confronto fra il penultimo e l'ultimo elemento. Ad ogni confronto, se i due elementi confrontati non sono ordinati secondo il criterio prescelto, vengono scambiati di posizione. Durante ogni iterazione almeno un valore viene spostato rapidamente fino a raggiungere la sua collocazione definitiva; in particolare, alla prima iterazione il numero più grande raggiunge l'ultima posizione dell'array, alla seconda il secondo numero più grande raggiunge la penultima posizione e così via.

Il motivo è semplice e si può illustrare con un esempio. Si supponga che l'array sia inizialmente disposto come segue:

15 6 4 10 11 2

Riga 10 ⟶ 45:

6 15 4 10 11 2

A questo punto il 15 viene confrontato col 4, e nuovamente scambiato:

Riga 18 ⟶ 53:

# se i numeri sono in tutto N, dopo N-1 iterazioni si avrà la garanzia che l'array sia ordinato;

# alla all'iterazione i-esima, le ultime i-1 celle dell'array ospitano i loro valori definitivi, per cui la sequenza di confronti può essere terminata col confronto dei valori alle posizioni N-+1-i e N-i.

Ovviamente, a ogni iterazione può accadere che più numeri vengano spostati; per cui, oltre a portare il numero più grande in fondo all'array, ogni singola iterazione può contribuire anche a un riordinamento parziale degli altri valori. Anche per questo motivo, può accadere (e normalmente accade) che l'array risulti effettivamente ordinato ''prima'' che si sia raggiunta la N-1esima1ª iterazione. Su questa osservazione sono basate alcunele versioni ottimizzazioniottimizzate dell'algoritmo.

=== Analisi dell'algoritmo ===

===Varianti e ottimizzazioni===

Il bubble sort effettua all'incirca <math>\frac{N^2}{2}</math> confronti ed <math>\frac{N^2}{2}</math> scambi sia in media che nel caso peggiore.

Il tempo di esecuzione dell'algoritmo è <math>\Theta(n^2)</math>.

=== Varianti e ottimizzazioni ===

Esistono numerose varianti del bubblesort, molte delle quali possono essere definite ''ottimizzazioni'' nel senso che mirano a ottenere lo stesso risultato finale (l'ordinamento dell'array) eseguendo, in media, meno operazioni.

Esistono numerose varianti del bubble sort, molte delle quali possono essere definite ottimizzazioni, in quanto mirano a ottenere lo stesso risultato finale (l'ordinamento dell'array) eseguendo, in media, meno operazioni, quindi impiegando meno tempo e meno risorse computazionali.

Un insieme di ottimizzazioni sonosi basatebasa sull'osservazione che, se, in una data iterazione, non avviene alcuno scambio, allorasignifica che l'array è necessariamentesicuramente ordinato, equindi l'algoritmo può essere terminato anticipatamente (ovvero senza giungere alla N-1esima1ª iterazione). Una tecnica di ottimizzazione può dunque essere applicata usando una variabile [[logica booleana|booleana]] (o equivalente) usata come "''[[tecnica del flag|flag]]''" che indicatiene traccia se lnell'iterazione corrente hasi è eseguito prodottoalmeno uno scambio. La variabile viene reimpostataimpostata a ''false'' all'inizio di ogni iterazione, e impostatamodificata a ''true'' solo nel caso in cui si proceda a uno scambio. Se al termine di una un'iterazione completa il valore della variabile ''flag'' è rimasto ''false'', ovvero nell'iterazione non sono stati eseguiti scambi, l'array è ordinato e l'intero algoritmo viene terminato. Questa tecnica produce una riduzione del tempo ''medio'' di esecuzione dell'algoritmo, pur con un certo [[overhead]] costante (dato dall'assegnamento e dal confronto della variabile ''flag'').

Una seconda linea di ottimizzazione (che può essere combinata con la prima) è basata sull'osservazione che (sempre assumendo una scansione dell'array, per esempio, in avanti, e ordinamento crescente) se una data iterazione non sposta nessun elemento di posizione maggiore di un dato valore ''i'', allora si può facilmente dimostrare che nessuna nessun'iterazione successiva eseguirà alcuno scambioscambi in posizioni successive a tale valore ''i''. L'algoritmo può dunque essere ottimizzato memorizzando l'indicela posizione a cui avviene l'ultimo scambio durante una un'iterazione, e limitando le iterazioni successive alla scansionescansioni dell'array durante le iterazioni successive solo fino a tale posizione. Anche questa tecnica evidentemente introduce un piccolo ''overhead'', dato dalla (gestione delladi una variabile aggiuntiva che indica la posizione dialla ultimaquale modifica).la Questascansione tecnicadella silista puòdeve combinarefermarsi proficuamentedi convolta quella presentata nel precedentein paragrafovolta.

Un'altra variante già menzionata, (lo ''shakersortshaker sort''), consente di ridurre la probabilità che si verifichi la situazione di [[analisi del caso peggiore|caso peggiore]], (in cui tutte le ottimizzazioni precedentemente citate falliscono e quindi contribuiscono solo negativamente con i relativi ''overhead''); vedi [[shakersortShaker sort|la voce relativa]].

=== Conigli e tartarughe ===

==Implementazioni==

Come detto, la struttura dell'algoritmo porta ad avere elementi che si spostano verso la posizione corretta più velocemente di altri. Tutti gli elementi che si spostano nella stessa direzione di scorrimento dell'indice avanzano più velocemente di quelli che lo fanno in senso contrario. Si riprende l'esempio precedente. Data la lista

15 6 4 10 11 2

Seguono alcune implementazioni in vari [[Linguaggio di programmazione|linguaggi]]. Le implementazioni nei diversi linguaggi non si riferiscono necessariamente alla stessa variante dell'algoritmo.

dopo la prima iterazione la disposizione dei numeri sarà:

Altre implementazioni si trovano [http://wikisource.org/wiki/bubble_sort qui] su [[wikisource]]

6 4 10 11 2 15

=== [[linguaggio C|C]] ===

Qui si osserva il "coniglio" 15 e la "tartaruga" 2: il primo numero, in una sola iterazione, ha attraversato tutta la lista, posizionandosi nella sua collocazione definitiva. Il secondo, invece, durante la stessa iterazione è avanzato di una sola posizione verso la sua collocazione corretta.

void BubbleSort(int* array, int elemN)

{

register int i,tmp, ultimo;

register int alto=elemN-1; /* indica la parte di array ancora da ordinare */

while (alto >= 0){

ultimo = -1;

for (i=0; i<alto; i++)

if (array[i]>array[i+1]) { /* scambiate il '>' con '<' se volete un ordinamento decrescente */

tmp = array[i];

array[i] = array[i+1];

array[i+1] = tmp;

ultimo = i;

}

alto = ultimo;

}

}

Sono stati effettuati diversi tentativi per eliminare le tartarughe e aumentare l'efficienza del Bubble sort: l'algoritmo [[shaker sort]] risolve molto bene questo problema, utilizzando un indice interno la cui direzione di scorrimento è invertita a ogni passaggio; risulta più efficiente del Bubble sort, ma paga un dazio in termini di complessità (<math>O(n^2)</math>). Il [[Comb sort]] compara elementi divisi da una grossa separazione, potendo quindi spostare le tartarughe molto velocemente prima di procedere a controlli fra elementi via via sempre più vicini per rifinire l'ordine della lista (la sua velocità media è comparabile a quella di algoritmi molto più veloci quali il [[quicksort]]).

''Due note di carattere tecnico:''

alcune variabili sono dichiarate come ''register'', il chè significa che, se possibile, il [[compilatore]] C farà in modo che vengano collocate nei [[registro|registri]] della [[CPU]]; questo renderà più rapido l'accesso a dette variabili.

== Pseudocodice ==

''tmp'' è dichiarata di tipo ''int'', quindi dovrà contenere interi; se l'array contiene elementi di tipo diverso, sarà sufficiente modificare la sua dichiarazione.

Di seguito viene riportato uno [[pseudocodice]] base relativo alla versione originale dell'algoritmo:

'''procedure''' BubbleSort(A''':'''lista degli elementi da ordinare)

=== [[C plus plus|C++]] ===

scambio ← true

'''while''' scambio '''do'''

scambio ← false

'''for''' i ← 0 '''to''' length(A)-1 ''' do'''

'''if''' A[i] > A[i+1] '''then'''

swap( A[i], A[i+1] )

scambio ← true

Lo pseudocodice appena scritto sposta, ad ogni ciclo while, l'elemento più grande all'estrema destra.

#include <algorithm>

template <typename container> void bubbleSort(container &array)

{

container::reverse_iterator i;

container::iterator j;

for(i = array.rbegin(); i != array.rend(); ++i)

for(j = array.begin(); j != i ; ++j)

if((*j) > *(j+1) /* compara gli elementi vicini */

std::swap(*j, *(j+1));

}

template<typename T> void bubble_sort(T *base, size_t n) {

T *p, *q, t;

while (n--) {

for (q = (p = base) + 1; p < base + n; ++q, ++p) {

(*p > *q) && (t = *p, *p = *q, *q = t);

}

}

}

=== [[Linguaggio di programmazione Java|Java]] ===

Una versione alternativa potrebbe essere la seguente:

public void bubbleSort(int[] array)

'''procedure''' BubbleSort(A''':'''lista degli elementi da ordinare)

{

'''for''' i ← 0 '''to''' length(A)-2 ''' do'''

int temp = 0;

'''for(''' j=0;j<array. ← i+1 '''to''' length;j++(A){-1 ''' do'''

'''if''' A[j] < A[i] '''then'''

for(i=j;i<array.length;i++){

if swap(x A[j]>x, A[i] ){

temp=x[j];

x[j]=x[i];

x[i]=temp; //swap boubble sort

}

}

}

}

Questa versione, invece, sposta, ad ogni ciclo for esterno, l'elemento più piccolo all'estrema sinistra.

===[[BASIC]]===

=== Ottimizzazioni ===

Sub Bubblesort(Array() as Integer, Length as Integer)

Le prestazioni del bubble sort possono essere leggermente migliorate tenendo conto del fatto che dopo la prima iterazione l'elemento più grande si troverà certamente nell'ultima posizione della lista, quella sua definitiva; alla seconda iterazione il secondo più grande si troverà in penultima posizione, quella sua definitiva, e così via. Ad ogni iterazione il ciclo dei confronti può accorciarsi di un passo rispetto al precedente, evitando di scorrere ogni volta tutta la lista fino in fondo: all'n-esima iterazione si può quindi fare a meno di trattare gli ultimi n-1 elementi che ormai si trovano nella loro posizione definitiva. Si può rappresentare quanto detto con questo secondo pseudocodice:

Dim I as Integer

Dim J as Integer

Dim Temp as Integer

For I = Length -1 To 1 Step -1

For J = 0 to I - 1

IF Array(J)>Array(J+1) THEN ' cofronta gli elementi vicini

Temp = Array(j)

Array(J) = Array(J+1)

Array(J+1) = Temp

End If

Next J

Next I

End Sub

'''procedure''' BubbleSort(A:lista di elementi da ordinare)

===[[Perl]]===

scambio ← true

n ← length'''(A)''' - 2 //poiché l'indice parte da 0 e devo fermarmi al penultimo elemento del vettore devo togliere 2

'''while''' (scambio) '''do'''

scambio ← false

'''for''' i ← 0 '''to''' n '''do'''

'''if''' (A[i] > A[i + 1]) '''then''' //sostituire '>' con '<' per ottenere un ordinamento decrescente

swap ( A[i], A[i+1] )

scambio ← true

n ← n-1 //ad ogni passaggio il ciclo for si accorcia di un'iterazione

Un altro tipo di ottimizzazione deriva dall'osservazione che spesso, alla fine di un'iterazione, non uno bensì due o più elementi si trovano nella loro posizione definitiva: tutti gli elementi che si trovano a valle dell'ultimo scambio effettuato risultano ordinati e si può evitare di trattarli ancora nell'iterazione successiva.

sub bubble_sort(@) {

my @a = @_;

foreach $i (reverse 0..$#a) {

foreach $j (0..$i-1) {

($a[$j],$a[$j+1]) = ($a[$j+1],$a[$j]) if ($a[$j] > $a[$j+1]);

}

}

return @a;

}

Si può rappresentare quanto detto con questo terzo pseudocodice:

===[[Python]]===

'''procedure''' BubbleSort(A:lista di elementi da ordinare)

def bubblesort(iterable):

n ← length'''(A)''' - 1

seq = list(iterable)

ultimoScambiato ← n

for passesLeft in range(len(seq)-1, 0, -1):

'''while''' (ultimoScambiato > 0) '''do'''

for index in range(passesLeft):

ultimoScambiato ← 0

if seq[index] > seq[index + 1]:

'''for''' i ← 0 '''to''' n '''do'''

seq[index], seq[index + 1] = seq[index + 1], seq[index]

'''if''' (A[i] > A[i + 1]) '''then''' //sostituire '>' con '<' per ottenere un ordinamento decrescente

return seq

swap ( A[i], A[i+1] )

ultimoScambiato ← i

n ← ultimoScambiato //ad ogni passaggio si accorcia il ciclo for fermandosi in corrispondenza dell'ultimo scambio effettuato

Il terzo pseudocodice accorcia ulteriormente, se possibile, il ciclo di for: mentre nello pseudocodice base ad ogni passaggio il ciclo si ripete sempre n-1 volte e nel secondo pseudocodice esso si accorcia progressivamente di un'unità, nel terzo pseudocodice l'accorciamento può essere ancora più marcato dipendendo dal punto in cui si è verificato l'ultimo scambio.

===[[Fortran]]===

== Note ==

SUBROUTINE Bubble (X,N)

<references/>

! X e' l'array da ordinare, di dimensione N

IMPLICIT NONE

INTEGER :: N, J, I, JMAX, TEMP

INTEGER :: X(N)

JMAX=N-1

spike1: DO I=1,N-1

spike2: DO J=1,JMAX

IF(X(J).GT.X(J+1)) GO TO 100

TEMP=X(J)

X(J)=X(J+1)

X(J+1)=TEMP

100 END DO spike2

JMAX=JMAX-1

END DO spike1

RETURN

END

== Voci correlate ==

===[[Lisp]]===

* [[Algoritmo di ordinamento]]

* [[Shaker sort]]

* [[Stupid sort]]

== Altri progetti ==

(DEFUN bubble-sort (X)

{{interprogetto|b=Implementazioni di algoritmi/Bubble sort|b_oggetto=implementazioni|b_preposizione=del|preposizione=sul}}

(LET ((Bubble (bubble X)))

(IF (EQUAL X Bubble) X (bubble-sort Bubble))))

(DEFUN bubble (X)

(COND ((NULL X) X)

((= (LENGTH X) 1) X)

((LISTP X)

(IF (> (CADR X) (CAR X))

(CONS (CADR X)

(bubble (CONS (CAR X) (CDR X))))

(CONS (CAR X) (bubble (CDR X)))))

(T (ERROR "bubble expects a list"))))

== Collegamenti esterni ==

===[[AppleScript]]===

* {{FOLDOC|2=bubble sort}}

* {{en}} [http://corte.si/posts/code/visualisingsorting/index.html Visualising Sorting Algorithms] - Visualizzazione grafica di alcuni algoritmi di ordinamento

* {{en}} [http://www.sorting-algorithms.com Sorting Algorithm Animations] - Animazione grafica di alcuni algoritmi di ordinamento

{{Ordinamento}}

-- Nota: AppleScript è 1-based, cioè il primo elemento di una lista è 1

{{Portale|informatica}}

--

on bubblesort( array )

repeat with i from length of array to 2 by -1 --> va indietro

repeat with j from 1 to i - 1 --> va avanti

tell array

if item j > item ( j + 1 ) then

set { item j, item ( j + 1 ) } to { item ( j + 1 ), item j } -- swap

end if

end tell

end repeat

end repeat

end bubblesort

[[Categoria:Algoritmi di ordinamento]]

[[de:Bubblesort]]

[[en:Bubble sort]]

[[es:Ordenamiento de burbuja]]

[[fi:Kuplalajittelu]]

[[fr:Tri à bulles]]

[[he:מיון בועות]]

[[is:Bóluröðun]]

[[ja:バブルソート]]

[[lt:Burbulo rūšiavimo algoritmas]]

[[nl:Bubblesort]]

[[pl:Sortowanie bąbelkowe]]

[[pt:Bubble sort]]

[[ru:Сортировка пузырьком]]

[[sv:Bubble sort]]

[[zh:冒泡排序]]