Introducció a l'Algorisme d'Ordenació Merge Sort

Introducció a l'Algorisme d'Ordenació Merge Sort

L'algorisme d'ordenació Merge Sort és un mètode eficient, general i comparatiu per a ordenar llistes o arrays. És un exemple clàssic d'un algorisme "divideix i venceràs". Merge Sort divideix el conjunt de dades en meitats més petites, les ordena i després les fusiona de nou en una sola llista ordenada.

El principal avantatge d'usar Merge Sort és la seva eficiència consistent, que és particularment útil quan es manegen grans conjunts de dades. El seu temps d'execució és generalment de O(n * log n)*, la qual cosa ho fa significativament més ràpid que algorismes d'ordenació simples com Bubble Sort o Insertion Sort, especialment en llistes grans.

Merge Sort és un algorisme d'ordenació estable, cosa que significa que si dos elements tenen el mateix valor, conserva l'ordre original en què apareixen. Això és crucial en situacions on l'ordre dels elements iguals ha de mantenir-se, per exemple, en llistes d'esdeveniments que han de seguir un ordre cronològic específic, fins i tot si ocorren en la mateixa data.

cta:cloud_so

A continuació, vam mostrar com s'implementa l'algorisme de Merge Sort en tres llenguatges de programació diferents: Python, C i Java.

Implementació de Merge Sort en Python

def merge_sort(arr): if len(arr) > 1: mid = len(arr) // 2 L = arr[:mid] R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

        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

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

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

# Exemple d'ús
arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr)
print("Array ordenado:", arr)

Implementació de Merge Sort en 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("Array ordenado: \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\n");
    for (int i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);
    printf("\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\n");

    return 0;
}

Implementació de Merge Sort en 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("Array ordenado:");
        for (int i = 0; i < arr.length; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}

En conclusió, Merge Sort és un algorisme d'ordenació altament eficient i fiable, ideal per a manejar grans volums de dades a causa de la seva complexitat temporal consistent de O(n * log n)*.

Encara que la seva implementació pot ser lleugerament més complexa que altres algorismes més simples d'ordenació, els beneficis del seu rendiment i fiabilitat justifiquen el seu ús en entorns que demanden alta eficiència i precisió. En resum, triar Merge Sort és optar per una solució robusta i eficaç en el camp dels algorismes d'ordenació.

cta:hosting