Cómo ordenar una matriz en Java

La clasificación es una de las operaciones más comunes y necesarias en programación. Representa la ordenación de algún conjunto de elementos en un orden específico. Este artículo trata sobre métodos estándar para ordenar matrices en Java.

Brevemente sobre la clasificación

Entonces, ordenar es ordenar un conjunto de datos. En nuestro caso, matrices. El propósito de ordenar matrices u otras estructuras de datos es facilitar la búsqueda, manipulación o análisis de los datos de la colección. Los programadores necesitan ordenar con tanta frecuencia que cualquier lenguaje de programación incluye métodos integrados para ordenar matrices, listas y otras estructuras de datos ordenadas. Para utilizar dichos métodos, llámelos. La operación se simplifica al máximo. Por lo general, los métodos integrados están optimizados al máximo; en la mayoría de los casos, utilizarlos para su trabajo o proyectos es una buena idea. Sin embargo, casi todos los programadores, durante sus estudios, necesitan implementar algoritmos de clasificación por sí mismos. Por tanto, estos ejercicios perfectos te enseñan a comprender la esencia misma de la programación. Además, a veces se necesitan métodos de clasificación no estándar en el trabajo. Hay muchos algoritmos de clasificación. Tienen fortalezas y debilidades según el tipo o tamaño de los conjuntos de datos. Los algoritmos de clasificación estándar incluyen clasificación por burbujas, clasificación por selección, clasificación por inserción, clasificación por combinación y clasificación rápida.

Método incorporado para ordenar matrices en Java: Arrays.sort

Empecemos por lo más sencillo. Alguien ya ha escrito un método para ordenar matrices en Java para nosotros. Este método está en la clase Arrays , más específicamente java.util.Arrays . Esta clase contiene varios métodos para trabajar con matrices, como ordenar y buscar. El método Arrays.sort proporciona una manera conveniente de ordenar matrices en Java, ya sea que contengan cadenas, números enteros u otros elementos. Existen varias variaciones del método Arrays.sort en Java. A continuación se muestran algunos métodos de clasificación de uso común de la clase Arrays :

• Arrays.sort(Array) : úselo para ordenar matrices de tipos u objetos primitivos en orden ascendente. Utiliza el orden natural de los elementos.
• Arrays.sort(Array, fromIndex, toIndex) : este método de clasificación sobrecargado le permite ordenar solo una parte de la matriz especificada por los parámetros fromIndex y toIndex.
• Arrays.sort(Array, comparador) : este es para ordenar matrices de objetos usando un comparador personalizado. El comparador define el orden de los elementos.
• Arrays.parallelSort(Array) : esta versión del método ordena el Array en paralelo, utilizando múltiples subprocesos para mejorar el rendimiento. Es beneficioso para ordenar matrices grandes.
• Arrays.parallelSort(Array, fromIndex, toIndex) : esta versión sobrecargada del método paraleloSort permite ordenar un rango específico de elementos en el Array .

Le permiten organizar rápidamente los elementos según su orden natural o utilizando un comparador personalizado. Exploremos este método con dos ejemplos, uno que involucra cadenas.

Ejemplo 1: ordenar cadenas

Supongamos que tenemos una variedad de instrumentos musicales de cuerda: "violín", "viola", "violonchelo" y "contrabajo". Podemos utilizar el método Array.sort para ordenarlos alfabéticamente.

import java.util.Arrays;
//Arrays.sort example
public class StringSortExample {
    public static void main(String[] args) {
        String[] instruments = {"violin", "viola", "cello", "double bass"};

        Arrays.sort(instruments);

        System.out.println("Sorted Instruments:");
        for (String instrument : instruments) {
            System.out.println(instrument);
        }
    }
}

El resultado está aquí: En este programa, primero importamos la clase java.util.Arrays para obtener acceso al método Array.sort . Luego creamos una matriz de cuerdas llamada instrumentos que contiene los nombres de los instrumentos musicales. Después, llamamos Arrays.sort(instruments) . Entonces, este método obtiene una matriz y clasifica los elementos en orden ascendente según su orden natural (alfabético). Finalmente, recorremos el Array ordenado e imprimimos cada instrumento.

Ejemplo 2: ordenar números enteros

Consideremos otro ejemplo en el que ordenamos una matriz de números enteros en orden ascendente.

import java.util.Arrays;

