Baixe o app para aproveitar ainda mais
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.
Compartilhar