Bubble Sort

Data una lista di n interi, vogliamo ordinarli in ordine crescente. Bubble sort è uno degli algoritmi più famosi e semplici per raggiungere questo obiettivo (ricorda però che non è veloce - la maggior parte degli algoritmi usati in produzione adotta tecniche più efficienti per ordinare una lista di numeri).

Nell’algoritmo di bubble sort, eseguiamo più passate sull’array e scambiamo tutti gli elementi adiacenti che non risultano ordinati. Quindi, se , invertiamo i due per far sì che la lista proceda in ordine crescente.

Più nello specifico, prendiamo l’array iniziale a (per esempio a è [4, 1, -1, 0, 2, 8]) e guardiamo i primi due elementi. Se non sono ordinati, li scambiamo (nel nostro caso [1, 4, -1, 0, 2, 8]). Poi passiamo alla coppia successiva. Se non sono in ordine, li scambiamo (nel nostro caso [1, -1, 4, 0, 2, 8]). Ripetiamo questo processo fino alla fine dell’array (nel nostro esempio si passa da [1, -1, 4, 0, 2, 8] a [1, -1, 0, 4, 2, 8], poi [1, -1, 0, 2, 4, 8] → non ci sono più cambiamenti → fine).

Poi il ciclo ricomincia dall’inizio. Si confronta la prima coppia e, se non è in ordine, la si scambia. Quindi si passa alla successiva e così via, fino a raggiungere la fine dell’array. Nel nostro esempio, avremo: [1, -1, 0, 2, 4, 8] → [-1, 1, 0, 2, 4, 8] → [-1, 0, 1, 2, 4, 8] → nessun cambiamento.

Questo processo viene ripetuto finché l’intera lista non risulta completamente ordinata:

a = [...]
while True:                                 # esegui finché l'array non è ordinato
    is_sorted = True                        # se modifichiamo qualcosa, impostiamo questa variabile a False
    for i in range(len(a) - 1):             # iterare da 0 ... n-2
        if a[i] > a[i + 1]:                 # se qualcosa non è in ordine
            is_sorted = False               # => l'array non era ordinato
            a[i], a[i + 1] = a[i + 1], a[i] # scambia a[i] e a[i + 1]
    
    if is_sorted:                           # termina il processo se a è ordinato
        break
print(a)

C’è un’ottimizzazione che si può fare per evitare di eseguire passi inutili:

Dopo ogni passata, gli elementi più grandi vengono portati in fondo alla lista. Quindi, dopo k iterazioni, i k elementi più alti sono sicuramente ordinati e collocati alla fine dell’array, per cui possiamo saltare quei confronti nel ciclo interno:

a = [...]
for u in range(len(a) - 1, 0, -1):          # u = limite superiore per il ciclo interno
    is_sorted = True                        # se modifichiamo qualcosa, la impostiamo a False
    for i in range(u):                      # iterare da 0 ... u-1
        if a[i] > a[i + 1]:                 # se qualcosa non è in ordine
            is_sorted = False               # => l'array non era ordinato
            a[i], a[i + 1] = a[i + 1], a[i] # scambia a[i] e a[i + 1]
    
    if is_sorted:                           # termina il processo se a è ordinato
        break
print(a)

La situazione peggiore per l’algoritmo di bubble sort è quando i numeri sono in ordine completamente discendente invece che ascendente. In quel caso, l’algoritmo esegue operazioni, che è molto rispetto ad algoritmi più rapidi che vedremo in seguito nel corso.

Facciamo ora una simulazione dell’algoritmo su alcuni array:

[4, 1, -1, 0, 2, 8]

u = 5

i = 0 ⇒ swap ⇒ [1, 4, -1, 0, 2, 8]
i = 1 ⇒ swap ⇒ [1, -1, 4, 0, 2, 8]
i = 2 ⇒ swap ⇒ [1, -1, 0, 4, 2, 8]
i = 3 ⇒ swap ⇒ [1, -1, 0, 2, 4, 8]
i = 4 ⇒ do nothing

i = 0 ⇒ swap ⇒ [1, 4, -1, 0, 2, 8]

i = 0 ⇒ swap ⇒ [-1, 1, 0, 2, 4, 8]
i = 1 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
i = 2 ⇒ do nothing
i = 3 ⇒ do nothing

