Implementazioni di algoritmi/Merge sort: differenze tra le versioni

Wikibooks, manuali e libri di testo liberi.
Contenuto cancellato Contenuto aggiunto
m robot Aggiungo: no:Flettesortering
m Interwiki - Aggiungo: eo:Kunfanda ordigo
Riga 219: Riga 219:
[[de:Mergesort]]
[[de:Mergesort]]
[[en:Merge sort]]
[[en:Merge sort]]
[[eo:Kunfanda ordigo]]
[[es:Ordenamiento por mezcla]]
[[es:Ordenamiento por mezcla]]
[[fi:Lomituslajittelu]]
[[fi:Lomituslajittelu]]

Versione delle 13:12, 4 mar 2007

Template:S Il merge sort è un algoritmo di ordinamento abbastanza rapido, che utilizza un processo di risoluzione ricorsivo.

L'idea alla base del merge sort è il procedimento Divide et Impera, che consiste nella suddivisione del problema in sottoproblemi via via più piccoli.

Il merge sort opera quindi dividendo l'insieme da ordinare in due metà e procedendo all'ordinamento delle medesime ricorsivamente. Quando si sono divise tutte le metà si procede alla loro fusione (merge appunto) costruendo un insieme ordinato.

L'algoritmo fu inventato da John von Neumann nel 1945.

Esempio pratico

Supponiamo di dover ordinare il seguente array:

10 3 15 2 1 4 9 0

Si procede dividendolo in metà successive, fino ad arrivare a coppie:

10 3

15 2

 1 4

 9 0

A questo punto si fondono (merge) in maniera ordinata gli elementi, riunendo le metà:

10 3 -> 3 10

15 2 -> 2 15

 1 4 -> 1  4

 9 0 -> 0  9

Al passo successivo:

3 10 2 15 -> 2 3 10 15

1  4 0  9 -> 0 1  4  9

Infine:

2 3 10 15 0 1 4 9 -> 0 1 2 3 4 9 10 15

L'esecuzione ricorsiva all'interno del calcolatore non avviene nell'ordine descritto sopra, ma si è preferito formulare l'esempio in questo modo in maniera da renderlo più comprensibile.

Implementazioni

Seguono alcune implementazioni in vari linguaggi.

C

 #include <stdio.h>
 #define LEN 8
 
 void merge(int a[], int left, int center, int right)
 {
 	int i, j, k; 
 	int b[10];
 
 	i = left;
 	j = center+1;
 	k = 0;
 
 	while ((i<=center) && (j<=right)) {
 		if (a[i] <= a[j]) {
 			b[k] = a[i];
 			i++;
 		}
 		else {
 			b[k] = a[j];
 			j++;
 		}
 
 		k++;
 	}
 
 	while (i<=center) {
 		b[k] = a[i]; 
 		i++;
 		k++;
 	}
 
 	while (j<=right) {
 		b[k] = a[j]; 
 		j++; 
 		k++;
 	}
 
 	for (k=left; k<=right; k++)
 		a[k] = b[k-left];
 }
 
 void mergesort(int a[], int left, int right)
 {
 	int center;
 
 	if(left<right){
 		center = (left+right)/2;
 		mergesort(a, left, center);
 		mergesort(a, center+1, right);
 		merge(a, left, center, right);
 	}
 }
 
 int main(void)
 {
 	int a[LEN], i;
      
 	for(i=0; i<LEN; i++) {
 		printf(": ");
 		scanf("%d", &a[i]);  
 	}
 
 	mergesort(a, 0, LEN-1);
  
 	printf("[ ");
 
 	for(i=0; i<LEN; i++)
 		printf("%d ", a[i]);  
 
 	printf("]\n");
 
 	return 0;
 }

C++

typedef int Item;

void merge(Item a[], int left, int center, int right) {
	const int n=8;
	static Item aux[n];
	int i,j;
	for (i = center+1; i > left; i--) aux[i-1] = a[i-1];
	for (j = center; j < right; j++) aux[right+center-j] = a[j+1];
	for (int k = left; k <= right; k++)
	if (aux[j] < aux[i]) a[k] = aux[j--];
		else a[k] = aux[i++];
}


void mergesort(Item a[], int left, int right) {
	if (left<right) {
		int center = (left+right)/2;
		mergesort(a, left, center);
		mergesort(a, center+1, right);
		merge(a, left, center, right);
	}
}

int main() {
	const int n=8;
	int a[n] = {10, 3, 15, 2, 1, 4, 9, 0};
	mergesort(a,0,n-1);
	return 0;
}

Java

import java.util.*;
   
public class Sort{
       private static void mergeSort(int []a, int []vectorTemp, int left, int right ){
               if (left < right){
                       int center = (left + right) /2;
                       mergeSort (a, vectorTemp, left, center);
                       mergeSort (a, vectorTemp, center+1, right);
                       merge (a, vectorTemp, left, center+1, right);
               }
       }
       
       public static void mergeSort(int[]a ){
		int vectorTemp [];
		vectorTemp =new int [a.length];
		mergeSort (a, vectorTemp, 0, a.length-1);
       }

	private static void merge (int[]a, int[]vectorAux, int posLeft, int posRight, int posEnd ){
		int endLeft = posRight -1;
		int posAux = posLeft;
		int numElemen = posEnd - posLeft +1;

		while (posLeft <= endLeft && posRight <=posEnd)
		if ((a[ posLeft ])< (a[posRight]))        
			vectorAux [posAux++]=a[posLeft++];
		else
			vectorAux [posAux++] = a[posRight++];

		while (posLeft <= endLeft)
			vectorAux [posAux++]=a[posLeft++];

		while (posRight <= posEnd)
			vectorAux [posAux++]=a[posRight++];

		for (int i=0;i<numElemen;i++,posEnd--)
			a[posEnd]=vectorAux[posEnd];
	}

       public static void main (String [] args){
               int vector[]= { 10, 3, 15, 2, 1, 4, 9, 0};
	        mergeSort(vector);
       }
}

Analisi delle prestazioni

Il tempo di esecuzione dell'algoritmo Merge Sort è Θ(n log n). Infatti:

- la funzione merge ha costo Θ(n), e mergesort richiama se stessa due volte ogni volta su metà della porzione di input. Quindi possiamo associare al tempo di esecuzione di mergesort la funzione temporale

che per il secondo caso del teorema master è Θ(nlogn).