Merge sort
Origem: Wikipédia, a enciclopédia livre.
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 sequência ordenada a partir de duas outras também ordenadas. Para isso, ele divide a sequência original em pares de dados, ordena-as; depois as agrupa em sequências de quatro elementos, e assim por diante, até ter toda a sequê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:
- Dividir: Dividir os dados em subsequências pequenas;
- Conquistar: Classificar as duas metades recursivamente aplicando o merge sort;
- Combinar: Juntar as duas metades em um único conjunto já classificado.
Índice |
[editar] Características
- Complexidade de tempo: Θ( n log2 n )
- Complexidade de espaço: Θ( n log2 n )
[editar] 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)
[editar] Implementações
[editar] 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<num_elementos;i++) { vetor[dire]=aux[dire]; dire=dire-1; } }
[editar] Java
/* * int [] x ===== vetor a ser ordenado * int [] xTemp ===== vetor auxiliar de mesmo tamanho ( obs: precisa ser inicializado ) * int esq ===== posição inicial, ou seja, 0 * int dir ===== posição final , x.length -1 */ public static void mergeSort(int [ ] x,int [ ] xTemp, int esq, int dir) { if(esq < dir) { int medio = (esq + dir)/2; mergeSort(x,xTemp,esq,medio); mergeSort(x,xTemp,medio+1,dir); mezclar(x,xTemp,esq,medio+1,dir); } } public static void mezclar (int [ ] x,int [ ] xAux,int posEsq, int posDir,int posFin) { int finIzq = posDir - 1; int posAux = posEsq; int numElementos = posFin - posEsq +1; // Busca principal while(posEsq <= finIzq && posDir <= posFin) if( x[posEsq] < x[posDir] ) xAux[posAux++] = x[posEsq++]; else xAux[posAux++] = x[posDir++]; // Copia primeira metade while (posEsq <= finIzq) xAux[posAux++] = x[posEsq++]; // Copia segunda metade while (posDir <= posFin) xAux[posAux++] = x[posDir++]; // Copia veteor temporário no principal for(int i = 0; i < numElementos; i++, posFin--) x[posFin] = xAux[posFin]; } }
[editar] Haskell
sort :: Ord a => [a] -> [a] sort [] = [] sort [x] = [x] sort xs = merge (sort ys) (sort zs) where merge (ys,zs) = splitAt (length xs `div` 2) xs
[editar] Python
def sort(array): if len(array) <= 1: return array mid = len(array) // 2 return merge (sort(array[0:mid]), sort(array[mid:]))
[editar] Ruby
def sort(array) mid = array.length / 2 mid < 1 ? array : merge(sort(array[0...mid]), sort(array[mid..-1])) end
[editar] 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
[editar] 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), !.
[editar] Ver também
- Ordenação de vector
- Quick sort
- Bubble sort
- Selection sort
- Pesquisa binária
- sort-merge utility
- Heapsort