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:

1. Divisão: A lista de elementos é dividida ao meio recursivamente até que cada sublista contenha apenas um elemento.
2. Ordenação: Cada sublista é ordenada separadamente, utilizando o mesmo processo de divisão e conquista.
3. 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

1. 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.
2. Estabilidade: O Merge Sort é um algoritmo estável, o que significa que ele preserva a ordem relativa de elementos com chaves iguais.
3. 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.
4. 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.

1. 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.
2. 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 MergeSort e MergeSortRecursive.

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