PDA

Visualizza la versione completa : [C]Merge Sort


zoritativo
10-06-2008, 10:50
#include <stdio.h>

void mergesort(int a[], int left, int right);
void merge(int a[], int left, int center, int right);

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

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);
}
}

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];
}


ciao ragazzi...non ho ben capito quando chjiama "void mergesort" che cosa succede ricorsivamente...

GreyFox86
10-06-2008, 12:19
Su wikipedia viene spiegato bene il funzionamento dell'algoritmo: http://en.wikipedia.org/wiki/Merge_sort

Loading