Seguici su Telegram, ne vale la pena ❤️ ➡ @trovalost
Vai al contenuto

Guida pratica al merge sort (con esempi pratici)

Il merge sort è un algoritmo di ordinamento efficiente che utilizza un approccio “divide et impera“. Divide ricorsivamente l’array da ordinare in sottoarray più piccoli, ordina questi sottoarray e infine combina (fonde) i risultati ordinati per ottenere l’array completamente ordinato.

La sua complessità temporale è O(n log n), rendendolo ideale per ordinare grandi quantità di dati.

Storia dell’algoritmo


Cerchi un hosting economico per il tuo sito o blog? Tophost ti aspetta (clicca qui)

Il merge sort è stato ideato da John von Neumann negli anni ’40. Tuttavia, il concetto di merge sort è stato formalizzato e pubblicato per la prima volta da John von Neumann e da un collega, Herman Goldstine, nel 1945 nel documento intitolato “Planning and Coding of Problems for an Electronic Computing Instrument”.

Perchè è utile

Questo algoritmo di ordinamento è noto per la sua efficienza e per il suo approccio divide et impera, che lo rende una delle scelte popolari per l’ordinamento di grandi quantità di dati.

Implementazione in Python dell’algoritmo merge sort

# Python program for implementation of MergeSort


def mergeSort(arr):
	if len(arr) > 1:

		# Finding the mid of the array
		mid = len(arr)//2

		# Dividing the array elements
		L = arr[:mid]

		# Into 2 halves
		R = arr[mid:]

		# Sorting the first half
		mergeSort(L)

		# Sorting the second half
		mergeSort(R)

		i = j = k = 0

		# Copy data to temp arrays L[] and R[]
		while i < len(L) and j < len(R):
			if L[i] <= R[j]:
				arr[k] = L[i]
				i += 1
			else:
				arr[k] = R[j]
				j += 1
			k += 1

		# Checking if any element was left
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1

		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1


# Code to print the list
def printList(arr):
	for i in range(len(arr)):
		print(arr[i], end=" ")
	print()


# Driver Code
if __name__ == '__main__':
	arr = [12, 11, 13, 5, 6, 7]
	print("Given array is")
	printList(arr)
	mergeSort(arr)
	print("\nSorted array is ")
	printList(arr)

# This code is contributed by Mayank Khanna
# source: https://www.geeksforgeeks.org/merge-sort/

(fonte)

In cosa consiste

Il merge sort è un algoritmo di ordinamento basato sull’approccio “divide et impera”, che suddivide ricorsivamente un’array in sottoproblemi più piccoli, li ordina e poi combina le soluzioni dei sottoproblemi per ottenere l’array ordinato. Ecco una descrizione generale del funzionamento del merge sort:

  1. Divide: L’array non ordinato viene diviso a metà in modo ricorsivo fino a quando non si ottengono singoli elementi o sottoproblemi di dimensione 1.
  2. Conquista: Una volta che gli elementi sono divisi in singoli elementi (considerati ordinati per definizione), l’algoritmo inizia a combinare gli elementi in modo ordinato. Questo processo di fusione avviene combinando due sottoparti ordinate per creare una parte ordinata più grande. Questo passaggio è chiamato “merge”.
  3. Merge: L’operazione di merge prende due sottoparti ordinate e le fonde in un’unica parte ordinata. Questo viene fatto confrontando gli elementi più piccoli di entrambe le sottoparti e posizionando il più piccolo nell’array ordinato risultante. L’operazione di merge continua fino a quando tutti gli elementi delle sottoparti non sono stati inseriti nell’array ordinato.
  4. Ricombina: Questo processo di divisione e fusione continua fino a quando tutte le sottoparti non sono state unite in un’unica parte ordinata, creando così l’array completamente ordinato.
Ti potrebbe interessare:  Come sapere se un hosting supporta PHP-FPM

L’implementazione pratica di merge sort coinvolge tipicamente una funzione ricorsiva che divide l’array in due parti, ordina le due parti separatamente e infine fonde le due parti ordinate in un’unica parte ordinata.

Analisi della complessità del merge sort

La complessità temporale del merge sort è generalmente calcolata come O(n log n), dove ‘n’ è il numero di elementi nell’array da ordinare. Questo rappresenta la complessità nel caso peggiore, medio e migliore.

Nel merge sort, il processo di divisione ricorsiva dell’array in sottoarray di dimensioni sempre più piccole richiede un tempo logaritmico, O(log n), perché l’array viene diviso a metà ripetutamente fino a quando non si ottengono singoli elementi o sottoproblemi di dimensione 1.

Successivamente, il processo di fusione dei singoli elementi o sottoparti ordinate richiede un tempo lineare, O(n), dove ‘n’ è il numero totale di elementi nell’array. La fusione di due sottoparti ordinate richiede di scorrere attraverso entrambe le sottoparti, e in un contesto di fusione ricorsiva, questa operazione viene eseguita proporzionalmente al numero totale di elementi da unire.

Quindi, poiché l’intero array viene diviso in log(n) livelli e ciascun livello richiede un tempo lineare O(n) per la fusione, la complessità totale del merge sort è O(n log n).

Questo rende il merge sort un algoritmo molto efficiente per ordinare grandi quantità di dati, mantenendo una buona performance anche per dimensioni elevate di array da ordinare.

Esempi pratici di funzionamento del merge sort

Ecco una semplice spiegazione dell’algoritmo, passaggio dopo passaggio.

Da non perdere 👇👇👇



Questo portale esiste da 4414 giorni (12 anni), e contiene ad oggi 3961 articoli (circa 3.168.800 parole in tutto) e 12 servizi online gratuiti. – Leggi un altro articolo a caso
Non ha ancora votato nessuno.
Ti potrebbe interessare:  È tempo di Web3: cos'è e come funziona

Ti sembra utile o interessante? Vota e fammelo sapere.

Questo sito contribuisce alla audience di sè stesso.
Il nostro network informativo: Lipercubo.it - Pagare.online - Trovalost.it.