Na aula de hoje vamos conhecer mais um algoritmo de ordenação, o Algoritmo Merge Sort. Vamos aprender como é seu funcionamento e apresentar uma implementação em portugol que pode ser traduzida facilmente para outras linguagens de programação.
O Merge Sort é um algoritmo de ordenação muito eficiente que possui o mesmo custo no melhor e no pior caso. Seu ponto fraco reside no fato de usar um vetor auxiliar durante o processo de ordenação, aumentando não apenas o tempo de execução devido às cópias de dados mas também o consumo de memória.
Aulas anteriores sobre ordenação:
Algoritmo BUBBLE SORT
Algoritmo SELECTION SORT
Algoritmo INSERTION SORT
O Merge Sort pode ser implementado como um procedimento que recebe como parâmetro o vetor a ser ordenado. Basicamente ele possui duas etapas. A primeira etapa consiste em dividir o vetor em partes menores. Aqui temos uma aplicação prática de um princípio muito difundido na computação: dividir pra conquistar. Ordenar um vetor inteiro pode ser difícil, então dividimos o vetor em vetores menores até um ponto em que o vetor seja tão pequeno que sabemos como ordenar.
Esse processo de divisão pode ser feito por meio de chamadas recursivas. Perceba que na prática não ocorre nenhuma divisão do vetor. Esta divisão é virtual, ou seja, por meio dos índices de acesso ao vetor. Primeiro dividimos o vetor ao meio, depois cada metade é dividida ao meio novamente. Esse processo de divisão continua até que cada parte do vetor tenha apenas um elemento.
Seguindo esta ideia, nosso procedimento receberá, além do vetor a ser ordenado, os índices de início e fim do vetor. Na primeira chamada ao procedimento será passado o vetor completo, então o índice inicial será 0 (zero) e o índice final será o tamanho do vetor menos 1.
/*
Algoritmo Merge Sort parte 1
*/
funcao merge_sort(inteiro vetor[], inteiro ini, inteiro fim){
inteiro meio, i, j, k, aux[tamanho]
// tamanho do vetor é maior que 1?
se(ini < fim){
meio = (ini + fim) / 2 // calcula o meio do vetor
merge_sort(vetor, ini, meio) // metade à esquerda
merge_sort(vetor, meio + 1, fim) // metade a direita
// fazer o merge, ordenando os elementos (Segunda Etapa)
}
}
A primeira etapa, apresentada no trecho de código acima, fará a divisão do vetor até que cada parte possua apenas 1 elemento. Um vetor que possui apenas um elemento já está ordenado. A segunda etapa consiste em juntar as partes do vetor fazendo uma intercalação, ou seja, inserindo os elementos das partes em um vetor auxiliar de forma ordenada. Ao fim do processo, os elementos ordenados no vetor auxiliar são copiados para o vetor original.
/*
Algoritmo Merge Sort parte 1 e parte 2
*/
funcao merge_sort(inteiro vetor[], inteiro ini, inteiro fim){ // 6 ,4 ,8 ,2,7
inteiro meio, i, j, k, aux[tamanho]
// tamanho do vetor é maior que 1?
se(ini < fim){
meio = (ini + fim) / 2 // calcula o meio do vetor
merge_sort(vetor, ini, meio) // metade à esquerda
merge_sort(vetor, meio + 1, fim) // metade a direita
// fazer o merge, ordenando os elementos (Segunda Etapa)
i = ini // início da primeira parte do vetor, que termina em meio
j = meio + 1 // início da segunda parte do vetor, que termina em fim
k = ini
enquanto(i <= meio e j <= fim){
se(vetor[i] < vetor[j]){
aux[k] = vetor[i] // copia o elemento da primeira parte do vetor
i++
}
senao{
aux[k] = vetor[j] // copia o elemento da segunda parte do vetor
j++
}
k++
}
// ainda há um passo aqui descrito a seguir
// copia os elementos já ordenados do vetor auxiliar para o vetor original
para(i = ini; i <= fim; i++)
vetor[i] = aux[i]
}
}
Perceba que ao intercalar as duas partes do vetor, inserindo de forma ordenada no vetor auxiliar, uma das partes irá finalizar primeiro. Então precisamos copiar o restante da outra parte para o vetor auxiliar. É esta parte que estava faltando no trecho de código acima, inserida agora no trecho de código a seguir.
/*
Algoritmo Merge Sort parte 1 e parte 2
*/
funcao merge_sort(inteiro vetor[], inteiro ini, inteiro fim){ // 6 ,4 ,8 ,2,7
inteiro meio, i, j, k, aux[tamanho]
// tamanho do vetor é maior que 1?
se(ini < fim){
meio = (ini + fim) / 2 // calcula o meio do vetor
merge_sort(vetor, ini, meio) // metade à esquerda
merge_sort(vetor, meio + 1, fim) // metade a direita
// fazer o merge, ordenando os elementos (Segunda Etapa)
i = ini // início da primeira parte do vetor, que termina em meio
j = meio + 1 // início da segunda parte do vetor, que termina em fim
k = ini
enquanto(i <= meio e j <= fim){
se(vetor[i] < vetor[j]){
aux[k] = vetor[i] // copia o elemento da primeira parte do vetor
i++
}
senao{
aux[k] = vetor[j] // copia o elemento da segunda parte do vetor
j++
}
k++
}
// copia o resto da primeira parte se foi a segunda que finalizou
enquanto(i <= meio){
aux[k] = vetor[i]
i++
k++
}
// copia o resto da segunda parte se foi a primeira que finalizou
enquanto(j <= fim){
aux[k] = vetor[j]
j++
k++
}
// copia os elementos já ordenados do vetor auxiliar para o vetor original
para(i = ini; i <= fim; i++)
vetor[i] = aux[i]
}
}
Código completo em Portugol para o algoritmo de ordenação Merge Sorte
programa{
/*
Algoritmo de Ordenação MergeSort
Código escrito por Wagner Gaspar
Setembro de 2021
*/
const inteiro tamanho = 9
funcao imprimir_vetor(inteiro vetor[]){
inteiro i
para(i = 0; i < tamanho; i++)
escreva(vetor[i], " ")
}
funcao merge_sort(inteiro vetor[], inteiro ini, inteiro fim){ // 6 ,4 ,8 ,2,7
inteiro meio, i, j, k, aux[tamanho]
// tamanho do vetor é maior que 1?
se(ini < fim){
meio = (ini + fim) / 2
merge_sort(vetor, ini, meio)
merge_sort(vetor, meio + 1, fim)
// fazer o merge ordenando os elementos
i = ini
j = meio + 1
k = ini
enquanto(i <= meio e j <= fim){
se(vetor[i] < vetor[j]){
aux[k] = vetor[i]
i++
//k++
}
senao{
aux[k] = vetor[j]
j++
//k++
}
k++
}
enquanto(i <= meio){
aux[k] = vetor[i]
i++
k++
}
enquanto(j <= fim){
aux[k] = vetor[j]
j++
k++
}
para(i = ini; i <= fim; i++)
vetor[i] = aux[i]
}
escreva("\nVetor: ", ini, " até ", fim, ": ")
imprimir_vetor(vetor)
}
funcao inicio(){
inteiro vetor[tamanho] = {5,7,9,1,3,2,4,8,6}
escreva("Vetor original: ")
imprimir_vetor(vetor)
merge_sort(vetor, 0, tamanho - 1)
escreva("\nVetor ordenado: ")
imprimir_vetor(vetor)
}
}
