Abrir menu principal
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
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 subproblemas e resolver esses subproblemas através da recursividade) e Conquistar (após todos os subproblemas terem sido resolvidos ocorre a conquista que é a união das resoluções dos subproblemas). 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ísticasEditar

AlgoritmoEditar

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 subproblemas, 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ênciaEditar

 
Árvore de recursão

 

ComplexidadeEditar

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

Demonstração da complexidade de tempoEditar

 

 

Para que   teremos que fazer com que  

Então:

 

Comparação com outros algoritmos de ordenação por comparaçãoEditar

Em comparação a outros algoritmos de divisão e conquista, como o Quicksort, o Merge apresenta a mesma complexidade. Já em comparação a algoritmos mais básicos de ordenação por comparação e troca (bubble, insertion e selection sort), o Merge é mais rápido e eficiente quando é utilizado sobre uma grande quantidade de dados[1]. Para entradas pequenas os algoritmos de ordenação por comparação mais básicos são pró-eficientes.

Abaixo uma tabela para comparação[2]:

Algoritmo Tempo
Melhor Médio Pior
Merge sort      
Quick sort      
Bubble sort      
Insertion sort      
Selection sort      

Obs.: O Bubble sort apresenta melhor caso como  porque o algoritmo pode ser modificado de forma que, se a lista já estiver ordenada, basta apenas uma verificação básica que custa  [3]. O Quick sort pode atingir um tempo de  em um caso específico quando o particionamento é desequilibrado.

ObservaçõesEditar

 
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.

DesvantagensEditar

  • Utiliza funções recursivas;
  • Gasto extra de memória. O algoritmo cria uma cópia do vetor para cada nível da chamada recursiva, totalizando um uso adicional de memória igual a  .

Implementações do MergesortEditar

PseudocódigoEditar

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[j] = 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 CEditar

 1 void merge(int vetor[], int comeco, int meio, int fim) {
 2     int com1 = comeco, com2 = meio+1, comAux = 0, tam = fim-comeco+1;
 3     int *vetAux;
 4     vetAux = (int*)malloc(tam * sizeof(int));
 5 
 6     while(com1 <= meio && com2 <= fim){
 7         if(vetor[com1] < vetor[com2]) {
 8             vetAux[comAux] = vetor[com1];
 9             com1++;
10         } else {
11             vetAux[comAux] = vetor[com2];
12             com2++;
13         }
14         comAux++;
15     }
16 
17     while(com1 <= meio){  //Caso ainda haja elementos na primeira metade
18         vetAux[comAux] = vetor[com1];
19         comAux++;
20         com1++;
21     }
22 
23     while(com2 <= fim) {   //Caso ainda haja elementos na segunda metade
24         vetAux[comAux] = vetor[com2];
25         comAux++;
26         com2++;
27     }
28 
29     for(comAux = comeco; comAux <= fim; comAux++){    //Move os elementos de volta para o vetor original
30         vetor[comAux] = vetAux[comAux-comeco];
31     }
32     
33     free(vetAux);
34 }
35 
36 void mergeSort(int vetor[], int comeco, int fim){
37     if (comeco < fim) {
38         int meio = (fim+comeco)/2;
39 
40         mergeSort(vetor, comeco, meio);
41         mergeSort(vetor, meio+1, fim);
42         merge(vetor, comeco, meio, fim);
43     }
44 }

Implementação em C++Editar

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

    while(i <= meio){
        saida[k] = auxiliar[i];
        i++;
        k++;
    }

    while(j <= fim){
        saida[k] = auxiliar[j];
        j++;
        k++;
    }
    //Copia os elementos que foram ordenados para o auxiliar
    for(int p = inicio; p <= fim; p++)
        auxiliar[p] = saida [p];
}



void mergeSort(int *saida, int *auxiliar, int inicio, int fim){
    if(inicio < fim){
        int meio = (inicio + fim) / 2;
        mergeSort(saida, auxiliar, inicio, meio);
        mergeSort(saida, auxiliar, meio + 1, fim);
        merge(saida, auxiliar, inicio, meio, fim);
    }
}

