Taller: Implementación de un Algoritmo de Ordenamiento

Descripción del Trabajo

Este taller consistió en la codificación del algoritmo de ordenamiento Merge Sort utilizando el lenguaje de programación Java. El proceso se dividió en dos funciones esenciales: merge y mergeSort.

• merge: Esta función se encarga de combinar dos subarreglos previamente ordenados, que se encuentran dentro del arreglo principal A en los rangos A[p...q] y A[q+1...r]. Para ello, se crean arreglos temporales que almacenan cada mitad y luego se fusionan manteniendo el orden.
  Por ejemplo, si se tiene el arreglo {10, 12, 20, 5, 18, 22} con p = 0, q = 2 y r = 5, el resultado de aplicar merge sería {5, 10, 12, 18, 20, 22}.

• mergeSort: Esta es la función principal que implementa el algoritmo Merge Sort mediante recursión. El arreglo se divide en mitades más pequeñas hasta que cada subarreglo tiene un solo elemento (considerado ordenado). Luego, estas mitades se fusionan usando merge, formando arreglos ordenados más grandes hasta ordenar completamente el arreglo inicial.

---

Código en Java

public class MergeSort {

    // Método para combinar dos subarreglos ordenados
    public static void merge(int[] A, int p, int q, int r) {
        int tamIzq = q - p + 1;
        int tamDer = r - q;

        int[] izquierda = new int[tamIzq];
        int[] derecha = new int[tamDer];

        // Copiar datos a arreglos temporales
        for (int i = 0; i < tamIzq; i++) {
            izquierda[i] = A[p + i];
        }
        for (int j = 0; j < tamDer; j++) {
            derecha[j] = A[q + 1 + j];
        }

        int i = 0, j = 0, k = p;

        // Fusionar los arreglos ordenadamente
        while (i < tamIzq && j < tamDer) {
            if (izquierda[i] <= derecha[j]) {
                A[k] = izquierda[i];
                i++;
            } else {
                A[k] = derecha[j];
                j++;
            }
            k++;
        }

        // Copiar elementos restantes de izquierda (si hay)
        while (i < tamIzq) {
            A[k] = izquierda[i];
            i++;
            k++;
        }

        // Copiar elementos restantes de derecha (si hay)
        while (j < tamDer) {
            A[k] = derecha[j];
            j++;
            k++;
        }
    }

    // Función recursiva que aplica Merge Sort
    public static void mergeSort(int[] A, int inicio, int fin) {
        if (inicio < fin) {
            int medio = (inicio + fin) / 2;
            mergeSort(A, inicio, medio);
            mergeSort(A, medio + 1, fin);
            merge(A, inicio, medio, fin);
        }
    }

    public static void main(String[] args) {
        int[] datos = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("Arreglo original:");
        for (int n : datos) {
            System.out.print(n + " ");
        }

        // Aplicar Merge Sort
        mergeSort(datos, 0, datos.length - 1);

        System.out.println("\nArreglo ordenado:");
        for (int n : datos) {
            System.out.print(n + " ");
        }
    }
}