Selection sort (Ordinamento per selezione)

L’algoritmo di selection sort è uno dei metodi di ordinamento più intuitivi. Ripetutamente individua l’elemento minimo da una certa porzione dell’array e lo porta in testa a quella sezione. Dopodiché prosegue cercando il minimo nell’array rimanente, ripetendo questo processo fino a raggiungere la fine dell’array.

a = [...]
for i in range(len(a)):                  # Dovremmo posizionare il valore minimo di a[i:] in a[i]
    min_idx = i                          # Indice dell'elemento minimo
    for j in range(i + 1, len(a)):       # Trova l'indice dell'elemento minimo
        if a[j] < a[min_idx]:            # Se troviamo un elemento più piccolo
            min_idx = j                  # Aggiorna l'indice dell'elemento minimo
    a[i], a[min_idx] = a[min_idx], a[i]  # Scambia a[i] e a[min_idx]
print(a)

A ogni iterazione, prendiamo il minimo dalla parte rimanente dell’array e scambiamo l’elemento corrente con quello minimo usando i loro indici. Nel caso in cui l’elemento corrente sia già il minimo, non succede nulla poiché si scambierebbe con se stesso, senza modificare l’array.

L’algoritmo di selection sort individua il minimo in ogni porzione dell’array e scambia l’indice corrente con quell’elemento minimo. Ciò implica che a ogni iterazione percorriamo l’intera parte rimanente dell’array per cercare il minimo (la funzione min va uno per uno sui valori rimanenti per trovare il più piccolo). Di conseguenza, il tempo di esecuzione complessivo è dato da n iterazioni che eseguono circa n passaggi ⇒ operazioni in totale.

Simuliamo l’algoritmo su alcuni array di esempio:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[1, 2, 3, 4, 5]

i = 0 ⇒ val = 1 ⇒ idx = 0 ⇒ swap ⇒ [1, 2, 3, 4, 5]

i = 1 ⇒ val = 2 ⇒ idx = 1 ⇒ swap ⇒ [1, 2, 3, 4, 5]

i = 2 ⇒ val = 3 ⇒ idx = 2 ⇒ swap ⇒ [1, 2, 3, 4, 5]

i = 3 ⇒ val = 4 ⇒ idx = 3 ⇒ swap ⇒ [1, 2, 3, 4, 5]

i = 4 ⇒ val = 5 ⇒ idx = 4 ⇒ swap ⇒ [1, 2, 3, 4, 5]

Challenge

Data una lista di n interi, ordinarli in ordine crescente usando il selection sort.

Input

La prima riga dell’input contiene un unico intero n (1 ≤ n ≤ 1000), il numero di elementi dell’array.

La riga successiva contiene n interi separati da spazi ( ≤ ≤ ).

Output

Il programma deve stampare l’array di input ordinato in ordine crescente.

Esempi

Ingresso	Uscita
5 5 5 3 2 3	2 3 3 5 5

Challenge

Input

Output

Esempi

Constraints

To check your solution you need to sign in

Sign in to continue