Merge sort – Wikipédia a enciclopédia livre

Prévia do material em texto

Merge sort
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
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 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 do Merge Sort usa a
recursividade em alguns problemas esta técnica não é
muito eficiente devido ao alto consumo de memória e
tempo de execução.
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 duas metades
recursivamente aplicando o merge sort;
3. Combinar: Juntar as duas metades em um único
conjunto já classificado.
Índice
1 Características
1.1 Observações
1.2 Desvantagens
2 Implementações
2.1 C
2.2 Código em C++
2.3 Código em C#
2.4 Haskell
2.5 Python
2.6 Ruby
2.7 R
2.8 Miranda
2.9 Prolog
3 Ver também
4 Ligações externas
Exemplo de execução do merge sort.
Características
Complexidade de tempo: Θ(n log 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 log n).
É possível também implementar o algoritmo com espaço
adicional Θ(1)
Algoritmo Criado por Von Neumann em 1945.
Desvantagens
Implementação complexa
Ideia complexa
Utiliza funções recursivas
Implementações
C
2
void merge(int vec[], int vecSize) {
 int mid;
 int i, j, k;
 int* tmp;
 
 tmp = (int*) malloc(vecSize * sizeof(int));
 if (tmp == NULL) {
 exit(1);
 }
 
 mid = vecSize / 2;
 
 i = 0;
 j = mid;
 k = 0;
 while (i < mid && j < vecSize) {
 if (vec[i] < vec[j]) {
 tmp[k] = vec[i];
 ++i;
 }
 else {
 tmp[k] = vec[j];
 ++j;
 }
 ++k;
 }
 
 if (i == mid) {
 while (j < vecSize) {
 tmp[k] = vec[j];
 ++j;
 ++k;
 }
 }
 else {
 while (i < mid) {
 tmp[k] = vec[i];
 ++i;
 ++k;
 }
 }
 
 for (i = 0; i < vecSize; ++i) {
 vec[i] = tmp[i];
 }
 
 free(tmp);
}
 
void mergeSort(int vec[], int vecSize) {
 int mid;
 
 if (vecSize > 1) {
 mid = vecSize / 2;
 mergeSort(vec, mid);
 mergeSort(vec + mid, vecSize - mid);
 merge(vec, vecSize);
 }
}
Código em C++
# include <stdio.h>
# include <ctype.h>
# include <string.h>
# include <stdlib.h>
 
# define MAX 10000001
# define SWAP(A, B) { int C = A; A = B; B =C; }
 
int A[MAX],B[MAX];
void mergesort(int begin, int end);
 
int main (void)
{
 int i = 0, j = 0;
 
 while(scanf("%d",&A[i]) >= 1)
 i++;
 
 mergesort(0,i-1);
 
 for(j = 0;j < i;j++)
 printf("%d\n",A[j]);
 
 return 0;
}
 
void mergesort(int begin, int end)
{
 int left = 0, right = 0, middle = 0;
 int i = 0;
 
 if(begin == end)
 return;
 
 middle = (begin + end)/2;
 
 mergesort(begin,middle);
 mergesort(middle + 1,end);
 
 left = begin;
 right = middle + 1;
 
 for(i = begin;i <= end;i++)
 {
 if(right > end || (left <= middle && A[left] <= A[right]))
 {
 B[i] = A[left];
 left++;
 }
 else
 {
 B[i] = A[right];
 right++;
 }
 }
 for(i = begin;i <= end;i++)
 A[i] = B[i];
}
Código em C#
=== [[ActionScript 3]] ===
<source lang="ActionScript">
/* Vetor de entrada */
 
var vetor:Array = new Array;
 
/*
 * Método recursivo que divide o vetor em dois e depois os mescla e ordena
 */
//trace (vetor);
function merge (inicio:int , fim:int):void
{
 if (inicio < fim)
 {
 var meio:int = (inicio + fim) / 2;
 merge (inicio, meio);
 merge (meio + 1, fim);
 merge (inicio, meio);
 merge (meio + 1, fim);
 mesclar (inicio, meio, fim);
 }
}
 
/* 
 * Ordena dois trechos ordenados e adjacente de vetores e ordena-os
 * conjuntamente
 */
