Merge Sort: O Método Eficaz de Ordenação
Fala galera da programação, tudo beleza?
Hoje vamos descobrir a eficiência do Merge Sort: um método de ordenação poderoso baseado em divisão e conquista. Aprenda como este algoritmo proporciona estabilidade e rapidez na ordenação de grandes conjuntos de dados.
Introdução
Ordenar uma lista de elementos é uma tarefa comum em programação e ciência da computação. Existem várias abordagens para ordenação, cada uma com suas vantagens e desvantagens. Uma dessas abordagens é o algoritmo Merge Sort, conhecido por sua eficiência e simplicidade. Neste artigo, exploraremos o funcionamento do Merge Sort, suas características principais e por que ele é uma escolha popular para ordenação de dados.
O Que É o Merge Sort?
O Merge Sort é um algoritmo de ordenação baseado no paradigma de divisão e conquista. Ele divide a lista de elementos em partes menores, ordena essas partes de forma independente e depois combina as partes ordenadas para obter a lista final ordenada. Esse processo é repetido recursivamente até que a lista esteja completamente ordenada.
Como Funciona o Merge Sort?
O Merge Sort opera em três etapas principais:
- Divisão: A lista de elementos é dividida ao meio recursivamente até que cada sublista contenha apenas um elemento.
- Ordenação: Cada sublista é ordenada separadamente, utilizando o mesmo processo de divisão e conquista.
- Combinação: As sublistas ordenadas são combinadas de forma a produzir uma única lista ordenada.
Implementação do Merge Sort
A implementação do Merge Sort geralmente é feita de forma recursiva. Aqui está uma versão básica em pseudocódigo:
mergeSort(lista):
se tamanho da lista for menor ou igual a 1:
retorne lista
divida a lista ao meio em sublistas esquerda e direita
lista_esquerda = mergeSort(sublista esquerda)
lista_direita = mergeSort(sublista direita)
retorne merge(lista_esquerda, lista_direita)
merge(lista_esquerda, lista_direita):
crie uma lista vazia resultado
enquanto lista_esquerda e lista_direita não estiverem vazias:
se o primeiro elemento de lista_esquerda for menor que o primeiro elemento de lista_direita:
adicione o primeiro elemento de lista_esquerda ao resultado
remova o primeiro elemento de lista_esquerda
senão:
adicione o primeiro elemento de lista_direita ao resultado
remova o primeiro elemento de lista_direita
adicione os elementos restantes de lista_esquerda ao resultado
adicione os elementos restantes de lista_direita ao resultado
retorne resultado
Exemplo em Python
'''
Criado pelo Professor Giovani Da Cruz
https://giovanidacruz.com.br
'''
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
merge_sort(left_half)
merge_sort(right_half)
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
def main():
arr = [12, 11, 13, 5, 6, 7]
print("Array original:", arr)
merge_sort(arr)
print("Array ordenado:", arr)
if __name__ == "__main__":
main()
Esta implementação do Merge Sort recebe uma lista de números como entrada e ordena essa lista em ordem crescente.
Exemplo em Rust
/******************************************************************************
Criado pelo professor Giovani Da Cruz
https://giovanidacruz.com.br
*******************************************************************************/
fn merge_sort(arr: &mut [i32]) {
let n = arr.len();
if n > 1 {
let mid = n / 2;
let mut left_half = arr[..mid].to_vec();
let mut right_half = arr[mid..].to_vec();
merge_sort(&mut left_half);
merge_sort(&mut right_half);
let (mut i, mut j, mut k) = (0, 0, 0);
while i < left_half.len() && j < right_half.len() {
if left_half[i] < right_half[j] {
arr[k] = left_half[i];
i += 1;
} else {
arr[k] = right_half[j];
j += 1;
}
k += 1;
}
while i < left_half.len() {
arr[k] = left_half[i];
i += 1;
k += 1;
}
while j < right_half.len() {
arr[k] = right_half[j];
j += 1;
k += 1;
}
}
}
fn main() {
let mut arr = [12, 11, 13, 5, 6, 7];
println!("Array original: {:?}", arr);
merge_sort(&mut arr);
println!("Array ordenado: {:?}", arr);
}
Esta implementação do Merge Sort em Rust é bastante semelhante à versão em Python. Ela ordena uma fatia mutável de números inteiros em ordem crescente.
Exemplo em Go
/******************************************************************************
Criado pelo professor Giovani Da Cruz
https://giovanidacruz.com.br
*******************************************************************************/
package main
import "fmt"
func mergeSort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
mid := len(arr) / 2
leftHalf := mergeSort(arr[:mid])
rightHalf := mergeSort(arr[mid:])
return merge(leftHalf, rightHalf)
}
func merge(left, right []int) []int {
result := make([]int, 0, len(left)+len(right))
leftIndex, rightIndex := 0, 0
for leftIndex < len(left) && rightIndex < len(right) {
if left[leftIndex] < right[rightIndex] {
result = append(result, left[leftIndex])
leftIndex++
} else {
result = append(result, right[rightIndex])
rightIndex++
}
}
result = append(result, left[leftIndex:]...)
result = append(result, right[rightIndex:]...)
return result
}
func main() {
arr := []int{12, 11, 13, 5, 6, 7}
fmt.Println("Array original:", arr)
sortedArr := mergeSort(arr)
fmt.Println("Array ordenado:", sortedArr)
}
Esta implementação do Merge Sort em Go recebe uma fatia de inteiros como entrada e retorna a fatia ordenada em ordem crescente. Ela utiliza recursão para dividir a fatia em partes menores, ordena essas partes e, em seguida, mescla as partes ordenadas para obter a fatia final ordenada.
Vantagens do Merge Sort
- Eficiência: O Merge Sort possui uma complexidade de tempo de O(n log n), onde n é o número de elementos na lista. Isso o torna eficiente mesmo para grandes conjuntos de dados.
- Estabilidade: O Merge Sort é um algoritmo estável, o que significa que ele preserva a ordem relativa de elementos com chaves iguais.
- Adaptabilidade: O Merge Sort é particularmente eficiente em cenários onde os dados estão armazenados em estruturas de dados externas, como arquivos, devido à sua natureza de dividir e combinar.
- Paralelismo: O Merge Sort pode ser facilmente paralelizado, o que permite que seja executado de forma mais rápida em sistemas com múltiplos núcleos de processamento.
Comparativo entre o BubbleSort e o MergeSort em Pascal
{
Criado pelo professor Giovani Da Cruz
https://giovanidacruz.com.br
}
program Ordenacao;
uses
SysUtils, DateUtils;
type
IntArray = array of Integer;
TMyProc = procedure (var arr: IntArray);
procedure BubbleSort(var arr: IntArray);
var
i, j, temp: Integer;
begin
for i := 0 to Length(arr) - 1 do
begin
for j := 0 to Length(arr) - i - 2 do
begin
if arr[j] > arr[j + 1] then
begin
temp := arr[j];
arr[j] := arr[j + 1];
arr[j + 1] := temp;
end;
end;
end;
end;
procedure MergeSort(var arr: IntArray);
procedure Merge(var arr: IntArray; low, mid, high: Integer);
var
leftIdx, rightIdx, mergeIdx: Integer;
leftSize, rightSize: Integer;
leftArr, rightArr: array of Integer;
begin
leftSize := mid - low + 1;
rightSize := high - mid;
SetLength(leftArr, leftSize);
SetLength(rightArr, rightSize);
for leftIdx := 0 to leftSize - 1 do
leftArr[leftIdx] := arr[low + leftIdx];
for rightIdx := 0 to rightSize - 1 do
rightArr[rightIdx] := arr[mid + 1 + rightIdx];
leftIdx := 0;
rightIdx := 0;
mergeIdx := low;
while (leftIdx < leftSize) and (rightIdx < rightSize) do
begin
if leftArr[leftIdx] <= rightArr[rightIdx] then
begin
arr[mergeIdx] := leftArr[leftIdx];
Inc(leftIdx);
end
else
begin
arr[mergeIdx] := rightArr[rightIdx];
Inc(rightIdx);
end;
Inc(mergeIdx);
end;
while leftIdx < leftSize do
begin
arr[mergeIdx] := leftArr[leftIdx];
Inc(leftIdx);
Inc(mergeIdx);
end;
while rightIdx < rightSize do
begin
arr[mergeIdx] := rightArr[rightIdx];
Inc(rightIdx);
Inc(mergeIdx);
end;
end;
procedure MergeSortRecursive(var arr: IntArray; low, high: Integer);
var
mid: Integer;
begin
if low < high then
begin
mid := (low + high) div 2;
MergeSortRecursive(arr, low, mid);
MergeSortRecursive(arr, mid + 1, high);
Merge(arr, low, mid, high);
end;
end;
begin
MergeSortRecursive(arr, 0, Length(arr) - 1);
end;
function GenerateRandomArray(size: Integer): IntArray;
var
arr: IntArray;
i: Integer;
begin
SetLength(arr, size);
for i := 0 to size - 1 do
arr[i] := Random(1000) + 1;
GenerateRandomArray := arr;
end;
procedure TestSortingAlgorithm(algorithm: TMyProc; arraySizes: array of Integer);
var
arr: IntArray;
i, size: Integer;
startTime, endTime: TDateTime;
begin
for i := Low(arraySizes) to High(arraySizes) do
begin
size := arraySizes[i];
arr := GenerateRandomArray(size);
startTime := Now;
algorithm(arr);
endTime := Now;
Writeln(Format('%16d | %16d | ', [size, MilliSecondsBetween(endTime, startTime)]));
end;
end;
var
arraySizes: array of Integer;
begin
Randomize;
SetLength(arraySizes, 4);
arraySizes[0] := 100;
arraySizes[1] := 1000;
arraySizes[2] := 10000;
arraySizes[3] := 30000;
Writeln('Comparativo de tempo de execução:');
Writeln('Tamanho do Array | Bubble Sort (ms) ');
TestSortingAlgorithm(@BubbleSort, arraySizes);
Writeln('Comparativo de tempo de execução:');
Writeln('Tamanho do Array | Merge Sort (ms)');
TestSortingAlgorithm(@MergeSort, arraySizes);
Writeln('Enter para finalizar!');
Readln;
end.
Explicação
Este programa em Pascal compara os tempos de execução de dois métodos de ordenação: Bubble Sort e Merge Sort.
- Bubble Sort: O Bubble Sort é um algoritmo simples de ordenação que percorre repetidamente a lista, compara elementos adjacentes e os troca se estiverem na ordem errada. Esse processo é repetido até que a lista esteja ordenada. No caso deste programa, a implementação do Bubble Sort é feita na função
BubbleSort. - Merge Sort: Como já comentado no artigo, o Merge Sort é um algoritmo de ordenação eficiente que divide recursivamente a lista ao meio, ordena as duas metades separadamente e, em seguida, mescla as partes ordenadas para produzir a lista final ordenada. No caso deste programa, a implementação do Merge Sort é feita nas funções
MergeSorteMergeSortRecursive.
O programa começa definindo tipos de dados e procedimentos necessários para os métodos de ordenação. Em seguida, define uma função para gerar um array de inteiros aleatórios. A função TestSortingAlgorithm é responsável por testar os algoritmos de ordenação com diferentes tamanhos de array e medir o tempo de execução de cada um.
Por fim, o programa define os tamanhos dos arrays a serem testados e executa os testes para comparar os tempos de execução do Bubble Sort e do Merge Sort para cada tamanho de array. Os resultados são impressos no console para análise.
Este programa é uma ferramenta útil para comparar o desempenho de diferentes algoritmos de ordenação em diferentes cenários de entrada. Ele fornece uma maneira eficiente de avaliar a eficácia dos algoritmos e escolher o mais adequado para uma determinada situação.
Conclusão
O Merge Sort é um método eficaz e amplamente utilizado para ordenar listas de elementos. Sua eficiência, estabilidade e adaptabilidade o tornam uma escolha popular para uma variedade de aplicações. Ao entender os princípios básicos do Merge Sort e suas características, os programadores podem tomar decisões informadas sobre a escolha do algoritmo de ordenação mais adequado para suas necessidades específicas.
#MergeSort
#Ordenação
#EficiênciaComputacional
#GiovaniDaCruz
