Estrutura de Dados
Gostaria de reagir a esta mensagem? Crie uma conta em poucos cliques ou inicie sessão para continuar.

Ir para baixo
Lukinha
Lukinha
Admin
Admin
Mensagens : 5
Pontos : 17
Reputação : 2
Data de inscrição : 05/05/2017
Idade : 33
Localização : Bandeirantes

MergeSort - Método de Ordenação Empty MergeSort - Método de Ordenação

Seg Nov 13, 2017 1:55 pm
Definição

Algoritmo de ordenação é baseado primeiramente em selecionar um elemento, dividir a lista e então, ordenar-las separadamente. E posteriormente há um processo complementar o qual é chamado de junção. O processo de Seleção e junção são complementares porque:
Seleção: divide a lista em 2 outras independentes. Junção: une 2 listas independentes em uma lista maior ordenada.

Isso insinua que o Mergesort consiste em duas chamadas recursivas e um processo de junção. Então, Mergesort é um algoritmo recursivo, que é implementado dividindo uma sequência original em pares de dados, ordena-as e depois as agrupa em sequências de quatro elementos, e assim por diante, até ter toda a sequência dividida em apenas duas partes. Assim, sua idéia básica é que é muito fácil criar uma sequência ordenada a partir de duas outras também ordenadas.
O mergeSort consiste em dividir um problema maior em problemas pequenos, e sucessivamente até que o mesmo seja resolvido diretamente.
Esta técnica realiza-se em três fases:
1 - Divisão: o problema maior é dividido em problemas menores e os problemas menores obtidos são novamente divididos sucessivamente de maneira recursiva.
2 - Conquista: o resultado do problema é calculado quando o problema é pequeno o suficiente.
3 - Combinação: os resultados dos problemas menores são combinados até que seja obtida a solução do problema maior. Algoritmos que utilizam o método de partição são caracterizados por serem os mais rápidos dentre os outros algoritmos pelo fato de sua complexidade ser, na maioria das situações, O(nlogn).
MergeSort - Método de Ordenação Merge10
Figura 1. Esquema de funcionamento do MergeSort

Performances:
Melhor caso: O(N log N).
Pior caso (raro): O(N log N).

Operações do Algoritmo

Função Intercala
Código:

void intercala(int *X, int ini, int fim, int meio){
    int poslivre, ini_v1, ini_v2, i, aux[10];
    ini_v1=ini;
    ini_v2=meio+1;
    poslivre=ini;
    while(ini_v1<=meio && ini_v2<=fim){
        if(X[ini_v1]<=X[ini_v2]){
            aux[poslivre]=X[ini_v1];
            ini_v1++;
        }
        else{
            aux[poslivre]=X[ini_v2];
            ini_v2++;
        }
        poslivre++;
    }

    for(i=ini_v1; i<=meio; i++){
        aux[poslivre]=X[i];
        poslivre++;
    }
    for(i=ini_v2; i<=fim; i++){
        aux[poslivre]=X[i];
        poslivre++;
    }

    for(i=ini; i<=fim; i++){
        X[i]=aux[i];
    }
}

Função de Ordenação
Código:

void merge(int *X, int ini, int fim){
   int meio;
   if(ini<fim){
     meio=(int)floor((ini+fim)/2);
     merge(X, ini, meio);
     merge(X, meio+1, fim);
     intercala(X, ini, fim, meio);
   }
}

Main
Código:

int main()
{
    int X[10], i;
    for(i=0; i<10; i++){
        printf("\nDigite o %do elemento:   ", i+1);
        scanf("%d",&X[i]);
    }

    printf("\n\n Desordenado");

    for(i=0; i<10; i++)  printf("\t%d", X[i]);
    merge(&X[0], 0, 9);
    printf("\n\n Ordenado");

    for(i=0; i<10; i++)  printf("\t%d", X[i]);

    return 0;
}

Videos para reforços ( ABRA OS SPOILERS )

MergeSort Método de Ordenação:


ATIVIDADE DE FIXAÇÃO ( ABRA O SPOILER )
Spoiler:
Ir para o topo
Permissões neste sub-fórum
Não podes responder a tópicos