function mesclar (inicio:int ,meio:int, fim:int):void
{
 var tamanho:int = fim - inicio + 1;
 /*
 * Inicialização de um vetor temporario para auxiliar na ordenação O
 * vetor temporário é uma cópia do trecho que será ordenado
 */
 
 var temp:Array = new Array ;//int[tamanho];
 ArrayCopy (vetor, inicio, temp, 0, tamanho);
 
 /*
 * Laço para ordenação do vetor, utilizando o vetor temporário, usando
 * índices i e j para cada trecho de vetor da mesclagem
 */
 
 var i:int = 0;
 var j:int = meio - inicio + 1;
 
 //A depender das condições, recebe um elemento de um trecho ou outro
 for (var posicao:int = 0; posicao < tamanho; posicao++)
 {
 if (j <= tamanho - 1)
 {
 if (i <= meio - inicio)
 {
 if (temp[i] < temp[j])
 {
 vetor[inicio + posicao] = temp[i++];
 }
 else
 {
 vetor[inicio + posicao] = temp[j++];
 }
 }
 else
 {
 vetor[inicio + posicao] = temp[j++];
 }
 }
 else
 {
 vetor[inicio + posicao] = temp[i++];
 }
 }
}
function ArrayCopy (src:Array,srcInit:int,dest:Array,destInit:int,_length:int):void
{
 var destIniHandler:int = destInit;
 for (var i:int=srcInit; i<(srcInit+_length); i++)
 {
 dest[destIniHandler] = src[i];
 destIniHandler++;
 }
}
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
 merge [] y=y
 merge x []=x
 merge (x:xs) (y:ys)
 | x <= y = x:merge xs (y:ys)
 | otherwise = y:merge (x:xs) ys
Python
def merge(lista_x,lista_y):
 if lista_x == []:
 return lista_y
 elif lista_y == []:
 return lista_x
 else:
 if lista_x[0] < lista_y[0]:
 return [lista_x[0]] + merge(lista_x[1:],lista_y)
 else:
 return [lista_y[0]] + merge(lista_x,lista_y[1:])
 
def mergesort(lista):
 if len(lista) <= 1:
 return lista
 else:
 mid = len(lista) // 2
 return merge(mergesort(lista[:mid]), mergesort(lista[mid:]))
Ruby
def sort(array)
 mid = array.length / 2
 mid < 1 ? array : merge(sort(array[0...mid]), sort(array[mid..-1]))
end
R
mergesort=function(x){ # Função que irá quebrar a entrada ao meio cada vez que for acionada
 semisort=function(y,z){ #Função que vai juntando ordenadamente as partes da entrada
 resultado=NULL
 while(length(y)>0 & length(z)>0){ # Enquanto tiver elemento nas duas partes que estou trabalhando
 if(y[1]<=z[1]){
 resultado=c(resultado,y[1])
 y=y[-1] # Tira o primeiro elemento do vetor, já que ele já foi adicionadoao resultado
 }
 else{
 resultado=c(resultado,z[1])
 z=z[-1] 
 }
 }
 if(length(y)>0){ # A partir do momento que acaba os elementos em uma das metades, me resta "copiar" o que sobrou da outra metade
 resultado=c(resultado,y)
 }
 if(length(z)>0){
 resultado=c(resultado,z)
 }
 return(resultado) # Retorna o resultado ordenado
 }
 tamanho=length(x) # Se a entrada tiver mais de um elemento, o algoritmo irá "quebrar" a entrada ao "meio" para ordenar individualmente cada entrada e depois juntar as metades já ordenadas
 if(tamanho>1){
 meio= tamanho/2
 esq=x[1:floor(meio)]
 dit=x[floor(meio+1):tamanho]
 esq=mergesort(esq) 
 dit=mergesort(dit)
 if(esq[length(esq)]<=dit[1]){
 return(c(esq,dit))
 }
 else{
 semisort(esq,dit)
 }
 }
 else{ # Se a entrada for um unico elemento, a ordenação dela é trivial
 return(x)
 }
}
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), !.
Ver também
Ordenação de vector
Quick sort
Bubble sort
Selection sort
Pesquisa binária
sort-merge utility
Heapsort
Shell sort
Radix sort
Ligações externas
http://c2.com/cgi/wiki?MergeSort
Merge sort em 13 linguagens (http://www.codecodex.com/wiki/Merge_sort)
Obtida de "http://pt.wikipedia.org/w/index.php?title=Merge_sort&oldid=33094010"
Categoria: Algoritmos de ordenação
Esta página foi modificada pela última vez à(s) 12h02min de 28 de novembro de 2012.
Este texto é disponibilizado nos termos da licença Atribuição-Partilha nos Mesmos Termos 3.0 não
Adaptada (CC BY-SA 3.0); pode estar sujeito a condições adicionais. Consulte as condições de uso
para mais detalhes.