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

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 che finisco 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.

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)

Merge_sort(right_list)

left = 0

right = 0

k_list = 0

while left < len(left_list) and right < len(right_list):

if

right_list[right] < left_list[left] :
    lista[k_list] = right_list[right]
    right += 1
else:
    lista[k_list] = left_list[left]
    left += 1
k_list += 1

while left < len(left_list):
    lista[k_list] = left_list[left]
    left += 1
    k_list += 1

while right < len(right_list):
    lista[k_list] = right_list[right]
    right += 1
    k_list += 1

return lista

L_merge_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(Merge_sort(L_merge_sort))

################QUICK SORT

#Il Quick sort permette di ordinare la lista adottando una continua suddivisione di quest'ultima in
#più sotto parti. Praticamente prendiamo l'ultimo numero e lo definiamo pivot e lo confronto con
#tutti gli altri numeri e dividiamo la lista in una parte che contiene i valori minori a questo ed
#un'altra che contiene quelli maggiori
# (ad esempio in 0,9,4,6,3,7,5 si prende op 5 e a sinistra

Dopo averlo fatto con la principale applichiamo lo stesso processo con le altre due 'sotto liste' e continuo ad applicare questo processo finché non sono più rimasti elementi da ordinare. Per prendere il pivot e rimuoverlo dalla lista mi servo della funzione l.pop(index), se non gli passo nessun indice mi prende automaticamente l'ultimo della lista.

def Quick_sort(lista):
    if len(lista) <= 1:
        return lista
    else:
        pivot = lista.pop()
        i_lower = []
        i_greater = []
        for i in range(len(lista)):
            if lista[i] > pivot:
                i_greater.append(lista[i])
            else:
                i_lower.append(lista[i])
        return Quick_sort(i_lower) + [pivot] + Quick_sort(i_greater)

L_quick_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(Quick_sort(L_quick_sort))

BUBBLE SORT

Il Bubble Sort considera 2 valori alla volta nella lista e li scambia se non sono ordinati; controlla prima 1,2 poi 2,3 poi 3,4 e li scambia se non sono ordinati fra di loro. Continua a ripetere...

questo processo fino a quando dopo aver fatto un iterazione completa non effettua nessuno scambio. Questa cosa la gestisco usando una variabile booleana che rimane falsa se avviene anche un solo scambio.

def Bubble_sort(lista):
    finito=False
    while not finito:
        finito = True
        for i in range(len(lista)-1):
            if lista[i] > lista[i+1]:
                finito = False
                lista[i], lista[i+1] = lista[i+1], lista[i]
    return lista

L_bubble_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(Bubble_sort(L_bubble_sort))

RICERCA BINARIA

La Ricerca binaria è un metodo che in una lista ordinata ti permette di trovare un determinato valore; Concettualmente prende una lista ordinata e considera il valore centrale; se quel valore è maggiore di quello che sto cercando comincia a controllare a sinistra del valore centrale della lista (viceversa a destra)

def binary_digit(lista, search):
    high = len(lista) - 1
    lower = 0
    while lower <= high:
        mid = (high + lower) // 2
        if lista[mid] == search:
            return mid
        elif

##################RICERCA LINEARE

La ricerca lineare consiste nel cercare un valore all'interno di una lista; in questo caso basterà semplicemente iterare all'interno di una lista e controllare se è presente il valore da considerare. Una volta trovato abbiamo terminato altrimenti restituiamo False