|
merge(a, left, center, right)
== Altri progetti ==
==Implementazioni==
{{interprogetto|b=Algoritmi/Merge sort|b_oggetto=implementazioni|b_preposizione=di}}
{{Trasferimento|wb|Implementazioni}}
[[Categoria:Algoritmi di ordinamento]]
Seguono alcune implementazioni in vari [[Linguaggio di programmazione|linguaggi]].
[[cs:Merge sort]]
===[[C (linguaggio)|C]]===
[[de:Mergesort]]
<source lang="C">
[[en:Merge sort]]
#include <stdio.h>
[[es:Ordenamiento por mezcla]]
#define LEN 8
[[eo:Kunfanda ordigo]]
[[fr:Tri fusion]]
void merge(int a[], int left, int center, int right) {
[[id:Merge sort]]
int i, j, k;
[[it:Merge sort]]
int b[LEN];
[[he:מיון מיזוג]]
[[lb:Mergesort]]
i = left;
[[lt:Sąlajos rikiavimo algoritmas]]
j = center+1;
[[nl:Mergesort]]
k = 0;
[[ja:マージソート]]
[[no:Flettesortering]]
while ((i<=center) && (j<=right)) {
[[pl:Sortowanie przez scalanie]]
if (a[i] <= a[j]) {
[[pt:Merge sort]]
b[k] = a[i];
[[ru:Сортировка слиянием]]
i++;
[[sk:Triedenie zlučovaním]]
} else {
[[fi:Lomituslajittelu]]
b[k] = a[j];
[[vi:Sắp xếp trộn]]
j++;
[[tr:Birleştirmeli Sıralama]]
}
[[uk:Сортування злиттям]]
[[zh:归并排序]]
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;
}
</source>
===[[C (linguaggio)|C (metodo iterativo)]]===
[[Immagine:Merge_sort_algorithm_diagram2.JPG|thumb|Rappresentazione grafica]]
Questa particolare implementazione iterativa dell'algoritmo si basa su un principio inverso alla ricorsione, mentre molte implementazioni iterative tentano di imitare la ricorsione usando una pila che simuli lo stack delle funzioni ricorsive, questa invece effettua le operazioni matematicamente inverse a quelle effettuate dal metodo ricorsivo:
il metodo ricorsivo divide il vettore per due fino ad arrivare all'elemento più piccolo, l'unità indivisibile, dopodiché comincia a fondere i singoli elementi formando delle coppie ordinate, poi crea delle coppie di coppie e cosi via fino ad ottenere il vettore completo ed ordinato, durante queste operazioni però ci sono dei resti, cioè dei pezzi di vettore avanzati che non potevano formare delle coppie, questi nel metodo ricorsivo sono molto facili da gestire poiché vengono lasciati nello stack, e fusi al momento opportuno con il pezzo di vettore precedentemente ordinato tramite il merge.
Nel metodo iterativo puro invece essi sono più difficili da gestire, ma con la variabile sizetomerge e l'operazione %n (resto della divisione per n) si è cercato di simulare proprio questo concetto, ottenendo cosi un algoritmo che operasse come il merge sort ricorsivo, senza usare strutture d'appoggio stack per i dati.
Si Parte dall'elemento indivisibile per formare delle coppie da fondere fino a coprire l'intera dimensione del vettore.
v={3,2,5,6,1}
iterative merge sort()
ciclo
{
elementi indivisibili [3] [2] [5] [6] [1]
merge a due a due [2,3] [5,6] resto: [1] sizetomerge - 1
merge a due a due [2,3,5,6] resto: [1] se ci fossero altri resti verrebbero fusi tra di loro
}
*n è il numero di elementi unitari costituenti la coppia di cui fare il merge. es. n=2 merging [e1] whit [e2]
*merge() effettua il classico merge sul vettore di due sottovettori a e b dove a = [ v[start], v[center] ] e b = [ v[center], v[end] ]
*sizetomerge è la lunghezza del vettore da coprire con il merging delle coppie per la prossima iterazione
*sizetomerge%n è il numero di elementi che non possono essere accoppiati (il resto)
*quando dopo un iterazione ci sono elementi che non possono essere accoppiati sizetomerge decrementa per lasciarli da parte, mentre se c'era già un vecchio resto i due resti vengono fusi in modo ordinato e poi si decrementa sizetomerge per lasciarli da parte.
*alla fine il resto ordinato viene fuso con il vettore ordinato
<source lang="C">
void merge(int a[], int start, int center, int end, int size) {
int i, j, k;
int app[size];
i = start;
j = center+1;
k = 0;
while ((i<=center) && (j<=end)) {
if (a[i] <= a[j]) {
app[k++] = a[i++];
} else {
app[k++] = a[j++];
}
}
while (i<=center)
app[k++] = a[i++];
while (j<=end)
app[k++] = a[j++];
for (k=start; k<=end; k++)
a[k] = app[k-start];
printv(a,size);
// printf("merging.. {v[%d] - v[%d]} whit {v[%d] - v[%d]} \n",start,center,center+1,end);
}
void iterativemergesort(int a[],int size) {
int sizetomerge=size-1;
size--;
int i;
int n=2;
while (n<sizetomerge*2) {
for (i=0; (i+n-1)<=sizetomerge; i+=n) {
merge(a,i,(i+i+n-1)/2,i+(n-1),sizetomerge);
}
i--;
if ((sizetomerge+1)%n!=0) {
if (size>sizetomerge)
merge (a,sizetomerge -((sizetomerge)%n),sizetomerge,size,size);
sizetomerge=sizetomerge-((sizetomerge+1)%n);}
n=n*2;
}
if (size>sizetomerge)
merge (a,0,size-(size-sizetomerge),size,size);
}
//dal main chiamare iterativemergesort(vettore,dimensione del vettore);
</source>
===[[C++]]===
<source lang="cpp">
typedef int Item;
int main() {
const int n=8;
int a[n] = {10, 3, 15, 2, 1, 4, 9, 0};
mergesort(a,0,n-1);
return 0;
}
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);
}
}
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++];
}
</source>
===[[Linguaggio di programmazione Java|Java]]===
<source lang="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 print(int[] vector) {
System.out.print("{");
for(int i=0;i<vector.length;i++) {
System.out.print(" "+vector[i]);
if(i==vector.length-1)
System.out.println(" }");
else System.out.print(",");
}
}
public static void main(String[] args) {
int vector[]= { 10, 3, 15, 2, 1, 4, 9, 0};
System.out.println("Array Non Ordinato:");
print(vector);
System.out.println();
mergeSort(vector);
System.out.println("Array Ordinato Con MergeSort:");
print(vector);
}
}
</source>
[[Categoria:Algoritmi di ordinamento]]
== Analisi delle prestazioni ==
| 