Merge sort
O merge sort, ou ordenação por mistura, é um exemplo de algoritmo de ordenação por comparação do tipo dividir-para-conquistar.
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 | |
Algoritmos | |
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).
Características
editarAlgoritmo
editarOs três passos úteis dos algoritmos de divisão e conquista, ou divide and conquer, que se aplicam ao merge sort são:
- Dividir: Calcula o ponto médio do sub-arranjo, o que demora um tempo constante ;
- Conquistar: Recursivamente resolve dois subproblemas, cada um de tamanho n/2, o que contribui com para o tempo de execução;
- Combinar: Unir os sub-arranjos em um único conjunto ordenado, que leva o tempo
Complexidade
editar- Complexidade de tempo: .
- Complexidade de espaço: .
Demonstração da complexidade de tempo
editar
Para que teremos que fazer com que
Então:
Comparação com outros algoritmos de ordenação por comparação
editarEm 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
editar- É 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- 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
editarPseudocódigo
editarfunçã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
editarvoid 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++
editarvoid 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
editarpublic 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
editardef 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
editarReferências
- ↑ Felipe, Henrique (1 de julho 2018). «Merge Sort». Blog Cyberini. Consultado em 6 de julho de 2018
- ↑ Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2012). Algoritmos: teoria e prática 3 ed. Rio de Janeiro: Elsevier. ISBN 9788535236996
- ↑ Felipe, Henrique (19 de fevereiro de 2018). «Bubble Sort». Blog Cyberini. Consultado em 6 de julho de 2018