𝖂𝖎ƙ𝖎𝖊

Merge sort

Predefinição:Info/Algoritmo 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ísticas

Algoritmo

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
Árvore de recursão

Complexidade

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

Demonstração da complexidade de tempo

Para que teremos que fazer com que

Então:

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

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

A sua eficiência é a mesma para melhor, pior e caso médio, independentemente de como os dados do array estão organizados a ordenação será eficaz.

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ções

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

  • 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 Mergesort

Pseudocódigo

função mergesort (vetor a)
     se (n == 1) retornar a

     vetor l1 = a[0] ... a[n/2]
     vetor l2 = a[n/2 + 1] ... a[n]

     l1 = mergesort(l1)
     l2 = mergesort(l2)

     retornar mesclar(l1, l2)
fim da função mergesort

função mesclar (vetor a, vetor b)
     vetor c

     enquanto (a e b têm elementos)
          if (a[0] > b[0])
               adicionar b[0] ao final de c
               remover b[0] de b
          senão
               adicionar a[0] ao final de c
               remover a[0] de a
     enquanto (a tem elementos)
          adicionar a[0] ao final de c
          remover a[0] de a
     enquanto (b tem elementos)
          adicionar b[0] ao final de c
          remover b[0] de b
     retornar c
fim da função mesclar

Código em C

void merge(int vetor[], int comeco, int meio, int fim) {
    int com1 = comeco, com2 = meio+1, comAux = 0, tam = fim-comeco+1;
    int *vetAux;
    vetAux = (int*)malloc(tam * sizeof(int));

    while(com1 <= meio && com2 <= fim){
        if(vetor[com1] < vetor[com2]) {
            vetAux[comAux] = vetor[com1];
            com1++;
        } else {
            vetAux[comAux] = vetor[com2];
            com2++;
        }
        comAux++;
    }

    while(com1 <= meio){  //Caso ainda haja elementos na primeira metade
        vetAux[comAux] = vetor[com1];
        comAux++;
        com1++;
    }

    while(com2 <= fim) {   //Caso ainda haja elementos na segunda metade
        vetAux[comAux] = vetor[com2];
        comAux++;
        com2++;
    }

    for(comAux = comeco; comAux <= fim; comAux++){    //Move os elementos de volta para o vetor original
        vetor[comAux] = vetAux[comAux-comeco];
    }
    
    free(vetAux);
}

void mergeSort(int vetor[], int comeco, int fim){
    if (comeco < fim) {
        int meio = (fim+comeco)/2;

        mergeSort(vetor, comeco, meio);
        mergeSort(vetor, meio+1, fim);
        merge(vetor, comeco, meio, fim);
    }
}

Implementação em C++

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++:

void Juntar(int vetor[], int ini, int meio, int fim, int vetAux[]) {
    int esq = ini;
    int dir = meio;
    for (int i = ini; i < fim; ++i) {
        if ((esq < meio) and ((dir >= fim) or (vetor[esq] < vetor[dir]))) {
            vetAux[i] = vetor[esq];
            ++esq;
        }
        else {
            vetAux[i] = vetor[dir];
            ++dir;
        }
    }
    //copiando o vetor de volta
    for (int i = ini; i < fim; ++i) {
        vetor[i] = vetAux[i];
    }
}

void MergeSort(int vetor[], int inicio, int fim, int vetorAux[]) {
    if ((fim - inicio) < 2) return;
    
    int meio = ((inicio + fim)/2);
    MergeSort(vetor, inicio, meio, vetorAux);
    MergeSort(vetor, meio, fim, vetorAux);
    Juntar(vetor, inicio, meio, fim, vetorAux);
}

void MergeSort(int vetor[], int tamanho) { //função que o usuario realmente chama
    //criando vetor auxiliar
    int vetorAux[tamanho];
    MergeSort(vetor, 0, tamanho, vetorAux);
}

Código em Java

public class WikiMerge<T extends Comparable<T>>{
	 /**
	* Método que recebe um array de inteiros e dois inteiros referentes ao início e ao fim
	* da ordenação desse array, o que nos garante o poder de escolher uma faixa do array
	* para ser ordenado.
	*
	* @param array
	* @param indiceInicio
	* @param indiceFim
	*/
	public void ordena(T[] array, int indiceInicio, int indiceFim) {

		// Condicional que verifica a validade dos parâmetros passados.
		if (array != null && indiceInicio < indiceFim && indiceInicio >= 0 &&
		 indiceFim < array.length && array.length != 0) {
			int meio = ((indiceFim + indiceInicio) / 2);

			ordena(array, indiceInicio, meio);
			ordena(array, meio + 1, indiceFim);

			merge(array, indiceInicio, meio, indiceFim);
		}

	}

	/**
	* O merge consiste na junção de duas listas já ordenadas.
	* Usa um array auxiliar.
	*
	* @param array
	* @param indiceInicio
	* @param meio
	* @param indiceFim
	*/
	public void merge(T[] array, int indiceInicio, int meio, int indiceFim) {

		T[] auxiliar =(T[]) new Comparable[array.length];
		//Copiando o trecho da lista que vai ser ordenada
		for (int i = indiceInicio; i <= indiceFim; i++) {
			auxiliar[i] = array[i];
		}

		//Índices auxiliares
		int i = indiceInicio;
		int j = meio + 1;
		int k = indiceInicio;

		//Junção das listas ordenadas
		while (i <= meio && j <= indiceFim) {
			if (auxiliar[i].compareTo(auxiliar[j]) < 0) {
				array[k] = auxiliar[i];
				i++;
			} else {
				array[k] = auxiliar[j];
				j++;
			}
			k++;
		}

		//Append de itens que não foram usados na Junção
		while (i <= meio) {
			array[k] = auxiliar[i];
			i++;
			k++;
		}

		//Append de itens que não foram usados na Junção
		while (j <= indiceFim) {
			array[k] = auxiliar[j];
			j++;
			k++;
		}
	}
} 

//teste

Código em Python

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
    return lista

Ver também

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 externas

no:Sorteringsalgoritme#Flettesortering

talvez você goste