sábado, 26 de março de 2011

Algoritmo Mergesort em C

Algoritmo que ordena um vetor através da recursividade. A ideia é subdividir o vetor em 2 outros de mesmo tamanho ou com apenas a diferença de uma unidade (caso o vetor seja ímpar), ordená-los e depois intercalar, retornando o vetor inicial totalmente ordenado.

#include<stdio.h>
void intercalar (int v[],int aux[],int ini1, int ini2,int fim2)
{
int in1=ini1,in2=ini2,fim1=in2-1,au=0,i;
while(in1<=fim1 && in2<=fim2)
{
if (v[in1]<v[in2])
{
aux[au++] = v[in1++];
}
else
{
aux[au++] = v[in2++];
}
}
while(in1<=fim1)
{
aux[au++] = v[in1++];
}
while(in2<=fim2)
{
aux[au++] = v[in2++];
}

for(i=0;i<au;i++){
v[i+ini1]=aux[i];}
}
void mergeSort (int v[], int aux[],int esq, int dir)
{
int meio,i;
if(esq<dir)
{
meio=(esq+dir)/2;
mergeSort(v,aux,esq,meio);
mergeSort(v,aux,meio+1,dir);
intercalar(v,aux,esq,meio+1,dir);
}
}
int main()
{
int v[10]={45,23,10,25,89,75,46,32,20,1},aux[10],i;
mergeSort(v,aux,0,9);
for(i=0;i<10;i++)
{
printf("%d\t",v[i]);
}
return 0;
}

8 comentários:

  1. Muito obrigada!
    Procurava por um que realmente funcionava e não encontrava em lugar algum, um completo =]

    ResponderExcluir
  2. Parabens pelo blog, só faltou um sintaxhighlighter no Code para ficar perfeito seu blog!

    ResponderExcluir
  3. onde está sendo usada a variável "j"?

    ResponderExcluir
  4. a variável fim2, recebe qual valor na função mergesort?

    ResponderExcluir
  5. alguem sabe cmo faço para, imrpimir esse codigo passo a passo como funciona!, na tela!

    ResponderExcluir