public class IntegerSortExample {
    public static void main(String[] args) {
        int[] numbers = {8, 2, 7, 3, 1, 5};
//sort an array using Arrays.sort
        Arrays.sort(numbers);

        System.out.println("Sorted Numbers:");
        for (int number : numbers) {
            System.out.println(number);
        }
    }
}

Producción: Aquí creamos una matriz de enteros llamada números con varios elementos sin clasificar. A continuación, llamamos a Arrays.sort(numbers) para ordenar una matriz en orden ascendente. Tenga en cuenta que el método Array.sort modifica la matriz original in situ. Entonces, para conservar el Array original , haga una copia antes de ordenar.

Ejemplo 3: orden descendente

¿Qué pasa con el orden descendente? También es fácil con Arrays.sort . Simplemente use un comparador personalizado. He aquí un ejemplo:

import java.util.Arrays;
import java.util.Comparator;
//Arrays.sort with custom comparator example
public class DescendingSortExample {
    public static void main(String[] args) {
        Integer[] numbers = {8, 2, 7, 3, 1, 5};
        //sort an Array using Arrays.sort
        Arrays.sort(numbers, Comparator.reverseOrder());

        System.out.println("Sorted Numbers (Descending):");
        for (int number : numbers) {
            System.out.println(number);
        }
    }
}

El resultado es el siguiente: Aquí tenemos una serie de números enteros llamados números. Al pasar Comparator.reverseOrder() como segundo argumento del método Arrays.sort , especificamos un comparador personalizado que ordena los elementos en orden descendente. El método Comparator.reverseOrder() devuelve un comparador que invierte el orden natural de los elementos. Tenga en cuenta que aquí usamos la clase contenedora Integer en lugar del tipo int primitivo porque el método Comparator.reverseOrder() requiere objetos. Si tiene una matriz de valores int primitivos, también deberá convertirlos en objetos enteros antes de utilizar este enfoque. Con un comparador personalizado, puede ordenar fácilmente una matriz en orden descendente utilizando el método Arrays.sort en Java.

Algoritmos de clasificación clásicos autoescritos en Java

Ya has visto tareas de clasificación de matrices si estás estudiando Ciencias de la Computación de forma independiente o en la universidad. Existen muchos algoritmos de clasificación diferentes e implementaremos algunos de ellos en este artículo. Generalmente, cuanto más fácil es implementar un algoritmo, menos eficiente es. Los programadores miden la eficiencia de los algoritmos por el tiempo de su funcionamiento y la memoria que se gasta en recursos. Ese no es el tema de nuestro artículo, pero mencionamos que Arrays.sort en Java es un algoritmo eficaz.

Ordenamiento de burbuja

Comencemos con el algoritmo más popular entre los estudiantes: la clasificación por burbujas. Es sencillo: el algoritmo compara dos elementos y luego los intercambia si están en el orden incorrecto, y así sucesivamente hasta el final de la matriz. Resulta que los elementos más pequeños "flotan" hasta el final del Array , como burbujas de refresco hasta la parte superior.

public class BubbleSort {

       public static void bubbleSort(int[] myArray) {
           int n = myArray.length;
           for (int i = 0; i < n - 1; i++) {
               for (int j = 0; j < n - i - 1; j++) {
                   if (myArray[j] > myArray[j + 1]) {
                       // Swap myArray[j] and myArray[j+1]
                       int temp = myArray[j];
                       myArray[j] = myArray[j + 1];
                       myArray[j + 1] = temp;
                   }
               }
           }
       }

