Metodi ordinamento, Ricerca binaria e lineare. Codice, Spiegazione e Complessità

Metodi di ordinamento

Ricerca binaria e ricerca lineare

La ricerca binaria e la ricerca lineare sono due algoritmi fondamentali per la ricerca di elementi all'interno di una lista. Entrambi questi metodi hanno una complessità che li caratterizza e li rende adatti per situazioni diverse.

Insertion sort

L'Insertion Sort ordina la lista considerando concettualmente la lista divisa in due parti: una parte dove si considerano gli elementi già ordinati e l'altra parte dove ci sono quelli ancora da ordinare. Si confronta il valore a cui siamo con il precedente e se quello che viene prima è più grande si scambia; poi si fa la stessa cosa per tutti gli n numeri precedenti a quello che consideriamo nel primo scambio (sui quali numeri è stato effettuato precedentemente lo stesso processo) per cui sono già ordinati e si scambia fino a quando non si trova un numero che è più piccolo di quello che stiamo selezionando, oppure non ne trova da confrontare e quindi è il più piccolo trovato fino a quel momento.

Definizione della funzione:

def Insertion_sort(lista):
    for i in range(1, len(lista)):
        while lista[i] < lista[i-1] and i > 0:
            lista[i], lista[i-1] = lista[i-1], lista[i]
            i -= 1
    return lista

Lista di esempio:

L_insertion_sort = [7,10,1,8,2,5,9,7,3,2,5,7,9,0,7,5,4,3,6,8,9,6,4,3,5]
print(Insertion_sort(L_insertion_sort))

Selection sort

Il Selection Sort prende il primo numero nella lista e lo controlla con tutti i numeri della lista, conservando di volta in volta il numero minore e poi lo scambia col primo numero preso in considerazione. Continua così fino alla fine della lista.

Definizione della funzione:

def Selection_sort(lista):
    for i in range(len(lista)-1):
        min = i
        for j in range(i+1, len(lista)):
            if lista[min] > lista[j]:
                min = j
        if min != i:
            lista[i], lista[min] = lista[min], lista[i]
    return lista

Lista di esempio:

L_selection_sort = [7,10,1,8,2,5,9,7,3,2,5,7,9,0,7,5,4,3,6,8,9,6,4,3,5]
print(Selection_sort(L_selection_sort))

Merge sort

Il Merge Sort divide la lista in 2 sotto-liste e poi applica nuovamente questo processo fino a quando non si formano un n numero di liste ognuna contenente un singolo elemento. Dopo averlo fatto, si cominciano a comparare le prime due liste per parte ottenute e le si mette in ordine creando un'unica lista ordinata. Poi le successive due per parte ed infine queste 2 nuove liste ordinate che si formano per parte si ordinano nuovamente con quelle precedenti fra di loro in modo da finire l'ordine di quel livello e così via finché non si ritorna nuovamente alle 2 sotto-liste iniziali dove però questa volta sono ordinate e si ha l'ultimo ordinamento direttamente nella lista iniziale.

Definizione della funzione:

def Merge_sort(lista):
    if len(lista) > 1:
        left_list = lista[:len(lista)//2]
        right_list = lista[len(lista)//2:]
        # Ricorsione
        Merge_sort(left_list)
        ...