7-Algoritmi di Ordinamento: Gli algoritmi di ordinamento (come QuickSort, MergeSort) mettono in ordine una sequenza di dati, mentre gli algoritmi di ricerca (come la ricerca binaria) trovano un elemento specifico all'interno di una sequenza.
Algoritmi di ordinamento: Questi algoritmi sono progettati per organizzare una sequenza (o un array) di elementi in un ordine specifico, come crescente o decrescente, in base al valore di tali elementi. Alcuni esempi di algoritmi di ordinamento includono:
7.1-QuickSort: Un algoritmo di ordinamento basato sulla tecnica di "divide et impera" che suddivide ricorsivamente l'array in sottoarray più piccoli, ordinandoli rispetto a un elemento pivot scelto, finché l'intero array non è ordinato.
Ecco un esempio di implementazione del QuickSort in Python:
python
Copy code
def quicksort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
less_than_pivot = [x for x in arr[1:] if x <= pivot]
greater_than_pivot = [x for x in arr[1:] if x > pivot]
return quicksort(less_than_pivot) + [pivot] + quicksort(greater_than_pivot)
# Esempio di utilizzo:
array = [12, 4, 5, 6, 7, 3, 1, 15]
sorted_array = quicksort(array)
print(sorted_array)
Spiegazione dell'algoritmo:
La funzione quicksort prende in input un array arr.
Se la lunghezza dell'array è minore o uguale a 1, viene restituito l'array stesso (poiché un array con zero o un solo elemento è già ordinato).
Altrimenti, viene scelto un elemento pivot, comunemente il primo elemento dell'array (in questo caso pivot = arr[0]).
Vengono creati due sottoarray: less_than_pivot, contenente gli elementi minori o uguali al pivot, e greater_than_pivot, contenente gli elementi maggiori del pivot.
Ricorsivamente, i sottoarray less_than_pivot e greater_than_pivot vengono ordinati utilizzando lo stesso algoritmo quicksort.
Infine, si combinano i sottoarray ordinati (less_than_pivot, pivot, greater_than_pivot) per ottenere l'array completamente ordinato.
Questo esempio illustra una versione semplificata del QuickSort in Python. È importante notare che, sebbene il QuickSort sia un algoritmo di ordinamento efficiente nella pratica, può richiedere molta memoria in certi casi e inoltre il suo caso peggiore può avere una complessità temporale
O(n^2), se il pivot scelto in modo non ottimale porta a una divisione sbilanciata degli array. Tuttavia, nella maggior parte dei casi, il QuickSort è molto efficiente e viene utilizzato ampiamente in molte librerie e linguaggi di programmazione.
7.2-MergeSort: Un altro algoritmo di ordinamento basato sulla tecnica di "divide et impera", che suddivide l'array in sottoarray più piccoli fino a ottenere singoli elementi, quindi li ricombina in modo ordinato.
Ecco un esempio di implementazione del MergeSort in Python:
python
Copy code
def merge_sort(arr):
if len(arr) > 1:
middle = len(arr) // 2
left_half = arr[:middle]
right_half = arr[middle:]
merge_sort(left_half)
merge_sort(right_half)
i = j = k = 0
# Fase di merge
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
# Esempio di utilizzo:
array = [12, 4, 5, 6, 7, 3, 1, 15]
merge_sort(array)
print(array)
Spiegazione dell'algoritmo:
La funzione merge_sort prende in input un array arr.
Se la lunghezza dell'array è maggiore di 1, l'algoritmo procede.
Divide ricorsivamente l'array a metà, creando due sottoarray: left_half e right_half.
Applica ricorsivamente il MergeSort ai sottoarray left_half e right_half.
Successivamente, combina i due sottoarray ordinati in un unico array ordinato nella fase di merge.
La fase di merge avviene confrontando gli elementi di left_half e right_half e inserendoli nell'array originale arr in ordine crescente.
Infine, restituisce l'array ordinato.
Il MergeSort utilizza la tecnica "divide et impera" dividendo l'array a ogni passo fino a ottenere singoli elementi, e poi combina ricorsivamente e ordina i sottoarray. Questa caratteristica lo rende uno degli algoritmi di ordinamento più efficienti, poiché ha una complessità temporale di
O(nlogn) nel caso peggiore, rendendolo molto efficace anche per grandi quantità di dati.
Nessun commento:
Posta un commento