Bubble sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Etichette: Modifica da mobile Modifica da web per mobile |
|||
Riga 90:
'''while''' scambio '''do'''
scambio ← false
'''for''' i ← 0 '''to''' length(A)-
'''if''' A[i] > A[i+1] '''then'''
swap( A[i], A[i+1] )
Riga 103:
'''while''' (scambio) '''do'''
scambio ← false
'''for''' i ← 0 '''to''' n
'''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
Un altro tipo di ottimizzazione deriva dall'osservazione che spesso, alla fine di una 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.
Riga 122:
swap ( A[i], A[i+1] )
ultimoScambiato ← i
n ← ultimoScambiato //ad ogni passaggio si accorcia il ciclo
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 una unità, nel terzo pseudocodice l'accorciamento può essere ancora più marcato dipendendo dal punto in cui si è verificato l'ultimo scambio.
| |||