Taller

Codificación de algoritmo

• Registre su aporte con una descripción de la manera en que desarrolló y cuál es el resultado:

Consiste en implementar el algoritmo Merge Sort en Java. El desarrollo se realizó en dos partes principales: la función merge y la función mergeSort.

La función merge toma un arreglo A y fusiona los dos subarreglos ordenados A[p...q] y A[q+1...r] en un solo subarreglo ordenado A[p...r]. Para ello, utiliza arreglos temporales para guardar los subarreglos, luego los fusiona de vuelta en el arreglo original en orden ordenado. El resultado final es que los elementos en el rango A[p...r] están ordenados. Por ejemplo, si tuviéramos el arreglo {10, 12, 20, 5, 18, 22} con p=0, q=2 y r=5, la función merge lo modificaría de tal manera que el subarreglo resultante sería {5, 10, 12, 18, 20, 22}.

La función mergeSort, por su parte, implementa el algoritmo de ordenamiento Merge Sort. Este algoritmo funciona dividiendo recursivamente el arreglo en mitades más pequeñas hasta que cada subarreglo contiene un solo elemento (que se considera ordenado). Luego, la función merge se utiliza para fusionar estas mitades de manera ordenada, construyendo recursivamente arreglos ordenados más grandes hasta que todo el arreglo original esté ordenado. Así, mergeSort utiliza merge como una subrutina para lograr el ordenamiento completo del arreglo.

public class MergeSort {
    
    // Método para fusionar dos subarreglos
    public static void merge(int[] A, int p, int q, int r) {
        int nL = q - p + 1; // Longitud del subarreglo izquierdo
        int nR = r - q;      // Longitud del subarreglo derecho
        
        // Crear arreglos temporales
        int[] L = new int[nL];
        int[] R = new int[nR];
        
        // Copiar los elementos a los arreglos temporales
        for (int i = 0; i < nL; i++) {
            L[i] = A[p + i]; // Copiar A[p:q] a L
        }
        for (int j = 0; j < nR; j++) {
            R[j] = A[q + 1 + j]; // Copiar A[q+1:r] a R
        }
        
        // Índices para L, R y A
        int i = 0, j = 0, k = p;
        
        // Fusionar los arreglos temporales de nuevo en A
        while (i < nL && j < nR) {
            if (L[i] <= R[j]) {
                A[k] = L[i];
                i++;
            } else {
                A[k] = R[j];
                j++;
            }
            k++;
        }
        
        // Copiar los elementos restantes de L, si hay
        while (i < nL) {
            A[k] = L[i];
            i++;
            k++;
        }
        
        // Copiar los elementos restantes de R, si hay
        while (j < nR) {
            A[k] = R[j];
            j++;
            k++;
        }
    }

    // Método para realizar Merge Sort
    public static void mergeSort(int[] A, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2; // Encontrar el punto medio
            
            // Llamadas recursivas para dividir
            mergeSort(A, left, mid);
            mergeSort(A, mid + 1, right);
            
            // Fusionar las dos mitades
            merge(A, left, mid, right);
        }
    }

    public static void main(String[] args) {
        int[] array = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("Array original:");
        for (int num : array) {
            System.out.print(num + " ");
        }
        
        // Aplicar Merge Sort
        mergeSort(array, 0, array.length - 1);
        
        System.out.println("\nArray ordenado:");
        for (int num : array) {
       
     System.out.print(num + " ");
        }
    }
}