Ícone do site estude.org

Algoritmo Merge Sort – Implementação em Java, C e Python

estude.org
Algoritmo Merge Sort - Implementação em Java, C e Python

O Merge Sort é um dos algoritmos de ordenação mais eficientes. Ele funciona com base no princípio de Dividir para Conquistar, baseado na ideia de dividir uma lista em várias sub-listas até que cada sub-lista consista em um único elemento e, então, mesclar essas sub-listas de maneira que resulte em uma lista ordenada.

Regra de Funcionamento do Merge Sort

O conceito de Dividir para Conquistar envolve três passos:

  1. Dividir o problema em múltiplos subproblemas.
  2. Resolver os Subproblemas. A ideia é quebrar o problema em subproblemas atômicos, onde eles são de fato resolvidos.
  3. Combinar as soluções dos subproblemas para encontrar a solução do problema atual.

Portanto, a regra de funcionamento do Merge Sort envolve os seguintes passos:

  1. Dividir o array não ordenado em subarrays, cada um contendo um único elemento.
  2. Pegar pares adjacentes de arrays de um único elemento e mesclá-los para formar um array de 2 elementos.
  3. Repetir o processo até que um único array ordenado seja obtido.

Um array de Tamanho ‘N’ é dividido em duas partes, ‘N/2’ tamanho de cada. Então, esses arrays são divididos ainda mais até chegarmos a um único elemento. O caso base aqui é alcançar um único elemento. Quando o caso base é atingido, começamos a mesclar a parte esquerda e a parte direita e obtemos um array ordenado no final. O Merge Sort quebra repetidamente um array em vários subarrays até que cada subarray consista em um único elemento e mesclando esses subarrays de maneira que resulte em um array ordenado.

Implementações do Merge Sort

Vamos implementar o algoritmo de ordenação Merge Sort em Java, C e Python.

Implementação em Java

public class MergeSort {
    void merge(int arr[], int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;

        int L[] = new int[n1];
        int R[] = new int[n2];

        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];

        int i = 0, j = 0;

        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    void sort(int arr[], int l, int r) {
        if (l < r) {
            int m = l + (r - l) / 2;

            sort(arr, l, m);
            sort(arr, m + 1, r);

            merge(arr, l, m, r);
        }
    }

    public static void main(String args[]) {
        int arr[] = { 12, 11, 13, 5, 6, 7 };

        MergeSort ob = new MergeSort();
        ob.sort(arr, 0, arr.length - 1);

        System.out.println("Sorted array");
        for (int i = 0; i < arr.length; ++i)
            System.out.print(arr[i] + " ");
    }
}

Output:

Sorted array
5 6 7 11 12 13

Este código define uma classe MergeSort em Java que implementa o algoritmo de ordenação por mesclagem (Merge Sort). O Merge Sort é um algoritmo de ordenação eficiente baseado no princípio de dividir para conquistar. Aqui está o que cada parte do código faz:

Em resumo, este código ordena um array de inteiros usando o algoritmo Merge Sort e imprime o array ordenado na saída padrão. É um exemplo clássico de aplicação do princípio de dividir para conquistar para ordenação de dados.

Implementação em C

#include <stdio.h>
#include <stdlib.h>

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];

    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l+(r-l)/2;

        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);

        merge(arr, l, m, r);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr)/sizeof(arr[0]);

    mergeSort(arr, 0, arr_size - 1);

    printf("Sorted array is \n");
    for (int i=0; i < arr_size; i++)
        printf("%d ", arr[i]);
    return 0;
}

Output:

Sorted array is 
5 6 7 11 12 13

Este código é uma implementação do algoritmo de ordenação Merge Sort em C. Ele ordena um array de inteiros em ordem crescente. O código é dividido em três partes principais: a função merge, a função mergeSort e a função main. Aqui está o que cada parte faz:

Função merge

Função mergeSort

Função main

Em resumo, este código demonstra como aplicar o algoritmo Merge Sort para ordenar um array de inteiros em C. O algoritmo Divide e Conquista é exemplificado aqui pela divisão do problema de ordenação em problemas menores (ordenando subarrays menores) e pela combinação de suas soluções (mesclando subarrays ordenados) para resolver o problema maior (ordenar o array inteiro).

Implementação em Python

def mergeSort(arr):
    if len(arr) > 1:
        mid = len(arr)//2  # Encontra o ponto médio do array
        L = arr[:mid]  # Dividindo a parte esquerda
        R = arr[mid:]  # Dividindo a parte direita

        mergeSort(L)  # Ordenando a primeira metade
        mergeSort(R)  # Ordenando a segunda metade

        i = j = k = 0

        # Mescla os arrays temporários de volta para arr[]
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        # Verifica se algum elemento foi deixado
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

# Teste da função
arr = [12, 11, 13, 5, 6, 7]
mergeSort(arr)
print("Sorted array is:", arr)

Este código define uma função mergeSort que ordena um array (arr) em ordem crescente usando o algoritmo Merge Sort. O algoritmo divide o array em dois subarrays, ordena esses subarrays (recursivamente) e, em seguida, mescla os subarrays ordenados.

  1. Divisão do Array: Divide o array dado pela metade até que subarrays de um único elemento sejam alcançados.
  2. Ordenação e Mesclagem: Ordena e mescla esses subarrays para formar um array ordenado, comparando os elementos dos subarrays e os colocando na posição correta no array original.

Ao final, quando você executa a função mergeSort com o array de exemplo e imprime o array ordenado, o output será:

Sorted array is: [5, 6, 7, 11, 12, 13]

Complexidade de Tempo e Espaço do Merge Sort

  1. Complexidade de Espaço
    Espaço Auxiliar: O(n) Ordenação In Loco: Não Algoritmo: Dividir para Conquistar
  2. Complexidade de Tempo
    O Merge Sort é um algoritmo recursivo e sua complexidade de tempo pode ser expressa pela seguinte relação de recorrência: T(n) = 2T(n/2) + O(n). A solução da recorrência acima é O(nLogn). A lista de tamanho N é dividida em no máximo Logn partes, e a mesclagem de todas as sub-listas em uma única lista leva O(N) de tempo, portanto, o tempo de execução no pior caso deste algoritmo é O(nLogn).

A complexidade de tempo do MergeSort é O(n*Log n) nos 3 casos (pior, médio e melhor), pois o mergesort sempre divide o array em duas metades e leva um tempo linear para mesclar duas metades.

Resumo

Até agora, discutimos vários aspectos do algoritmo de ordenação Merge Sort, incluindo implementações em diferentes linguagens de programação, sua complexidade de tempo e espaço, e oferecemos uma análise sobre a eficácia do algoritmo. Aqui está um resumo dos pontos principais:

Implementações do Merge Sort

Complexidade de Tempo e Espaço

Análise

Conclusão

Sair da versão mobile