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 por comparaçã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 .

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

Algoritmo[editar | editar código-fonte]

Os três passos úteis dos algoritmos de divisão e conquista, ou divide and conquer, que se aplicam ao merge sort são:

  1. Dividir: Calcula o ponto médio do sub-arranjo, o que demora um tempo constante ;
  2. Conquistar: Recursivamente resolve dois sub-problemas, cada um de tamanho n/2, o que contribui com para o tempo de execução;
  3. Combinar: Unir os sub-arranjos em um único conjunto ordenado, que leva o tempo .

Equação de recorrência[editar | editar código-fonte]

Árvore de recursão

Complexidade[editar | editar código-fonte]

  • Complexidade de tempo: .
  • Complexidade de espaço: .

Comparação com outros algoritmos de ordenação por comparação[editar | editar código-fonte]

Em comparação com outros algoritmos de divisão e conquista como o Quick sort o Merge apresentam a mesma complexidade, mas em comparação com os algoritmos mais básicos de ordenação por comparação e troca (Bublle, insertion e selection sort), o Merge é mais rápido e eficiente, quando é utilizado uma grande quantidade de dados, para entradas pequenas os algoritmos de ordenação por comparação mais básicos são pró-eficientes.

Abaixo uma tabela para comparação:

Algoritmo Tempo
Melhor Médio Pior
Merge sort O(n*log(n)) O(n*log(n)) O(n*log(n))
Quick sort O(n*log(n)) O(n*log(n)) O(n2)
Bubble sort O(n) O(n2) O(n2)
Insertion sort O(n) O(n2) O(n2)
Selection sort O(n2) O(n2) O(n2)

Obs.: O Bubble sort apresenta melhor caso como O(n) porque o algoritmo pode ser modificado de forma que a lista já estando ordenando, basta apenas uma verificação básica que custa O(n), o Quick sort pode atingir um tempo de O(n2) em um caso específico quando o particionamento é desequilibrado.

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 .
  • É um algoritmo estável na maioria das implementações, em que elas podem ser iterativas ou recursivas.
  • É possível também implementar o algoritmo com espaço adicional .
  • Algoritmo Criado por Von Neumann em 1945.

Desvantagens[editar | editar código-fonte]

  • Utiliza funções recursivas;
  • 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).

Implementações do Mergesort[editar | editar código-fonte]

Pseudocódigo[editar | editar código-fonte]

MERGE-SORT(A, p, r)
    if p < r
        then q = ((p + r) / 2)
            Merge-Sort(A, p, q)
            Merge-Sort(A, q + 1, r)
            Merge(A, p, q, r)


Merge(A, p, q, r)
    n1 = q - p + 1
    n2 = r - q
    sejam L[1 ... n1 + 1] e R[1 ... n2 + 1]
    for i = 1 to n1
        L[i] = A[p + i - 1]
    for j = 1 to n2
        R[i] = A[q + j]

    i = 1
    j = 1
    
    for k = p to r
        if L[i] <= R[j]
            then A[k] = L[i]
                i = i + 1
            else A[k] = R[j]
                j = j + 1

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);
}

Implementação em C++:[editar | editar código-fonte]

void merge(int *, int, int, int); 

void mergeSort(int *array, int inicio, int fim) 
{
	if(inicio < fim) 
	{
		int meio = (inicio + fim) / 2;

		mergeSort(array, inicio, meio);
		mergeSort(array, meio + 1, fim);
		merge(array, inicio, meio, fim);
	}
}

