Bubble sort
Il Bubble Sort, in italiano ordinamento a bolla, è l'algoritmo più semplice per ordinare gli elementi di un array.
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.
L'algoritmo è così chiamato perché l'elemento più grande si trova in ultima posizione e quelli più piccoli salgono 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²).
Implementazioni
Seguono alcune implementazioni in vari linguaggi.
void bubble_sort(TYPE *array, int count) {
register int a, b;
int tmp;
for (a=0; a<count; a++) {
for (b=count-1; b>=a; --b) {
if (array[b-1] > array[b]) {
tmp = array[b-1];
array[b-1] = array[b];
array[b] = tmp;
}
}
}
}
Due note di carattere tecnico: a e b sono variabili dichiarate come register, il chè significa che, se possibile, il compilatore C farà in modo che vengano collocate nei registri della CPU; questo renderà più rapido l'accesso a dette variabili. tmp è dichiarata di tipo int, quindi dovrà contenere interi; se l'array contiene elementi di tipo diverso, sarà sufficiente modificare la sua dichiarazione.
#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);
}
}
}
public void bubbleSort(int [] array, int length)
{
int i, j;
for(i = length - 1; i > 0; i--)
for(j = 0; j < i; j++)
if(array[j] > array[j+1]) /* compara gli elementi vicini */
{
array[j] ^= array[j+1]; // Usa XOR per scambiare i valori più velocemente
array[j+1] ^= array[j];
array[j] ^= array[j+1];
}
}
Sub Bubblesort(Array() as Integer, Length as Integer)
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 ' compara gli elementi vicini
Temp = Array(j)
Array(J) = Array(J+1)
Array(J+1) = Temp
End If
Next J
Next I
End Sub
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;
}
def bubblesort(iterable):
seq = list(iterable)
for passesLeft in range(len(seq)-1, 0, -1):
for index in range(passesLeft):
if seq[index] > seq[index + 1]:
seq[index], seq[index + 1] = seq[index + 1], seq[index]
return seq
SUBROUTINE Bubble (X,N)
IMPLICIT NONE
INTEGER :: N, J, I, JMAX, TEMP
INTEGER :: X(N)
JMAX=N-1
ciclo1: DO I=1,N-1
ciclo2: 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 ciclo2
JMAX=JMAX-1
END DO ciclo1
RETURN
END
(DEFUN bubble-sort (X)
(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”))))
-- Nota: AppleScript è 1-based, cioè il primo elemento di una lista è 1
--
on bubblesort( array )
repeat with i from length of array to 2 by -1 --> go backwards
repeat with j from 1 to i - 1 --> go forwards
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