Uno fra gli aspetti più importanti e spesso influenti, sulle prestazioni di un sistema informatico, è la presenza di algoritmi di ordinamento.

 Vediamo nel dettaglio gli algoritmi di ordinamento basici più famosi e utilizzati in Python

Selection Sort

L'algoritmo Selection Sort, viene implementato innestando due cicli for annidati. Ogni elemento alla posizione di indice corrente, del ciclo più esterno, viene posto in una variabile "minimo". Esso verrà confrontato con i successivi elementi della lista, durante il ciclo for più interno, il quale, ogni volta che individua un valore più piccolo dell'elemento considerato, aggiorna la variabile "minimo" . Alla fine dell'iterazione vengono scambiate le posizioni dell'elemento a cui punta l'indice del primo for e del valore di minimo trovato. Può iniziare così una nuova iterazione. N.B: ad ogni scambio di posizione, significa che abbiamo individuato il primo valore di minimo della lista, il quale andrà ad occupare la sua posizione definitiva: di conseguenza il secondo for non deve verificare gli elementi già sistemati.

def selection_sort(lista):
    n = len(lista)
    for i in range(n):      # innestiamo il primo  ciclo for
        minimo = lista[i]   # il primo valore di minimo coinciderà con l'elemento in posizione i-esima, questo verrà poi confrontato 
        trovato = False                  
        
        for j in range(i+1,n):     # ciclo for per trovare il minimo corrente tra i valori successivi all'elemento in posizione i-esima  
            if lista[j] < minimo:           
                trovato = True
                minimo = lista[j]
                indice_trovato = j
        if trovato:                 # se "trovato" è True significa che abbiamo individuato un nuovo valore di minimo e dobbiamo effettuare uno scambio       
            occ = lista[i]
            lista[i] = lista[indice_trovato]
            lista[indice_trovato] = occ
            
    return lista

# Proviamo il codice!
l=[5,3,4,1,2,-1,6,-9,0]
print(selection_sort(l))           

# output:
   [-9, -1, 0, 1, 2, 3, 4, 5, 6]

Bubble Sort

Immaginiamo che ogni elemento di una data lista sia una bolla di sapone: le bolle più pesanti (i numeri più grandi) vanno verso il basso, mentre le bolle più leggere (i numeri più piccoli), salgono verso l'alto. Il Bubble Sort si basa su questa logica ed  è implementato con due cicli for annidati. Il ciclo più esterno effettua  n-1 iterazioni durante le quali il ciclo for più interno  confronta ogni elemento alla posizione j-esima con il successivo: se il primo è maggiore del secondo inverte le posizioni. Alla fine di ogni iterazione del ciclo for più interno, individueremo sempre il valore più grande che sarà collocato alla posizione definitiva.

N.B: per rendere ottimale l'algoritmo, ad ogni nuova iterazione diminuiremo il range del secondo ciclo for,  infatti non sarà necessario confrontare gli elementi che si trovano alle posizioni definitive.

def bubble_sort(lista):
    n = len(lista)
    for  i in range(n - 1):    # "ciclo for" per effettuare n-1 iterazioni

    # Innestiamo un "ciclo for" per confrontare le coppie di valori
    # N.B: poichè ad ogni iterazione, almeno un valore viene sistemato alla sua posizione definitiva, possiamo ridurre man mano il range del "ciclo"
        for j in range(n-1-i):    
            if lista[j] > lista[j+1]:
                occ = lista[j+1]     # utilizziamo la variabile "occ" per invertire le posizioni della coppia di valori confrontata
                lista[j+1] = lista[j]
                lista[j] = occ
    return lista

# Proviamo il codice!
l=[5,3,4,1,2,-1,6,-9,0]
print(bubble_sort(l))

# output:
   [-9, -1, 0, 1, 2, 3, 4, 5, 6]
   

Insertion Sort

La logica dell'algoritmo è di considerare ad ogni iterazione una sottolista ordinata di lunghezza pari all'indice del ciclo for più esterno (alla prima iterazione sarà formata da un solo elemento) e una sottolista non ordinata formata dai restanti elementi della lista. Ad ogni iterazione il primo elemento della sottolista non ordinata viene inserito nella sottolista ordinata, scalando ogni elemento maggiore di esso verso destra.

def insertion_sort(lista):
    n = len(lista)
    for i in range(1,n):       # effettua n-1 iterazioni a partire dal secondo elemento della lista
        valore = lista[i]         # salviamo il valore da inserire nella variabile "valore"
        j = i-1
        while j >= 0 and valore < lista[j]:# fin quando la condizione del while è verificata,
            lista[j+1] = lista[j]          # viene effettuato almeno un spostamento verso destra dei valori maggiori di "valore"        
            j -= 1
        lista[j+1] = valore
    return lista     

# Proviamo il codice!
l=[5,4,3,6,-9,0]  
print(insertion_sort(l))

# output:
   [-9, 0, 3, 4, 5, 6]