Implementazioni di algoritmi/Bubble sort
Il bubble sort o bubblesort (letteralmente: ordinamento a bolle) è un semplice algoritmo di ordinamento per ordinare array. Non è un algoritmo efficiente: ha una complessità computazionale (misurata in termini di numero di confronti) O(n²); si usa solamente a scopo didattico in virtù della sua semplicità, e per introdurre i futuri programmatori al ragionamento algoritmico e alle misure di complessità. Dell'algoritmo esistono numerose varianti, 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 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).
Analisi dell'algoritmo
[modifica | modifica sorgente]Il bubble sort effettua all'incirca confronti ed scambi sia in media che nel caso peggiore. Il tempo di esecuzione dell'algoritmo è Θ(n2).
Implementazioni
[modifica | modifica sorgente]Seguono alcune implementazioni in vari linguaggi. Le implementazioni nei diversi linguaggi non si riferiscono necessariamente alla stessa variante dell'algoritmo.
#include <stdlib.h>
#include <stdio.h>
int main(){
int array[100]; //Poniamo il caso "array" contenga 100 numeri in ordine sparso
int n1=0; //Contatore 1
int n2=0; //Contatore 2
int temp=0; //Variabile di supporto
for(n1=0; n1<100; n1++){
for(n2=0; n2<100-n1-1; n2++){
if(array[n2]>array[n2+1]){ //Scambio valori
temp=array[n2];
array[n2]=array[n2+1];
array[n2+1] = temp;
}
}
}
}
// elemN è il numero degli elementi del vettore da ordinare
void BubbleSort(int *array, int elemN){
int alto;
for (alto = elemN - 1; alto > 0; alto--)
for (int i=0; i<alto; i++)
if (array[i] > array[i+1]){ /* sostituire ">" con "<" per avere un ordinamento decrescente */
int tmp = array[i];
array[i] = array[i+1];
array[i+1] = tmp;
}
}
tmp è dichiarata di tipo int, quindi dovrà contenere interi; se l'array contiene elementi di tipo diverso, sarà sufficiente modificare la sua dichiarazione.
public void bubbleSort(int[] array) {
int temp;
int upperBound = array.length - 1;
while (upperBound > 0) {
for (int i = 0; i < upperBound; i++) {
if (array[i] > array[i + 1]){ //scambiare il '>' con '<' per ottenere un ordinamento decrescente
temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
upperBound--;
}
}
Implementazione dell'algoritmo che presenta le ottimizzazioni enunciate alla voce Bubble sort:
void bubbleSort(int[] array) {
boolean swapped = true;
int upperBound = array.length - 1;
int lastSwapIndex = 0;
int temp;
while (swapped && upperBound > 0) {
swapped = false;
for (int i = 0; i < upperBound; i++) {
if (array[i] > array[i + 1]) { //scambiare il '>' con '<' per ottenere un ordinamento decrescente
temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
swapped = true;
lastSwapIndex = i;
}
}
upperBound = lastSwapIndex;
}
}
Algoritmo implementato sui vector, in questo esempio, di oggetti di tipo String:
public void bubbleSort(Vector v)
{
String first;
String next;
int i = v.size();
while(i>0)
{
for(int j=0; j < i; j++)
{
first = (String) v.elementAt(j);
next = (String) v.elementAt(j+1);
if(first.compareTo(next)>0) /*scambiare il '<' con '>' per ottenere un ordinamento decrescente*/
exchange(v,j,j+1);
}
i--;
}
}
public static void exchange(Vector v, int i, int j)
{
Object obk = v.elementAt(i);
v.setElementAt(v.elementAt(j),i);
v.setElementAt(obk,j);
}
Segue una documentata implementazione Java dell'algoritmo di sort a bolle,
pensata da uno studente del dipartimento di informatica (ITPS) di Bari:
/**
* Questo algoritmo di sort a bolle, si basa sul
* confronto, passo dopo passo, dell'elemento corrente (dell' indice)
* con quello precedente (confronto tra coppie adiacenti).
* Se quello precedente e' maggiore di quello corrente
* viene effettuato lo scambio.
*
* Descrizione dettagliata:
* La variabile passo corrisponde al passo corrente, ovvero al numero
* di elementi gia' ordinati.
* Se nel passo sono stati effettuati scambi (lo sappiamo grazie alla
* variabile booleana scambio) allora significa che l'array non e' ancora
* ordinato e quindi bisogna continuare con il prossimo passo.
* Se, invece, in un intero passo non sono stati effettuati scambi (nel
* ciclo interno do-while) allora l'array e' ordinato e quindi si puo'
* uscire dall' intero algoritmo.
* Cosi' facendo si riesce a far risalire a galla ordinatamente le
* stringhe più' piccole fra quelle in esame.
* Ho pensato ad un ciclo do-while e non un while, perché
* altrimenti l'ultimo elemento (quello la cui posizione e' maggiore
* del passo) non verrebbe ordinato.
* Nel caso peggiore si esce dall'algoritmo solo quando il passo supera
* la posizione dell'ultimo elemento dell'array, e questo si verifica
* ad esempio quando gli elementi da ordinare sono in un ordine inverso.
* L'ordine di complessita' e' quadratico [MAX (n)*(n-1)/2 ],
* ma l'algoritmo, grazie alla variabile sentinella scambio,
* risulta ottimizzato.
*/
public void sort() {
String temp = "";
String[] strings = {"ciao", "come", "stai"};
int indice = 0;
//variabile sentinella di scambio.
boolean scambio = true;
if (strings.length > 1) {
//Il ciclo esterno si occupa di incrementare il passo se, e solo se,
//il passo corrente e' minore del numero di stringhe presenti nell'
//array e se sono stati effettuati scambi nel passo precedete.
for (int passo = 0; passo <= (strings.length - 1)
&& (scambio); passo++) {
//impostiamo indice all'ultimo elemento presente nell'array.
indice = strings.length - 1;
scambio = false;
do {
if (strings[indice].compareToIgnoreCase(
strings[indice - 1]) < 0) {
temp = strings[indice];
strings[indice] = this.strings[indice - 1];
strings[indice - 1] = temp;
//Sono stati effettuati scambi,quindi scambio sara'true.
scambio = true;
}
indice--;
} while (indice > passo);
//Non e'difficile notare che mentre il passo aumenta da sinistra,
//da destra vengono man mano ordinati sempre meno elementi.
}
}
}
Sub BubbleSort(ByRef MioArray() As Integer)
For I = LBound(MioArray, 1) To UBound(MioArray, 1) -1
For J = I + 1 To UBound(MioArray, 1)
If MioArray(I) > MioArray(J) Then 'scambiare il ">" con "<" per ottenere un ordinamento saliente
SWAP MioArray(I),MioArray(J)
End If
Next J
Next I
End Sub
''MioArray'' sono dichiarati di tipo ''Integer'', quindi dovranno contenere interi; se l'array contiene elementi di tipo diverso, sarà sufficiente modificare le dichiarazioni di entrambi.
def bubble(v)
tmp=v.length
while tmp > 0
(tmp-1).times{|i|
if v[i] > v[i+1]
v[i] , v[i+1] = v[i+1] , v[i] #scambia v[i] con v[i+1] alla maniera del Ruby!
end
}
tmp-=1
end
end
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 xrange(len(seq)-1, 0, -1):
for index in xrange(passesLeft):
if seq[index] > seq[index + 1]:
seq[index], seq[index + 1] = seq[index + 1], seq[index]
return seq
SUBROUTINE Bubble (X,N)
! X e' l'array da ordinare in modo non decrescente, di estensione N
IMPLICIT NONE
INTEGER :: N, J, I, TEMP
INTEGER :: X(N)
spike1: DO I=1,N
spike2: DO J=1,N-1
IF(X(J)<X(J+1)) CYCLE
TEMP=X(J)
X(J)=X(J+1)
X(J+1)=TEMP
END DO spike2
END DO spike1
RETURN
END
! GO TO [label] è un'istruzione deprecata da FORTRAN77 e condannata dal Th. di Böhm-Jacopini.
(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) (CDDR X))))
(CONS (CAR X) (bubble (CDR X)))))
(T (ERROR "bubble expects a list"))))
on bubblesort( array )
repeat with i from 1 to length of array
repeat with j from 1 to length of array - 1
tell array
if item j > item ( j + 1 ) then
set { item j, item ( j + 1 ) } to { item ( j + 1 ), item j }
end if
end tell
end repeat
end repeat
end bubblesort
Nota: AppleScript è 1-based, cioè il primo elemento di una lista è 1
function bubbleSort ($array)
{
$alto= count ($array);
while ($alto > 1) /* in questo modo si evita 1 passaggio*/
{
for ($i = 0; $i < $alto - 1; $i++)
if ($array[$i] > $array[$i+1]) /* sostituire ">" con "<" per avere un ordinamento decrescente */
{
$tmp = $array[$i];
$array[$i] = $array[$i+1];
$array[$i+1] = $tmp;
}
$alto--;
}
}
function vettore = bubblesort(a)
for k=numel(a)-1:-1:1
for i=1:k
if(a(i+1)<a(i))
tmp=a(i);
a(i)=a(i+1);
a(i+1)=tmp;
end
vettore=a
end
end
end
Altri progetti
[modifica | modifica sorgente]
Wikipedia contiene una voce su questo algoritmo
Wikimedia Commons contiene immagini o altri file su bubble sort
