Selection Sort Python

Sviluppiamo il selection sort in Python, un algoritmo di ordinamento, molto simile all’Insertion Sort e che opera in place. innanzitutto ricordiamo che con il termine in place si intende che non si utilizza dello spazio di memoria extra o tutt’al più un piccolo spazio.

L’algoritmo opera per confronto tra due elementi dell’array, spostando di volta in volta l’elemento più piccolo nella posizione corretta.

Selection Sort Python – come funziona

Spieghiamo, dunque, passo passo il ragionamento che sta alla base di questo algoritmo.

Data una lista iniziale di numeri interi, innanzitutto supponiamo di voler ordinarla in ordine crescente.

Dunque, con un ciclo for si scorre la lista dalla posizione 0 alla posizione n-2, dove n è la dimensione della lista, ovvero la sua lunghezza.

for i in range(n – 1):

Si assegna ad una variabile, l’indice più piccolo, ovvero l’indice 0.

min_index = i

Dopo, si utilizza un altro ciclo for per scorrere la lista partendo questa volta dalla posizione 1 (i+1) fino ad arrivare alla posizione n-1:

for j in range(i + 1, n):

Così, l’utilizzo dei due cicli for e dei due indici diversi ci consente di poter effettuare i controlli in loco.

Quindi, si confronta ciascun elemento con il valore minimo e si effettua lo scambio se si trova un valore più piccolo:

if array[j] < array[min_index]:
min_index = j

Infine si inserisce l’elemento in posizione:

array[min_index], array[i] = (array[i], array[min_index])

Ecco, quindi, una possibile implementazione dell’algoritmo Selection Sort in Python:


def selection_sort(array):
    
    n = len(array)
    
    for i in range(n - 1):
        min_index = i
        
        for j in range(i + 1, n):
            if array[j] < array[min_index]:
                min_index = j
                
        #inseriamo il minimo nella posizione corretta
        array[min_index], array[i] = (array[i], array[min_index])
    return array
numbers = [6,12,4,3,7,8]
print(selection_sort(numbers))

Provate il codice nel compiler online di sotto, per testare il funzionamento:

Analogamente se volessimo ordinare l'array in senso decrescente:


def selection_sort(array):
    
    n = len(array)
    
    for i in range(n - 1):
        max_index = i
        
        for j in range(i + 1, n):
            if array[j] > array[max_index]:
                max_index = j
                
        array[max_index], array[i] = (array[i], array[max_index])
    return array


numbers = [6,12,4,3,7,8]
print(selection_sort(numbers))

In questa lezione abbiamo sviluppato l'algoritmo di ordinamento Selection Sort in Python, nelle prossime lezioni studieremo altri algoritmo di ordinamento.

Lezione precedente: Bubble Sort in Python

Lezione Successiva: Insertion Sort in Python