Merg Sort

O merge sort, ou ordenação por mistura, é um exemplo de algoritmo de ordenação do tipo dividir-para-conquistar. Sua idéia básica é que é muito fácil criar uma seqüência ordenada a partir de duas outras também ordenadas. Para isso, ele divide a seqüência original em pares de dados, ordena-as; depois as agrupa em seqüências de quatro elementos, e assim por diante, até ter toda a seqüência dividida em apenas duas partes.

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 subseqüências pequenas;

    2. Conquistar: Classificar as duas metades recursivamente aplicando o merge sort;

    3. Combinar: Juntar as duas metades em um único conjunto já classificado.

■ Características

  • Complexidade de tempo: ->(n log2 n) é o mesmo que ->(n lg n)
  • Complexidade de espaço: ->(n)

■ Observações

  • É 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).
  • É possível também implementar o algoritmo com espaço adicional ?(1)
  • Algoritmo Criado por Von Neumann.
  • Comprovado cientificamente que é praticamente impossível fazer um algoritmo mais eficiente.

■ Desvantagens

  • Alto consumo de memória, devido a série de chamadas recursivas.

■ Implementações

 C 



void mergeSort(int vetor[],
int aux[],int tam) {
   m_sort(vetor,aux,0,tam-1);
}
 
void m_sort(int vetor[],
int aux[],int esq,int dire) {

   int meio;
   if (dire>esq) {
       meio=(dire+esq)/ 2;
       m_sort(vetor,aux,esq,meio);
       m_sort(vetor,aux,meio+1,dire);
       merge(vetor,aux,esq,meio+1,dire);
   }
}

void merge(int vetor[],int aux[],
int esq,int meio,int dire) {

   int i,esq_fim,num_elementos,aux_pos;

   esq_fim=meio-1;
   aux_pos=esq;
   num_elementos=dire-esq+1;

   while ((esq<=esq_fim)&&(meio<=dire)) {
 
    if (vetor[esq]<=vetor[meio]) {
   
      aux[aux_pos]=vetor[esq];
      aux_pos=aux_pos+1;
      esq=esq+1;
    }
    else {
   
      aux[aux_pos]=vetor[meio];
      aux_pos=aux_pos + 1;
      meio=meio+1;
    }
   }

 while (esq<=esq_fim) {
 
   aux[aux_pos]=vetor[esq];
   esq=esq+1;
   aux_pos=aux_pos+1;
 }

 while (meio<=dire) {
 
   aux[aux_pos]=vetor[meio];
   meio=meio+1;
   aux_pos=aux_pos+1;
 }

 for (i=0;i

■ Java 


/* Vetor de entrada */

private int[] vetor;

/*
 * Método recursivo que divide o 
 * vetor em dois e depois os mescla e ordena
 */

private void merge(int inicio, int fim) {

 if (inicio < fim) {
  int meio = (inicio + fim) / 2;
  merge(inicio, meio);
  merge(meio + 1, fim);
  mesclar(inicio, meio, fim);
        }
}

/* 
 * Ordena dois trechos ordenados e 
 *adjacente de vetores e ordena-os
 * conjuntamente
 */
private void mesclar(int inicio,
 int meio, int fim) {

 int tamanho = fim - inicio + 1;

 /*
* Inicialização de um vetor temporário
* para auxiliar na ordenação O vetor
* temporário é uma cópia do trecho 
* que será ordenado
*/

 int[] temp = new int[tamanho];

for (int posicao = 0; posicao 
 tamanho; posicao++) {
 temp[posicao] = vetor[inicio + posicao];
  }

 /*
* Laço para ordenação do vetor, utilizando
* o vetor temporário, usando
* índices i e j para cada trecho
* de vetor da mesclagem
 */
 int i = 0;
 int j = meio - inicio + 1;

 //Dependendo das condições, recebe
 //um elemento de um trecho ou outro

  for (int posicao = 0; posicao 
< tamanho; posicao++) {
 vetor[inicio + posicao] = 
  (j <= tamanho - 1) ? 
  ((i <= meio - inicio) ? 
   (temp[i] < temp[j]) ? 
    temp[i++]
    : temp[j++]
    : temp[j++])
    : temp[i++];
       }
}

■ Haskell 


sort :: Ord a => [a] -> [a]

sort [] =  []
sort [x] =  [x]
sort xs  =  merge (sort ys) (sort zs)
  where 
(ys,zs) = splitAt (length xs `div` 2) xs

■ Python 


def sort(array):
  if len(array) <= 1: return array
  mid = len(array) // 2
  return merge (sort(array[0:mid]),
  sort(array[mid:]))

■ Ruby 

def sort(array)
 mid = array.length / 2
 mid < 1 ? array : merge(sort(array[0...mid]),
 sort(array[mid..-1]))
end

■ Miranda 


sort []    = []
sort [x]   = [x]
sort array = merge (sort left) (sort right)
  where
   left  = [array!y | y <- [0..mid]]
   right = [array!y | y <- [(mid+1)..max]]
   max   = #array - 1
   mid   = max div 2

■ Prolog 


split([], K, [], []).
split(XS, K, [], XS)        :-
        K < 1.
split([X|XS], K, [X|YS], ZS):-
        K >= 1,
        P is K -1,
        split(XS, P, YS, ZS).

merge1([], [], []).
merge1(XS, [], XS).
merge1([], YS, YS).
merge1([X|XS], [Y|YS], [X|ZS]) :-
        X =< Y,
        merge1(XS, [Y|YS], ZS).
merge1([X|XS], [Y|YS], [Y|ZS]) :-
        Y < X,
        merge1([X|XS], YS, ZS).

mergesort([], []).
mergesort([X], [X]).
mergesort([X, Y], [X, Y])   :-
        X =< Y, !.
mergesort([X, Y], [Y, X])  :-
        X > Y, !.
mergesort(XS, ZS)          :-
        length(XS, L),
        L > 0,
        K is L / 2,
        split(XS, K, XS1, XS2),
        mergesort(XS1, YS1),
        mergesort(XS2, YS2),
        merge1(YS1, YS2, ZS), !.

[Topo]

[Voltar]

 

Associação SoftwareLivre

A Associação SoftwareLivre.org (ASL) é uma associação civil sem fins-lucrativos, com sede em Porto Alegre/RS que reúne empresários, profissionais liberais, estudantes e servidores públicos, estabelecendo relações com os mais diversos setores da sociedade como o poder público, universidades, empresas, grupos de usuários, hackers e ONGs. A ASL tem por principal objetivo tornar o software livre amplamente incluído na sociedade, propiciando espaço de discussão, apoio, fomento e organização de iniciativas nas mais diversas áreas relacionadas. - Site oficial da associação