Implementación recursiva de Merge Sort en Java

Introducción

Merge Sort es un algoritmo de clasificación eficiente y estable que utiliza la técnica Divide y Vencerás para clasificar una matriz. En este laboratorio, aprenderá a implementar Merge Sort en Java utilizando un enfoque recursivo.

Skills Graph

Crea un método de Merge Sort

Crea un método público estático llamado mergeSort() con tres parámetros enteros, int arrToSort[], startIdx, endIdx. Debes comprobar si la longitud del array es menor que 2, y en ese caso retornar. De lo contrario, calcular el índice medio del array y dividir el array en dos mitades izquierda y derecha. Las mitades izquierda y derecha también deben ser divididas recursivamente. Después de dividirlas, tienes que fusionarlas para formar un array ordenado.

public static void mergeSort(int[] arrToSort, int startIdx, int endIdx) {
    if (startIdx >= endIdx) {
        return;
    }

    int midIdx = startIdx + (endIdx - startIdx) / 2;
    mergeSort(arrToSort, startIdx, midIdx);
    mergeSort(arrToSort, midIdx + 1, endIdx);
    merge(arrToSort, startIdx, midIdx, endIdx);
}

Crea un método de fusión

Crea otro método público estático llamado merge() con cuatro parámetros: int arrToSort[], startIdx, midIdx y endIdx. Debes inicializar los arrays izquierdo y derecho. Luego, debes fusionar ambos arrays comparando los elementos de cada array y fusionándolos en un solo array.

public static void merge(int[] arrToSort, int startIdx, int midIdx, int endIdx) {
    int[] leftArr = new int[midIdx - startIdx + 1];
    int[] rightArr = new int[endIdx - midIdx];

    for (int i = 0; i < leftArr.length; i++) {
        leftArr[i] = arrToSort[startIdx + i];
    }
    for (int i = 0; i < rightArr.length; i++) {
        rightArr[i] = arrToSort[midIdx + i + 1];
    }

    int leftArrIdx = 0, rightArrIdx = 0, sortedArrIdx = startIdx;
    while ((leftArrIdx < leftArr.length) && (rightArrIdx < rightArr.length)) {
        if (leftArr[leftArrIdx] < rightArr[rightArrIdx]) {
            arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
            leftArrIdx += 1;
        } else {
            arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
            rightArrIdx += 1;
        }
        sortedArrIdx += 1;
    }

    while (leftArrIdx < leftArr.length) {
        arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
        leftArrIdx += 1;
        sortedArrIdx += 1;
    }

    while (rightArrIdx < rightArr.length) {
        arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
        rightArrIdx += 1;
        sortedArrIdx += 1;
    }
}

Prueba Merge Sort

Vamos a probar el método mergeSort() escribiendo código para ordenar una matriz de entrada. Crea un método principal. Luego, declara una matriz de enteros con algunos valores no ordenados. Llama al método mergeSort() y pasa la matriz no ordenada a él. Finalmente, imprime la matriz ordenada en la consola. El bloque de código para este paso se verá así:

public static void main(String[] args) {
    int[] arrToSort = { 4, 2, 8, 0, 1, 6 };
    mergeSort(arrToSort, 0, arrToSort.length - 1);
    System.out.println(Arrays.toString(arrToSort));
}

Después de ejecutar el programa, la salida debe ser: [0, 1, 2, 4, 6, 8].

Prueba con matriz vacía

Crea otra prueba para una matriz vacía. Declara una matriz de enteros vacía. Llama al método mergeSort() y pásale la matriz vacía. Finalmente, imprime la matriz ordenada en la consola. El bloque de código para este paso se verá así:

int[] emptyArr = {};
mergeSort(emptyArr, 0, emptyArr.length - 1);
System.out.println(Arrays.toString(emptyArr));

La salida debe ser la misma que la entrada.

Prueba con matriz de un solo elemento

Crea una prueba más con una matriz de un solo elemento. Declara una matriz de enteros de un solo elemento. Llama al método mergeSort() y pásale la matriz de un solo elemento. Finalmente, imprime la matriz ordenada en la consola. El bloque de código para este paso se verá así:

int[] singleElementArr = {7};
mergeSort(singleElementArr, 0, singleElementArr.length - 1);
System.out.println(Arrays.toString(singleElementArr));

La salida debe ser la misma que la entrada.

Prueba con valores negativos

Crea otra prueba para una matriz que consta de enteros negativos. Declara una matriz de enteros que incluye algunos enteros negativos. Llama al método mergeSort() y pasa la matriz como argumento. Finalmente, imprime la matriz ordenada en la consola. El bloque de código para este paso se verá así:

int[] arrWithNegatives = {-7, 2, -9, 0, -1, 6, 8};
mergeSort(arrWithNegatives, 0, arrWithNegatives.length - 1);
System.out.println(Arrays.toString(arrWithNegatives));