Outra implementação em C++:

 1 void Juntar(int vetor[], int ini, int meio, int fim, int vetAux[]) {
 2     int esq = ini;
 3     int dir = meio;
 4     for (int i = ini; i < fim; ++i) {
 5         if ((esq < meio) and ((dir >= fim) or (vetor[esq] < vetor[dir]))) {
 6             vetAux[i] = vetor[esq];
 7             ++esq;
 8         }
 9         else {
10             vetAux[i] = vetor[dir];
11             ++dir;
12         }
13     }
14     //copiando o vetor de volta
15     for (int i = ini; i < fim; ++i) {
16         vetor[i] = vetAux[i];
17     }
18 }
19 
20 void MergeSort(int vetor[], int inicio, int fim, int vetorAux[]) {
21     if ((fim - inicio) < 2) return;
22     
23     int meio = ((inicio + fim)/2);
24     MergeSort(vetor, inicio, meio, vetorAux);
25     MergeSort(vetor, meio, fim, vetorAux);
26     Juntar(vetor, inicio, meio, fim, vetorAux);
27 }
28 
29 void MergeSort(int vetor[], int tamanho) { //função que o usuario realmente chama
30     //criando vetor auxiliar
31     int vetorAux[tamanho];
32     MergeSort(vetor, 0, tamanho, vetorAux);
33 }

Código em JavaEditar

 1 public class WikiMerge<T extends Comparable<T>>{
 2 	 /**
 3 	* Método que recebe um array de inteiros e dois inteiros referentes ao início e ao fim
 4 	* da ordenação desse array, o que nos garante o poder de escolher uma faixa do array
 5 	* para ser ordenado.
 6 	*
 7 	* @param array
 8 	* @param indiceInicio
 9 	* @param indiceFim
10 	*/
11 	public void ordena(T[] array, int indiceInicio, int indiceFim) {
12 
13 		// Condicional que verifica a validade dos parâmetros passados.
14 		if (array != null && indiceInicio < indiceFim && indiceInicio >= 0 &&
15 		 indiceFim < array.length && array.length != 0) {
16 			int meio = ((indiceFim + indiceInicio) / 2);
17 
18 			ordena(array, indiceInicio, meio);
19 			ordena(array, meio + 1, indiceFim);
20 
21 			merge(array, indiceInicio, meio, indiceFim);
22 		}
23 
24 	}
25 
26 	/**
27 	* O merge consiste na junção de duas listas já ordenadas.
28 	* Usa um array auxiliar.
29 	*
30 	* @param array
31 	* @param indiceInicio
32 	* @param meio
33 	* @param indiceFim
34 	*/
35 	public void merge(T[] array, int indiceInicio, int meio, int indiceFim) {
36 
37 		T[] auxiliar =(T[]) new Comparable[array.length];
38 		//Copiando o trecho da lista que vai ser ordenada
39 		for (int i = indiceInicio; i <= indiceFim; i++) {
40 			auxiliar[i] = array[i];
41 		}
42 
43 		//Índices auxiliares
44 		int i = indiceInicio;
45 		int j = meio + 1;
46 		int k = indiceInicio;
47 
48 		//Junção das listas ordenadas
49 		while (i <= meio && j <= indiceFim) {
50 			if (auxiliar[i].compareTo(auxiliar[j]) < 0) {
51 				array[k] = auxiliar[i];
52 				i++;
53 			} else {
54 				array[k] = auxiliar[j];
55 				j++;
56 			}
57 			k++;
58 		}
59 
60 		//Append de itens que não foram usados na Junção
61 		while (i <= meio) {
62 			array[k] = auxiliar[i];
63 			i++;
64 			k++;
65 		}
66 
67 		//Append de itens que não foram usados na Junção
68 		while (j <= indiceFim) {
69 			array[k] = auxiliar[j];
70 			j++;
71 			k++;
72 		}
73 	}
74 } 
75 
76 //teste

Código em PythonEditar

def mergeSort(lista):

    if len(lista) > 1:

        meio = len(lista)//2
        #também é valido: meio = int(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

Ver tambémEditar

Referências

  1. Felipe, Henrique (1 de julho 2018). «Merge Sort». Blog Cyberini. Consultado em 6 de julho de 2018 
  2. Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2012). Algoritmos: teoria e prática 3 ed. Rio de Janeiro: Elsevier. ISBN 9788535236996 
  3. Felipe, Henrique (19 de fevereiro de 2018). «Bubble Sort». Blog Cyberini. Consultado em 6 de julho de 2018 

Ligações externasEditar