Sviluppiamo l’algoritmo Merge Sort in Python, uno dei più famosi algoritmi di ordinamento che sfrutta il metodo divide et impera, così come il Quick Sort.
Innantitutto spieghiamo il funzionamento di questo algoritmo.
Dapprima suddiviamo la lista in due sottoliste e poi a mano a mano in parti ancora più piccole. Poi utilizziamo una funzione ricorsiva su ciascuna sottolista ed infine combiniamo il risultato in modo da ottenere la soluzione all’algoritmo di ordinamento.
Merge Sort Python – solution
Supponiamo di avere una lista di numeri interi:
numbers = [6,12,4,3,7,8]
Indichiamo l’indice che punta al numero 6 con p e l’indice che punta al numero 8 con r.
numbers = [p, …, …, r]
Come primo passo, dunque, dividiamo la lista a metà utilizzando un altro indice, ad esempio q:
quindi avremo numbers_1 = [p,…,…,q] e numbers_2 = [q+1,…,…,r]
Si continua a dividere finchè non può essere più diviso. Questa condizione si verifica quando l’array è vuoto oppure è rimasto solo un elemento (ovvero 0 elementi oppure 1).
Su ciascuna delle due metà, poi, si invoca la funzione di ordinamento ricorsiva. Infine si combina tutto.
Nel nostro esempio si ha:
numbers = [6,12,4,3,7,8]
da cui ne deriva: numbers_1 = [6,12,4,] e numbers_2 = [3,7,8] e così via.
Ecco, dunque, una rappresentazione grafica di quello che succede:
Adesso che tutti gli elementi sono divisi, utilizziamo una lista di appoggio ed iniziamo l’ordinamento.
La seconda parte dell’algoritmo di Merge Sort, dunque, riguarda l’ordinamento effettivo degli elementi in un ordine che può essere crescente o decrescente.
Scegliamo un ordinamento crescente. Ordiniamo e poi combiniamo ciascuna parte delle sottoliste.
Merge Sort Python – code
Ecco dunque una possibile soluzione all’algoritmo:
def merge_sort(list):
list_length = len(list)
if list_length == 1:
return list
q = list_length // 2 #calcoliamo il punto centrale
left = merge_sort(list[:q]) #lista di sinistra da 0 a q
right = merge_sort(list[q:]) #lista di destra da q alla fine
return merge(left, right)
def merge(left, right):
ordered = []
while left and right:
ordered.append((left if left[0] <= right[0] else right).pop(0))
return ordered + left + right
numbers = [10,5,12,1,9]
print(numbers)
sorted_list = merge_sort(numbers)
print(sorted_list)
Provate il codice nel compilatore sotto:
Chiaramente quella proposta è una possibile soluzione all'algoritmo Merge Sort in Python, implementate pure la vostra e scrivetela nei commenti sotto.
Implementiamo l’algoritmo quicksort in Python, noto anche come l’algoritmo di ordinamento che è basato sull’approccio divide et impera!
Il suo funzionamento è basato sul pivot, ovvero un elemento che può essere selezionato in vari modi. Nel corso della presente guida studieremo i vari modi. Infatti, ad esempio, il pivot può essere il primo elemento, oppure l’ultimo o ancora l’elemento di mezzo ed infine può anche essere un elemento scelto a caso.
Il ragionamento che sta alla base di questo algoritmo è la partizione, ovvero la suddivisione di un array in sottoarray. Metteremo gli elementi più piccoli del pivot alla sua sinistra mentre gli elementi più grandi saranno posizionati alla sua destra.
Quicksort in Python – funzionamento
Lista di partenza:
number_list = [10,5,12,1,9,7]
I passaggi per ordinare una qualsiasi lista con il quicksort sono questi:
Divide – Dividendo la lista da ordinare scomponiamo il problema in sotto-problemi.
Impera – Si risolve l’algoritmo e si applica la ricorsione.
Combina – Si combinano gli output precedenti ottenuti dalle chiamate ricorsive.
Iniziamo con il primo passo, ovvero la partizione.
Scegliamo come pivot l’ultimo elemento: 7. Per estrarlo uso semplicemetne il metodo pop di Python, dunque avremo:
pivot = number_list.pop()
Dopo creiamo due liste vuote, low and high per contenere rispettivamente gi elemnti più piccoli e quelli più grandi del pivot.
low, high = [], []
Confrontiamo ciascun elemento con il pivot e lo inseriamo nella lista opportuna.
number_list = [10,5,12,1,9,7]
pivot = number_list.pop()
high, low = [], []
for number in number_list:
if number > pivot:
high.append(number)
else:
low.append(number)
print(number_list)
print(high)
print(low)
In questo modo la lista number_list non conterrà più l’ultimo elemento perchè è stato estratto e le due liste high e low sono popolate con gli elementi più grandi e più piccoli del pivot, rispettivamente.
L’output prodotto sarà questo:
number_list: [10, 5, 12, 1, 9] #manca l’elemento 7, ovvero il pivot high: [10, 12, 9] #tutti gli elementi maggiori di 7 low: [5, 1] #tutti gli elementi minori o uguali a 7
Come possiamo notare le due liste high e low non sono ordinate. Cosa possiamo fare?
Sicuramente possiamo applicare lo stesso metodo a queste due sotto-liste. Dunque richiamiamo la funzione in maniera ricorsica.
Ricordiamo di controllare la lunghezza della lista e fermarci quando non ha più elementi.
Scriviamo dunque tutto l’algoritmo che ci consente di risolvere l’ordinamento utilizzando il quicksort in Python.
def quick_sort(numbers):
length = len(numbers)
if length <= 1:
return numbers
pivot = numbers.pop()
high, low = [], []
for number in numbers:
if number > pivot:
high.append(number)
else:
low.append(number)
return quick_sort(low) + [pivot] + quick_sort(high)
number_list = [10,5,12,1,9,7]
print(quick_sort(number_list))
Potete provare l’algoritmo nel compiler online sotto:
La soluzione più classica dell’algoritmo quicksort è questa:
def quicksort(numbers, p, r):
"""indichiamo con:
p - l'indice della sottolista di sinistra
r - l'indice della sottolista di destra
"""
if p < r:
q = partition(numbers, p, r)
quicksort(numbers, p, q - 1)
quicksort(numbers, q + 1, r)
def partition(numbers, p, r):
pivot = numbers[r] #definiamo il pivot assegnando l'ultimo elemento
i = p - 1 #inizilizziamo l'indice dell'array di sinistra
for j in range(p, r):
if numbers[j] <= pivot:
i += 1
numbers[i], numbers[j] = numbers[j], numbers[i] #scambio i valori
numbers[i + 1], numbers[r] = numbers[r], numbers[i + 1] #scambio i valori
return i + 1
number_list = [10,5,12,1,9,7]
quicksort(number_list,0,len(number_list)-1)
print(number_list)
Chiaramente ci possono essere tante altre soluzioni sull'algoritmo quicksort in Python, provate ad implementare la vostra e lasciatela nei commenti sotto.
