Merge sort

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Merge sort

algoritmo mergesort
classe Algoritmo de ordenação
estrutura de dados Array, Listas ligadas
complexidade pior caso
complexidade caso médio
complexidade melhor caso típico,

variante natural

complexidade de espaços pior caso auxiliar
Algoritmos

O merge sort, ou ordenação por mistura, é um exemplo de algoritmo de ordenação do tipo dividir-para-conquistar.

Sua ideia básica consiste em Dividir (o problema em vários sub-problemas e resolver esses sub-problemas através da recursividade) e Conquistar (após todos os sub-problemas terem sido resolvidos ocorre a conquista que é a união das resoluções dos sub-problemas). Como o algoritmo Merge Sort usa a recursividade, há um alto consumo de memória e tempo de execução, tornando esta técnica não muito eficiente em alguns problemas .

Os três passos úteis dos algoritmos dividir-para-conquistar, ou divide and conquer, que se aplicam ao merge sort são:

  1. Dividir: Dividir os dados em subsequências pequenas;
  2. Conquistar: Classificar as metades recursivamente aplicando o merge sort; e
  3. Combinar: Juntar as metades em um único conjunto já classificado.

Características[editar | editar código-fonte]

  • Complexidade de tempo: Θ(n log2 n).
  • Complexidade de espaço: Θ(n).

Observações[editar | editar código-fonte]

Exemplo de execução do merge sort.
  • É possível implementar o merge sort utilizando somente um vetor auxiliar ao longo de toda a execução, tornando assim a complexidade de espaço adicional igual a Θ(n log n).
  • É possível também implementar o algoritmo com espaço adicional Θ(1).
  • Algoritmo Criado por Von Neumann em 1945.

Desvantagens[editar | editar código-fonte]

  • Utiliza funções recursivas; e
  • Gasto extra de memória. O algorítimo cria uma cópia do vetor para cada nível da chamada recursiva, totalizando um uso adicional de memória igual a (n log n).

Código em C[editar | editar código-fonte]

void mergeSort(int *vetor, int posicaoInicio, int posicaoFim) {
    int i, j, k, metadeTamanho, *vetorTemp;

    if(posicaoInicio == posicaoFim) return;

    // ordenacao recursiva das duas metades
    metadeTamanho = (posicaoInicio + posicaoFim ) / 2;
    mergeSort(vetor, posicaoInicio, metadeTamanho);
    mergeSort(vetor, metadeTamanho + 1, posicaoFim);

    // intercalacao no vetor temporario t
    i = posicaoInicio;
    j = metadeTamanho + 1;
    k = 0;
    vetorTemp = (int *) malloc(sizeof(int) * (posicaoFim - posicaoInicio + 1));

    while(i < metadeTamanho + 1 || j  < posicaoFim + 1) {
        if (i == metadeTamanho + 1 ) { // i passou do final da primeira metade, pegar v[j]
            vetorTemp[k] = vetor[j];
            j++;
            k++;
        }
        else {
            if (j == posicaoFim + 1) { // j passou do final da segunda metade, pegar v[i]
                vetorTemp[k] = vetor[i];
                i++;
                k++;
            }
            else {
                if (vetor[i] < vetor[j]) {
                    vetorTemp[k] = vetor[i];
                    i++;
                    k++;
                }
                else {
                    vetorTemp[k] = vetor[j];
                    j++;
                    k++;
                }
            }
        }

    }
    // copia vetor intercalado para o vetor original
    for(i = posicaoInicio; i <= posicaoFim; i++) {
        vetor[i] = vetorTemp[i - posicaoInicio];
    }
    free(vetorTemp);
}

Ver também[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]