L'algoritmo Bubble sort va implementato secondo queste istruzioni:
Il metodo consiste nel confrontare coppie di
elementi adiacenti ed effettuare uno scambio nel caso in cui
gli elementi non siano in ordine, fino a che tutti gli elementi non
siano ordinati. Sara` tipicamente costituito da due cicli:
- Il ciclo piu` interno (indice i) si occupa di testare l'ordinamento di
due elementi consecutivi.
Ad esempio, se il primo elemento del vettore non è ordinato
rispetto al successivo, questi andranno scambiati.
Al passo seguente
confronterò il secondo elemento con il successivo, e
così via, per tutti gli elementi.
All'ultimo passo (i = N-2): considera gli elementi N-1, N-2.
Come effetto complessivo, il vettore sarà ordinato a partire
dal fondo, fino a una certa posizione corrispondente al punto in cui e`
avvenuto l'ultimo scambio.
- Il ciclo più esterno (indice j) si occupa di ripetere
l'operazione sulla parte non ordinata del vettore, fino a che tutto
il vettore non sarà stato ordinato. In sostanza, l'indice j
introdotto ora divide il vettore in 2 parti:
fino a j gli elementi sono ancora da ordinare, mentre da j in poi possiamo
essere sicuri che siano già ordinati. Il ciclo interno
dovrà quindi limitarsi a ordinare la parte restante del vettore (a ogni
ciclo "j", la parte analizzata del vettore sarà "accorciata" di una
posizione).
- (Facoltativo)
Volendo ottimizzare l'algoritmo si
può tener conto del fatto che il vettore è
già ordinato almeno fino alla posizione dell'ultimo scambio.
Quindi il ciclo esterno può essere eseguito solo fino a tale posizione.
Verificare che il
numero di iterazioni si riduce sensibilmente per un vettore del tipo "1 2
3 4 6 5 7" rispetto al caso precedente.
|