Bubble sort: differenze tra le versioni

Versione delle 18:22, 20 lug 2005

Versione delle 08:42, 21 lug 2005

Riga 2:

Il '''Bubble Sort''', in italiano '''ordinamento a bolla''', è un semplice [[algoritmo]] per ordinare gli elementi di un [[array]].

L'algoritmo comincia con un ciclo in cui ogni elemento, a partire dall'ultimo, è confrontato con l'elemento che lo precede; se i due elementi non si trovano nell'ordine esatto vengono scambiati. Alla fine del primo ciclo inevitabilmente l'elemento 'più leggero' come una bolla sarà risalito in prima posizione. Il secondo ciclo esegue le stesse operazioni escudendo il primo elemento e così facendo risalire il secondo elemento 'più leggero' e così si prosegue fino all'orinamento completo. Se N è la lunghezza del array, occorreranno N-1 di questi cicli.

Come funziona? Esso prevede l'uso di due indici: il primo, inizialmente, punta al primo elemento dell'array, il secondo indice punta al secondo elemento. Partendo da queste posizioni, il primo elemento viene confrontato con tutti gli elementi successivi. Ogni volta che il primo elemento risulta maggiore dell'elemento con cui viene confrontato, i due valori vengono scambiati. È chiaro che alla fine di questa serie di confronti il primo elemento risulterà il minore di tutto l'array. Poi il primo indice viene spostato alla seconda posizione e il secondo indice riparte dalla terza; di nuovo si effettuano tutti i confronti. E così via, finché il primo indice arriva al penultimo elemento dell'array.

E' anche possibile invertire l'ordine delle operazioni iniziando ad ordinare l'array a partire dall'ultimo elemento per poi risalire.

L'algoritmo è così chiamato perché l'elemento più grande si trova in ultima posizione e quelli più piccoli salgono verso l'alto come delle bolle.

Questo algoritmo è usato solo per scopi didattici o quando gli elementi da ordinare sono pochi poiché, siccome richiede una quantità di confronti troppo alta, risulta molto poco efficente (dell'ordine di ''n²'').

Riga 17 ⟶ 16:

{

register int a, b,tmp=0;

for (a=0elemN; a<elemN>0; a++--)

{

for (b=a+10; b<elemNa; b++)

{

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

{

tmp = array[ab+1];

array[ab+1] = array[b];

array[b] = tmp;

}