i = 1 ⇒ swap ⇒ [1, -1, 4, 0, 2, 8]

i = 0 ⇒ do nothing
i = 1 ⇒ do nothing
i = 2 ⇒ do nothing
is_sorted is True ⇒ break

i = 2 ⇒ swap ⇒ [1, -1, 0, 4, 2, 8]

[10, 5, 1, -1, -2, -7]

u = 5

i = 0 ⇒ swap ⇒ [5, 10, 1, -1, -2, -7]
i = 1 ⇒ swap ⇒ [5, 1, 10, -1, -2, -7]
i = 2 ⇒ swap ⇒ [5, 1, -1, 10, -2, -7]
i = 3 ⇒ swap ⇒ [5, 1, -1, -2, 10, -7]
i = 4 ⇒ swap ⇒ [5, 1, -1, -2, -7, 10]

i = 0 ⇒ swap ⇒ [5, 10, 1, -1, -2, -7]

i = 0 ⇒ swap ⇒ [1, 5, -1, -2, -7, 10]
i = 1 ⇒ swap ⇒ [1, -1, 5, -2, -7, 10]
i = 2 ⇒ swap ⇒ [1, -1, -2, 5, -7, 10]
i = 3 ⇒ swap ⇒ [1, -1, -2, -7, 5, 10]

i = 1 ⇒ swap ⇒ [5, 1, 10, -1, -2, -7]

i = 0 ⇒ swap ⇒ [-1, 1, -2, -7, 5, 10]
i = 1 ⇒ swap ⇒ [-1, -2, 1, -7, 5, 10]
i = 2 ⇒ swap ⇒ [-1, -2, -7, 1, 5, 10]

i = 2 ⇒ swap ⇒ [5, 1, -1, 10, -2, -7]

i = 0 ⇒ swap ⇒ [-2, -1, -7, 1, 5, 10]
i = 1 ⇒ swap ⇒ [-2, -7, -1, 1, 5, 10]

i = 3 ⇒ swap ⇒ [5, 1, -1, -2, 10, -7]

i = 0 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]

i = 4 ⇒ swap ⇒ [5, 1, -1, -2, -7, 10]

[1, 2, 3, 4, 5]

u = 5

i = 0 ⇒ do nothing
i = 1 ⇒ do nothing
i = 2 ⇒ do nothing
i = 3 ⇒ do nothing
i = 4 ⇒ do nothing
is_sorted is True ⇒ break

i = 0 ⇒ do nothing

Extracurricular (interesting video)

C’è un ottimo video su YouTube realizzato da Lines That Connect che approfondisce ulteriormente il Bubble Sort e spiega l’intuizione dietro la curva che si forma quando si esegue l’algoritmo.

Challenge

n persone partecipano a una competizione. Devi disporle in ordine crescente di altezza. A ogni passo, ti è consentito chiedere a due partecipanti vicini di scambiarsi di posto. Il tempo è poco, quindi vorresti farlo nel modo più efficiente possibile.

Hai deciso di scrivere un programma che stampi gli indici dei partecipanti che dovrebbero scambiarsi. La numerazione parte da 0.

Input

La prima riga dell’input contiene un singolo intero n (1 ≤ n ≤ 1000).

La riga successiva contiene n interi separati da spazio ( ≤ ≤ ) che rappresentano le altezze dei partecipanti.

Output

Il programma deve stampare le coppie di indici dei partecipanti che devono scambiarsi di posizione. Ogni coppia va stampata su una riga separata. In caso di più soluzioni ottimali, qualsiasi configurazione è accettabile.

Esempi

Ingresso	Uscita
5 1 4 8 2 -1	2 3 3 4 1 2 2 3 1 2 0 1

Spiegazione

2 ↔ 3 ⇒ 1 4 2 8 -1

3 ↔ 4 ⇒ 1 4 2 -1 8

1 ↔ 2 ⇒ 1 2 4 -1 8

2 ↔ 3 ⇒ 1 2 -1 4 8

1 ↔ 2 ⇒ 1 -1 2 4 8

0 ↔ 1 ⇒ -1 1 2 4 8

Challenge

Input

Output

Esempi

Spiegazione

Constraints

To check your solution you need to sign in

Sign in to continue