Después de ejecutar el programa, la salida debe ser: [-9, -7, -1, 0, 2, 6, 8].

Prueba con elementos no numéricos

Crea otra prueba ordenando una matriz de elementos no numéricos. Declara una matriz de cadenas. Llama al método mergeSort() y pasa la matriz como argumento. Finalmente, imprime la matriz ordenada en la consola. El bloque de código para este paso se verá así:

String[] strsToSort = {"John", "David", "Emily", "Bob", "Christine"};
mergeSort(strsToSort, 0, strsToSort.length - 1);
System.out.println(Arrays.toString(strsToSort));

Después de ejecutar el programa, la salida debe ser: ['Bob', 'Christine', 'David', 'Emily', 'John'].

需要注意的是，这里英文输出的格式是因为代码块要求保持英文，实际西班牙语中数组元素的表示一般不用单引号，而是用双引号。完整准确的输出应该是：Después de ejecutar el programa, la salida debe ser: ["Bob", "Christine", "David", "Emily", "John"] 。但按照题目要求，代码块内保持英文，所以整体翻译后的文档呈现上述内容。

Código fuente final

A continuación se presenta el código fuente final para Merge Sort:

import java.util.Arrays;

public class MergeSort {
   public static void mergeSort(int[] arrToSort, int startIdx, int endIdx) {
       if (startIdx >= endIdx) {
           return;
       }

       int midIdx = startIdx + (endIdx - startIdx) / 2;
       mergeSort(arrToSort, startIdx, midIdx);
       mergeSort(arrToSort, midIdx + 1, endIdx);
       merge(arrToSort, startIdx, midIdx, endIdx);
   }

   public static void merge(int[] arrToSort, int startIdx, int midIdx, int endIdx) {
       int[] leftArr = new int[midIdx - startIdx + 1];
       int[] rightArr = new int[endIdx - midIdx];

       for (int i = 0; i < leftArr.length; i++) {
           leftArr[i] = arrToSort[startIdx + i];
       }

       for (int i = 0; i < rightArr.length; i++) {
           rightArr[i] = arrToSort[midIdx + i + 1];
       }

       int leftArrIdx = 0, rightArrIdx = 0, sortedArrIdx = startIdx;
       while ((leftArrIdx < leftArr.length) && (rightArrIdx < rightArr.length)) {
           if (leftArr[leftArrIdx] < rightArr[rightArrIdx]) {
               arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
               leftArrIdx += 1;
           } else {
               arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
               rightArrIdx += 1;
           }
           sortedArrIdx += 1;
       }

       while (leftArrIdx < leftArr.length) {
           arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
           leftArrIdx += 1;
           sortedArrIdx += 1;
       }

       while (rightArrIdx < rightArr.length) {
           arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
           rightArrIdx += 1;
           sortedArrIdx += 1;
       }
   }

   public static void main(String[] args) {
       //create an unsorted integer array
       int[] arrToSort = { 4, 2, 8, 0, 1, 6 };
       //sort the integer array using Merge Sort
       mergeSort(arrToSort, 0, arrToSort.length - 1);
       //print the sorted array
       System.out.println(Arrays.toString(arrToSort));

       //create an empty integer array
       int[] emptyArr = {};
       //sort the empty array
       mergeSort(emptyArr, 0, emptyArr.length - 1);
       //print the sorted array
       System.out.println(Arrays.toString(emptyArr));

       //create a single-element array
       int[] singleElementArr = {7};
       //sort the single-element array
       mergeSort(singleElementArr, 0, singleElementArr.length - 1);
       //print the sorted array
       System.out.println(Arrays.toString(singleElementArr));

       //create a negative integer array
       int[] arrWithNegatives = {-7, 2, -9, 0, -1, 6, 8};
       //sort the negative integer array
       mergeSort(arrWithNegatives, 0, arrWithNegatives.length - 1);
       //print the sorted array
       System.out.println(Arrays.toString(arrWithNegatives));

       //create a string array
       String[] strsToSort = {"John", "David", "Emily", "Bob", "Christine"};
       //sort the string array
       mergeSort(strsToSort, 0, strsToSort.length - 1);
       //print the sorted array
       System.out.println(Arrays.toString(strsToSort));
   }
}

Ejecuta el programa

Compila y ejecuta el programa usando la terminal:

javac MergeSort.java && java MergeSort

Resumen

En este laboratorio, aprendiste qué es Merge Sort, cómo funciona y cómo implementarlo en Java. Creaste dos métodos públicos estáticos, mergeSort() y merge() para dividir y fusionar la matriz de entrada respectivamente. Después de la implementación, la probaste con varios tipos de entrada, discutiste la complejidad temporal y espacial y verificaste su funcionalidad. ¡Felicitaciones! Has completado con éxito el laboratorio de Merge Sort en Java.