       public static void main(String[] args) {
           int[] arr = {18, 28, 2, 7, 90, 45};

           System.out.println("Array before sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }

           bubbleSort(arr);

           System.out.println("\nArray after sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }
       }
}

Aquí el método toma una matriz de números enteros como entrada. El bucle exterior va de 0 a n-1. Aquí n es el tamaño de la matriz. El bucle interior compara elementos adyacentes. Si el orden es incorrecto, el método los intercambia. Este procedimiento se repite hasta que se haya ordenado toda la matriz. Aquí hay un resultado de nuestro programa:

Orden de selección

El algoritmo de selección ordena una matriz encontrando repetidamente el elemento más pequeño de la parte no ordenada y colocándolo al principio. Escribámoslo en Java:

public class SelectionSort {
   public static void selectionSort(int[] myArray) {
       int n = myArray.length;

       for (int i = 0; i < n - 1; i++) {
           int minIndex = i;

           // Find the index of the minimum element in the unsorted part of the array
           for (int j = i + 1; j < n; j++) {
               if (myArray[j] < myArray[minIndex]) {
                   minIndex = j;
               }
           }

           // Swap the minimum element with the first element of the unsorted part
           int temp = myArray[minIndex];
           myArray[minIndex] = myArray[i];
           myArray[i] = temp;
       }
   }

   public static void main(String[] args) {
       int[] arr = {18, 28, 45, 2, 90, 7};

       System.out.println("Array before sorting:");
       for (int num : arr) {
           System.out.print(num + " ");
       }

       selectionSort(arr);

       System.out.println("\nArray after sorting:");
       for (int num : arr) {
           System.out.print(num + " ");
       }
   }
}

Aquí hay un resultado del programa: Vamos a explicarlo paso a paso. El bucle externo itera desde el principio de la matriz hasta el penúltimo elemento (hasta n-1). Este bucle selecciona cada elemento uno por uno como punto de partida de la parte sin clasificar del Array . Dentro del bucle externo, inicializamos minIndex con el índice actual i , asumiendo que es el índice del elemento más pequeño en la parte no ordenada de Array . El bucle interno comienza desde i+1 y sube hasta el último elemento del Array . Busca el índice del elemento más pequeño en la parte no ordenada de la matriz comparando cada elemento con el elemento mínimo actual ( arr[minIndex] ). Si encontramos un elemento que es más pequeño que el elemento mínimo actual, actualizamos minIndex al índice del nuevo elemento mínimo. Una vez que se completa el ciclo interno, encontramos el índice del elemento mínimo en la parte sin clasificar del Array . Luego intercambiamos el elemento mínimo con el primer elemento de la parte sin clasificar usando una variable temporal temp. El bucle exterior continúa hasta que todos los elementos estén ordenados, extendiendo gradualmente la parte ordenada del Array . Finalmente, la matriz ordenada se imprime en el método principal antes y después de llamar al método de selección .

Combinar ordenar

Merge Sort es un algoritmo de divide y vencerás que divide recursivamente el Array en subarreglos más pequeños, los clasifica y luego los fusiona para obtener un arreglo ordenado. Merge Sort es estable y se usa ampliamente, especialmente cuando se requiere estabilidad y una complejidad de tiempo garantizada en el peor de los casos.

public class MergeSort {

      //Merge Sort array
      public static void mergeSort(int[] myArray) {
        if (myArray.length <= 1) {
            return;
        }

        int mid = myArray.length / 2;
        int[] left = new int[mid];
        int[] right = new int[myArray.length - mid];

        System.arraycopy(myArray, 0, left, 0, mid);
        System.arraycopy(myArray, mid, right, 0, myArray.length - mid);

        mergeSort(left);
        mergeSort(right);

        merge(myArray, left, right);
    }

    public static void merge(int[] arr, int[] left, int[] right) {
        int i = 0; // index for left subarray
        int j = 0; // index for right subarray
        int k = 0; // index for merged array

        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }

        while (i < left.length) {
            arr[k++] = left[i++];
        }

        while (j < right.length) {
            arr[k++] = right[j++];
        }
    }

    public static void main(String[] args) {
        int[] arr = {18, 2, 28, 7, 90, 45};

        System.out.println("Array before sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        mergeSort(arr);

        System.out.println("\nArray after sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

El resultado aquí es: Expliquemos con mayor precisión cómo funciona. El algoritmo divide el Array en dos partes de forma recursiva hasta alcanzar el caso base (cuando el Array tiene uno o cero elementos). Luego, vuelve a fusionar las mitades ordenadas utilizando el método de fusión. El método de fusión toma tres matrices como entrada: la matriz original y los subarreglos izquierdo y derecho (izquierdo y derecho). Compara los elementos de los subarreglos izquierdo y derecho y los fusiona en el Array original en orden.

Tipo de inserción

La clasificación por inserción funciona insertando repetidamente un elemento de la parte no ordenada en su posición correcta en la parte ordenada. Funciona bien para conjuntos de datos pequeños o datos casi ordenados.

public class InsertionSort {
    public static void insertionSort(int[] myArray) {
        int n = myArray.length;

        for (int i = 1; i < n; i++) {
            int key = myArray[i];
            int j = i - 1;

            while (j >= 0 && myArray[j] > key) {
                myArray[j + 1] = myArray[j];
                j--;
            }

            myArray[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {18, 90, 7, 28, 45, 2};

        System.out.println("Array before sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        insertionSort(arr);

        System.out.println("\nArray after sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

El resultado del programa es el habitual: Aquí el método insertionSort implementa el algoritmo Insertion Sort. Itera a través del Array y considera cada elemento como una clave. Compara la clave con los elementos anteriores y los mueve una posición hacia adelante si son mayores, desplazando efectivamente los elementos para dejar espacio para la clave en la posición correcta. El bucle externo itera desde el segundo elemento ( i = 1 ) hasta el último elemento de la matriz. El bucle interno comienza desde el elemento actual ( arr[i] ) y va hacia atrás ( j = i - 1 ) hasta que encuentra la posición correcta para la clave o llega al comienzo del Array . Dentro del bucle interno, si un elemento ( arr[j] ) es mayor que la clave, se desplaza una posición hacia adelante ( arr[j + 1] = arr[j] ) para dejar espacio para la clave. Este proceso continúa hasta que se encuentra la posición correcta para la llave. Una vez que se completa el bucle interno, la clave se coloca en la posición correcta ( arr[j + 1] = key ). En el método principal, se crea e imprime una matriz de ejemplo antes y después de ordenar utilizando el método insertionSort .

Ordenación rápida

Quick Sort es un algoritmo de divide y vencerás que selecciona un elemento pivote y divide la matriz alrededor del pivote. Como regla general, Quick Sort es más rápido que Merge Sort para conjuntos de datos pequeños y medianos debido a sus bajos factores constantes.

public class QuickSort {

       public static void quickSort(int[] myArray, int low, int high) {
           if (low < high) {
               int pivotIndex = partition(myArray, low, high);
               quickSort(myArray, low, pivotIndex - 1);
               quickSort(myArray, pivotIndex + 1, high);
           }
       }

       public static int partition(int[] arr, int low, int high) {
           int pivot = arr[high];
           int i = low - 1;

           for (int j = low; j < high; j++) {
               if (arr[j] <= pivot) {
                   i++;
                   swap(arr, i, j);
               }
           }

           swap(arr, i + 1, high);
           return i + 1;
       }

       public static void swap(int[] arr, int i, int j) {
           int temp = arr[i];
           arr[i] = arr[j];
           arr[j] = temp;
       }

       public static void main(String[] args) {
           int[] arr = {18, 28, 2, 90, 7, 45};

           System.out.println("Array before sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }

           quickSort(arr, 0, arr.length - 1);

           System.out.println("\nArray after sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }
       }
}

El resultado está aquí: Aquí tenemos tres métodos para implementar la clasificación rápida. El método QuickSort toma tres parámetros: la matriz que se va a ordenar, el índice bajo del subarreglo y el índice alto del subarreglo. Inicialmente, verifica si el subarreglo tiene más de un elemento. Si es así, selecciona un pivote usando el método de partición, ordena recursivamente el subarreglo antes del pivote y ordena recursivamente el subarreglo después del pivote. El método de partición selecciona el pivote como último elemento del subarreglo ( arr[high] ). Establece el índice de partición (i) en el índice bajo menos 1. Luego itera desde el índice bajo hasta el índice alto - 1 y verifica si cada elemento es menor o igual que el pivote. Si es así, intercambia el elemento con el elemento en el índice de partición (i) e incrementa el índice de partición. Finalmente, intercambia el elemento pivote con el elemento en el índice de partición + 1 y devuelve el índice de partición. El método de partición selecciona el pivote como último elemento del subarreglo ( arr[high] ). Establece el índice de partición (i) en el índice bajo menos 1. Luego itera desde el índice bajo hasta el índice alto - 1 y verifica si cada elemento es menor o igual al pivote. Si es así, intercambia el elemento con el elemento en el índice de partición (i) e incrementa el índice de partición. Finalmente, intercambia el elemento pivote con el elemento en el índice de partición + 1 y devuelve el índice de partición. El método de intercambio es un método de utilidad que se utiliza para intercambiar dos elementos en el Array . En el método principal , se crea e imprime una matriz de ejemplo antes y después de ordenar utilizando el método QuickSort .

Conclusiones

En este artículo has descubierto cómo ordenar una matriz en lenguaje Java. Puede utilizar un método Arrays.sort incorporado o escribir sus propias implementaciones de métodos de clasificación populares, como clasificación por burbujas, clasificación por fusión, etc. También puedes intentar invadir tu propio método de clasificación. Depende de tu tarea. Si necesita resolver un problema de clasificación rápidamente, simplemente utilice un método escrito previamente. Si aprende programación y trata de mejorar en ella, es una muy buena idea escribir algunos métodos de clasificación usted mismo.