Ordinamento per fusione: il codice

Ordinamento per fusione: il codice

Questo è il codice Julia dell’algoritmo di ordinamento per fusione, spiegato alle pagine 40-44 del libro.

# Questa funzione implementa l'algoritmo MergeSort.
# Quest'algoritmo applica in modo ricorsivo il paradigma
# del divide et impera. In particolare, la sequenza viene
# divisa in due sotto-sequenze di lunghezza circa uguale,
# le due sotto-sequenze in modo ricorsivo sono ordinate e
# quindi fuse dalla funzione merge.
function mergesort( a, sinistra, destra)
	if (sinistra < destra)
		centro = div(sinistra + destra, 2)
		mergesort(a,sinistra, centro)
		mergesort(a,centro + 1, destra)
		merge(a,sinistra, centro, destra)
	end
end

# Questa funzione implementa la funzione merge descritta 
# nel libro alle pagine 41-42. A tale scopo fa uso di un
# array di appoggio in cui inserire i numeri delle due
# sequenze ordinate. Alla fine, tale array di appoggio
# viene "riversato" nell'array di input.
function merge(a, sinistra, centro, destra)
	b = zeros(Int64,length(a))
	i = sinistra
	j = centro + 1
	k = 1
	while ((i <= centro) && (j <= destra))
		if (a[i]>a[j])
			b[k] = a[i]
			i = i + 1
		else
			b[k] = a[j]
			j = j + 1
		end
		k = k + 1
	end
	while (i <= centro)
		b[k] = a[i]
		i = i + 1
		k = k + 1
	end
	while (j <= destra)
		b[k] = a[j]
		j = j + 1
		k = k + 1
	end
	for i in sinistra:destra
		a[i] = b[i-sinistra+1]
	end
end

# Inizializza la sequenza da ordinare
a = [7,6,11,17,3,15,5,19,30,14]
println(a)
# Invoca la funzione di ordinamento
mergesort(a,1,length(a))
println(a)