void merge(int *array, int inicio, int meio, int fim) 
{
	int i, j, k, *auxiliar;
	
	i = inicio; 
	j = meio + 1;
	k = inicio; 
	auxiliar = array;  
	
	while(i <= meio && j <= fim)
	{
		if(auxiliar[i] < auxiliar[j])
		{
			array[k] = auxiliar[i];
			i++;
		}
		else
		{
			array[k] = auxiliar[j];
			j++;
		}
		k++;
	}
	
	while(i <= meio)
	{
		array[k] = auxiliar[i];
		i++;
		k++;
	}
	
	while(j <= fim)
	{
		array[k] = auxiliar[j];
		j++;
		k++;
	}
	
	for(int i = inicio; i < k; i++)
	{
		array[i] = auxiliar[i]; 
	}

}

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

 1 /**
 2  * O MergeSort é um algoritmo baseado no paradigma da Divisão e Conquista.
 3  * Consiste em recursivamente dividir um array nao ordenado ao meio e quando no caso mais
 4  * básico ordenar essas sublistas, aí então faz a junção dessas sublistas já ordenadas 
 5  * em um única lista ordenada. Note que se a lista tiver apenas um elemento 
 6  * (.length == 1) essa lista já está ordenada.
 7  * 
 8  * 
 9  *
10  *
11  */
12 public class WikiMerge<T extends Comparable<T>>{
13 	
14 	/**
15 	 * Método que recebe um array de inteiros e dois inteiros referentes ao inicio e ao fim
16 	 * da ordenação desse array, o que nos garante o poder de escolher uma faixa do array 
17 	 * para ser ordenado.
18 	 * 
19 	 * @param array
20 	 * @param indiceInicio
21 	 * @param indiceFim
22 	 */
23 	public void ordena(T[] array, int indiceInicio, int indiceFim){
24 		
25 		// Condicional que verifica a validade dos parametros passados.
26 		if (array != null && indiceInicio < indiceFim && indiceInicio < 0 &&
27 			indiceFim < array.length && array.length != 0) {
28 			int meio = ((indiceFim + indiceInicio) / 2);
29 			
30 			ordena(array, indiceInicio, meio);
31 			ordena(array, meio + 1, indiceFim);
32 			
33 			merge(array, indiceInicio, meio, indiceFim);
34 			
35 			
36 		}
37 		
38 	}
39 
40 	/**
41 	 * O merge consiste na junção de duas listas já ordenadas.
42 	 * Usa um array auxiliar.
43 	 * 
44 	 * @param array
45 	 * @param indiceInicio
46 	 * @param meio
47 	 * @param indiceFim
48 	 */
49 	public void merge(T[] array, int indiceInicio, int meio, int indiceFim) {
50 		
51 		T[] auxiliar =(T[]) new Comparable[array.length];
52 		//Copiando o trecho da lista que vai ser ordenada
53 		for (int i = indiceInicio; i <= indiceFim; i++) {
54 			auxiliar[i] = array[i];
55 		}
56 		
57 		//Índices auxiliares
58 		int i = indiceInicio;
59 		int j = meio + 1;
60 		int k = indiceInicio;
61 		
62 		//Junção das listas ordenadas
63 		while (i <= meio && j <= indiceFim) {
64 			if (auxiliar[i].compareTo(auxiliar[j]) < 0) {
65 				array[k] = auxiliar[i];
66 				i++;
67 			} else {
68 				array[k] = auxiliar[j];
69 				j++;				
70 			}
71 			k++;
72 		}
73 		
74 		//append de itens que não foram usados na Junção
75 		while (i <= meio) {
76 			array[k] = auxiliar[i];
77 			i++;
78 			k++;
79 		}
80 		
81 		//append de itens que não foram usados na Junção
82 		while (j <= indiceFim) {
83 			array[k] = auxiliar[j];
84 			j++;
85 			k++;
86 		}
87 	}
88 
89 }

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

def mergeSort(lista):
    
    if len(lista) > 1:
        
        meio = len(lista)/2
        
        listaDaEsquerda = lista[:meio]
        listaDaDireita = lista[meio:]

        mergeSort(listaDaEsquerda)
        mergeSort(listaDaDireita)

        i = 0
        j = 0
        k = 0
        
        while i < len(listaDaEsquerda) and j < len(listaDaDireita):
            
            if listaDaEsquerda[i] < listaDaDireita[j]:
                lista[k]=listaDaEsquerda[i]
                i += 1
            else:
                lista[k]=listaDaDireita[j]
                j += 1
            k += 1

        while i < len(listaDaEsquerda):
            
            lista[k]=listaDaEsquerda[i]
            i += 1
            k += 1

        while j < len(listaDaDireita):
            lista[k]=listaDaDireita[j]
            j += 1
            k += 1

Referências

  • Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Algoritmos (3rd ed.). MIT Press and McGraw-Hill. ISBN 978-85-352-36-6

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

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