La clasificación es una de las operaciones básicas que realizamos en los objetos. Incluso en la infancia, a los niños se les enseña a ordenar a medida que desarrollan sus habilidades de pensamiento. Las computadoras y el software no son una excepción. Hay una gran variedad de algoritmos de clasificación en Java . Te sugiero que compruebes qué son y cómo funcionan. ¿Qué pasa si algún día te preguntan sobre uno de ellos en una entrevista?
Introducción
Ordenar elementos es una de las categorías de algoritmos que un desarrollador debe conocer. Si alguna vez no se tomó en serio la informática cuando estaba en la escuela, los estudiantes de hoy deben ser capaces de implementar y comprender los algoritmos de clasificación. Los algoritmos básicos, los más simples, se implementan mediante un bucle for . Naturalmente, para ordenar una colección de elementos, como una matriz, debe revisar la colección de alguna manera. Por ejemplo:
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
¿Qué se puede decir sobre este segmento de código? Tenemos un bucle en el que cambiamos el índice ( int i) de 0 al último elemento de la matriz. De hecho, simplemente tomamos cada elemento de la matriz e imprimimos su contenido. Cuantos más elementos haya en la matriz, más tiempo tardará el código en finalizar. Es decir, si nes el número de elementos, cuando n = 10el programa tardará el doble en ejecutarse que cuando n = 5. Si nuestro programa tiene un solo bucle, el tiempo de ejecución crece linealmente: cuantos más elementos haya, mayor será el tiempo de ejecución. Resulta que el algoritmo anterior funciona en tiempo lineal (una función lineal de n). En tales casos, decimos que la complejidad del algoritmo es "O(n)". Esta notación también se denomina "gran O" o "comportamiento asintótico". Pero solo puedes recordar "
El algoritmo de clasificación más simple (clasificación de burbujas)
Supongamos que tenemos una matriz y podemos iterar a través de ella. Excelente. Ahora intentemos ordenarlo en orden ascendente. ¿Qué quiere decir esto? Significa que dados dos elementos (por ejemplo, a = 6, b = 5), debemos reordenar ay bsi aes mayor que b(si a > b). ¿Qué significa esto cuando usamos un índice para trabajar con una colección (como es el caso de una matriz)? Significa que si el elemento con índice a es más grande que el elemento con índice b( array[a] > array[b]), entonces los elementos deben intercambiarse. Hay diferentes formas de cambiar de lugar. Pero usaremos una técnica que es simple, comprensible y fácil de recordar:
private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
Ahora podemos escribir lo siguiente:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
}
}
System.out.println(Arrays.toString(array));
Como puede ver, los elementos realmente se intercambiaron. Comenzamos con el índice 1, porque si la matriz tiene solo un elemento, la expresión array[i] < array[i-1]no es válida para el índice 0. Hacer esto también nos protege de los casos en que la matriz no tiene elementos o solo tiene un elemento, y hace que el código se vea mejor. Pero la matriz resultante todavía no está ordenada, porque una sola pasada no es suficiente para ordenar. Tendremos que agregar otro bucle en el que realizaremos pases una y otra vez hasta obtener una matriz ordenada:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
boolean needIteration = true;
while (needIteration) {
needIteration = false;
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
needIteration = true;
}
}
}
System.out.println(Arrays.toString(array));
Así que terminamos nuestro primer algoritmo de clasificación. Repetimos el ciclo externo ( while) hasta que decidamos que no se necesitan más iteraciones. De forma predeterminada, antes de cada nueva iteración, asumimos que nuestra matriz está ordenada y ya no necesitamos hacer un bucle. En consecuencia, nos movemos secuencialmente a través de los elementos y verificamos esta suposición. Pero si los elementos no están en orden, intercambiamos elementos y entendemos que ahora no tenemos garantía de que los elementos estén en el orden correcto. Esto significa que necesitamos realizar otra iteración. Por ejemplo, supongamos que tenemos [3, 5, 2]. 5es más que 3— todo está bien. Pero 2es menor que 5. Sin embargo, [3, 2, 5]requiere otra pasada, ya que3 > 2y hay que cambiarlos. Debido a que estamos usando un ciclo dentro de un ciclo, la complejidad de nuestro algoritmo aumenta. Dados nlos elementos, se convierte en n * n, es decir, O(n^2). Esto se llama complejidad cuadrática. En general, no podemos saber exactamente cuántas iteraciones se necesitarán. La expresión de complejidad de un algoritmo muestra cómo aumenta la complejidad en el peor de los casos. Es decir, indica cuánto aumentará el tiempo de ejecución a medida que ncambie el número de elementos. Bubble sort es uno de los algoritmos de clasificación más simples e ineficientes. A veces también se le llama "tipo estúpido". Material sobre este tema:
Otro algoritmo de clasificación es la clasificación por selección. También tiene complejidad cuadrática, pero hablaremos de eso más adelante. Así que la idea es simple. En cada pasada, seleccionamos el elemento más pequeño y lo desplazamos al principio. Además, cada pase comienza un paso a la derecha. En otras palabras, el primer paso comienza desde el elemento cero, el segundo paso desde el primero, etc. Se verá así:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
int minInd = left;
for (int i = left; i < array.length; i++) {
if (array[i] < array[minInd]) {
minInd = i;
}
}
swap(array, left, minInd);
}
System.out.println(Arrays.toString(array));
Esta ordenación es inestable, porque los elementos idénticos (en términos de cualquier característica que estemos usando para ordenar los elementos) pueden cambiar sus posiciones relativas. Hay un buen ejemplo en el artículo de Wikipedia sobre ordenación por selección . Material sobre este tema:
La ordenación por inserción también tiene complejidad cuadrática, ya que nuevamente tenemos un ciclo dentro de un ciclo. ¿Qué hace que la ordenación por inserción sea diferente? Este algoritmo de clasificación es "estable". Esto significa que los elementos idénticos no cambiarán su orden relativo. Una vez más, nos referimos a idénticos en términos de las características por las que estamos clasificando.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
// Get an element
int value = array[left];
// Iterate through the elements that are in front of this element
int i = left - 1;
for (; i >= 0; i--) {
// If the current element is smaller, then move the larger element to the right.
if (value < array[i]) {
array[i + 1] = array[i];
} else {
// If the current element is larger, we stop
break;
}
}
// Insert the current value in the empty space
array[i + 1] = value;
}
System.out.println(Arrays.toString(array));
Clasificación de lanzadera
Hay otro algoritmo de clasificación simple: la ordenación de lanzadera. Esto también se conoce como tipo de burbuja bidireccional o tipo de coctelera. Estos nombres alternativos nos dicen que el tipo de transbordador no se trata del transbordador espacial. Se trata de algo que se mueve de un lado a otro. Ahora puedes pensar en eso cuando piensas en este algoritmo. ¿Cuál es la esencia del algoritmo? La esencia del algoritmo es que iteramos de izquierda a derecha, intercambiando elementos y comprobando si es necesario intercambiar alguno de los elementos que quedan en la otra dirección.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i - 1);
for (int z = i - 1; (z - 1) >= 0; z--) {
if (array[z] < array[z - 1]) {
swap(array, z, z - 1);
} else {
break;
}
}
}
}
System.out.println(Arrays.toString(array));
Otro algoritmo de clasificación simple es la clasificación de shell. La esencia es similar a la clasificación de burbujas, pero en cada iteración tenemos un espacio diferente entre los elementos comparados. Se corta por la mitad con cada iteración. Aquí hay una implementación:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Calculate the gap between the checked elements
int gap = array.length / 2;
// As long as there is a gap between the elements
while (gap >= 1) {
for (int right = 0; right < array.length; right++) {
// Shift the right index until we find one for which
// there is the necessary gap between it and the element before it
for (int c = right - gap; c >= 0; c -= gap) {
if (array[c] > array[c + gap]) {
swap(array, c, c + gap);
}
}
}
// Recalculate the gap
gap = gap / 2;
}
System.out.println(Arrays.toString(array));
Además de estos algoritmos de clasificación simples, también existen algoritmos de clasificación más complicados. Por ejemplo, ordenar por combinación. Hay dos cosas a tener en cuenta. Primero, la recursividad viene a rescatarnos aquí. En segundo lugar, la complejidad del algoritmo ya no es cuadrática, como estamos acostumbrados. La complejidad de este algoritmo es logarítmica. Esto se escribe como O(n log n). Así que vamos a implementarlo. Primero, escribiremos una llamada recursiva al método sort:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
}
Ahora, agreguemos la acción principal a nuestra implementación. Aquí está nuestro súper método:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
// Create a temporary array with the required size
int[] buffer = new int[right - left + 1];
// Starting from the specified left index, go through each element.
int cursor = left;
for (int i = 0; i < buffer.length; i++) {
// We use delimeter to point to the element on the right half
// If delimeter> right, then the right half has no elements that haven't been added
if (delimiter > right || source[cursor] > source[delimiter]) {
buffer[i] = source[cursor];
cursor++;
} else {
buffer[i] = source[delimiter];
delimiter++;
}
}
System.arraycopy(buffer, 0, source, left, buffer.length);
}
Podemos ejecutar nuestro ejemplo llamandomergeSort(array, 0, array.length-1). Como puede ver, el proceso se reduce a aceptar una matriz de entrada junto con indicaciones del principio y el final de la sección que debe ordenarse. Cuando comienza la clasificación, estos son el principio y el final de la matriz. Luego calculamos el delimitador, que es el índice donde dividiremos la matriz. Si la matriz se puede dividir en 2 partes, llamamos recursivamente al método de clasificación para las dos mitades de la matriz. Preparamos un búfer auxiliar donde insertaremos la sección ordenada. A continuación, establezca el índice al comienzo de la sección que desea ordenar y comience a recorrer cada elemento del búfer vacío, llenándolo con los elementos más pequeños. Si el elemento señalado por el índice es menor que el elemento señalado por el delimitador, colocamos el elemento en el búfer y cambiamos el índice. De lo contrario, colocamos el elemento señalado por el delimitador en el búfer y desplazamos el delimitador. Tan pronto como el delimitador va más allá de los límites de la sección que se está ordenando o llenamos toda la matriz, el rango especificado se considera ordenado.Material sobre este tema:
Otro algoritmo de clasificación interesante es la clasificación por conteo. La complejidad algorítmica aquí es O(n+k), donde nes el número de elementos y kes el valor máximo de un elemento. Este algoritmo tiene un inconveniente: necesitamos conocer los valores mínimo y máximo de la matriz. Aquí hay un ejemplo del tipo de conteo:
public static int[] countingSort(int[] theArray, int maxValue) {
// An array of "counters", ranging from 0 to the maximum value
int numCounts[] = new int[maxValue + 1];
// We increase the counter in the corresponding cell (index = value)
for (int num : theArray) {
numCounts[num]++;
}
// Create an array to hold the sorted result
int[] sortedArray = new int[theArray.length];
int currentSortedIndex = 0;
// Run through the array of "counters"
for (int n = 0; n < numCounts.length; n++) {
int count = numCounts[n];
// Run through the number of values
for (int k = 0; k < count; k++) {
sortedArray[currentSortedIndex] = n;
currentSortedIndex++;
}
}
return sortedArray;
}
Puede comprender que es muy inconveniente cuando necesitamos saber de antemano los valores mínimo y máximo. Y aquí tenemos otro algoritmo: ordenamiento radix. Solo presentaré el algoritmo aquí visualmente. Ver los materiales complementarios para la implementación: Materiales:
Bueno, es hora del postre: clasificación rápida, uno de los algoritmos de clasificación más famosos. Tiene complejidad logarítmica: O(n log n). Este algoritmo de clasificación fue desarrollado por Tony Hoare. Curiosamente, lo inventó mientras vivía en la Unión Soviética, donde estudió traducción automática en la Universidad de Moscú y desarrolló un libro de frases ruso-inglés. Además, Java utiliza una versión más compleja de este algoritmo en Arrays.sort. ¿Sobre qué Collections.sort? ¿Por qué no echar un vistazo a cómo se ordenan las cosas "bajo el capó"? Aquí está el código:
public static void quickSort(int[] source, int leftBorder, int rightBorder) {
int leftMarker = leftBorder;
int rightMarker = rightBorder;
int pivot = source[(leftMarker + rightMarker) / 2];
do {
// Move the left marker from left to right as long as the element is less than pivot
while (source[leftMarker] < pivot) {
leftMarker++;
}
// Move the right marker as long as the element is greater than pivot
while (source[rightMarker] > pivot) {
rightMarker--;
}
// Check whether we need to swap the elements pointed to by the markers
if (leftMarker <= rightMarker) {
// The left marker will be less than the right one only if we need to do a swap
if (leftMarker < rightMarker) {
int tmp = source[leftMarker];
source[leftMarker] = source[rightMarker];
source[rightMarker] = tmp;
}
// Shift the markers to get new borders
leftMarker++;
rightMarker--;
}
} while (leftMarker <= rightMarker);
// Execute recursively on the parts
if (leftMarker < rightBorder) {
quickSort(source, leftMarker, rightBorder);
}
if (leftBorder < rightMarker) {
quickSort(source, leftBorder, rightMarker);
}
}
Todo esto es algo muy aterrador, así que profundicemos en ello. Para la matriz de entrada ( int[]fuente), creamos dos marcadores: izquierda ( L) y derecha ( R). Durante la primera llamada al método, corresponden al principio y al final de la matriz. Luego identificamos el elemento pivote, que se llama acertadamente pivot. Después de esto, nuestra tarea es mover los valores más pequeños pivota la izquierda de pivot, y los más grandes a la derecha. Para ello, primero movemos el Lmarcador hasta encontrar un valor mayor que pivot. Si no se encuentra un valor menor, entonces
L se vuelve igual a
pivot. Luego movemos el
Rmarcador hasta que encontremos un valor menor que
pivot. Si no se encuentra un valor mayor, entonces
Rse vuelve igual a
pivot. A continuación, si el
Lmarcador está antes del
Rmarcador o coincide con él, tratamos de intercambiar los elementos si el
Lelemento es menor que el
Relemento. Luego nos desplazamos
La la derecha por 1, y nos desplazamos
Ra la izquierda por 1. Cuando el
Lmarcador se mueve más allá del
Rmarcador, significa que el intercambio está completo: los valores más pequeños están a la izquierda de
pivot, los valores más grandes están a la derecha de
pivot. Después de esto, llamamos recursivamente al mismo método de ordenación en los subarreglos, desde el principio de la sección que se ordenará hasta el marcador de la derecha, y desde el marcador de la izquierda hasta el final de la sección que se ordenará. ¿Por qué desde el principio hasta el marcador correcto? Porque al final de una iteración, resulta que el marcador derecho se mueve lo suficiente como para convertirse en el límite de la parte izquierda. Este algoritmo es más complejo que la clasificación simple, por lo que es mejor dibujarlo. Tome una hoja de papel blanca y escriba: 4 2 6 7 3. Luego escriba
pivoten el medio, es decir, debajo del número 6. Encierre en un círculo. Debajo de 4, escriba
L, y debajo de 3, escriba
R. 4 menos que 6, 2 menos que 6. Terminamos moviéndonos
La la
pivotposición, porque
Lno podemos pasar
pivot, según la condición. Escribe de nuevo 4 2 6 7 3. Haz un círculo alrededor del 6 (
pivot) y colócalo
Ldebajo. Ahora mueve el
Rmarcador. 3 es menor que 6, así que pon el
Rmarcador en 3. Como 3 es menor que 6 (
pivot), realizamos un
swap. Escribe el resultado: 4 2 3 7 6. Encierra en un círculo el 6, porque sigue siendo el
pivot. El
Lmarcador está en 3. El
Rmarcador está en 6. Recuerda que movemos los marcadores hasta que
Lse mueva más allá de
R. Mover
Lal siguiente número. Aquí me gustaría explorar dos posibilidades: 1) el caso donde el penúltimo número es 7 y 2) el caso donde es 1, no 7.
Si el penúltimo número es 1: Mueva el
Lmarcador a 1, porque podemos mover
Lsiempre y cuando el
Lmarcador apunta a un número menor que
pivot. Pero no podemos movernos
Rde 6, porque solo podemos mover R si el
Rmarcador apunta a un número que es mayor que
pivot. No realizamos a
swap, porque 1 es menor que 6. Escribe la situación actual: 4 2 3 1 6. Circula 6 (
pivot).
Lcambia
pivoty deja de moverse.
Rno se mueve No realizamos un intercambio. Shift
Ly
Rpor una posición. Escribe el
Rmarcador debajo de 1. El
Lmarcador está fuera de los límites. Porque
Lestá fuera de los límites, no hacemos nada. Pero escribimos 4 2 3 1 nuevamente, porque este es nuestro lado izquierdo, que es menor que
pivot(6). Seleccione el nuevo
pivoty comience todo de nuevo :)
Si el penúltimo número es 7:Mueva el
Lmarcador a 7. No podemos mover el marcador derecho porque ya está apuntando al pivote. 7 es mayor que
pivot, entonces realizamos un
swap. Escribe el resultado: 4 2 3 6 7. Encierra en un círculo el 6, porque es el
pivot. El
Lmarcador ahora se desplaza a 7 y el
Rmarcador se desplaza a 3. No tiene sentido ordenar la parte desde
Lel final, porque solo hay 1 elemento. Sin embargo, enviamos la parte de 4 al
Rmarcador para su clasificación. Elegimos a
pivoty comenzamos de nuevo :) A primera vista, puede parecer que si agrega muchos valores iguales a
pivot, entonces romperás el algoritmo. Pero este no es el caso. Puede pensar en combinaciones engañosas y convencerse sobre el papel de que todo es correcto y maravillarse de que acciones tan simples implementen un mecanismo de clasificación tan confiable. El único inconveniente es que este algoritmo de clasificación no es estable. Porque un intercambio puede cambiar el orden relativo de elementos idénticos si uno de ellos se encuentra antes
pivotde que el otro elemento se intercambie en la parte anterior
pivot.
La línea de fondo
Arriba, vimos un conjunto de algoritmos de clasificación de "caballeros" implementados en Java. Los algoritmos son generalmente útiles, tanto desde una perspectiva aplicada como en términos de aprender a pensar. Algunos son más simples, algunos son más complicados. Gente inteligente defendió sus disertaciones para algunos. Para otros, escribieron libros súper gruesos. Espero que los materiales complementarios lo ayuden a aprender aún más, ya que este artículo es solo una descripción general que ya resultó ser importante. Y su propósito es proporcionar una pequeña introducción. También puede encontrar una introducción a los algoritmos si lee
"Algoritmos de Grokking ". También me gusta la lista de reproducción de Jack Brown:
AQA Decision 1 1.01 Tracing an Algorithm . Para divertirse, puede ver visualizaciones de algoritmos en la
clasificación.visualgo.net .
GO TO FULL VERSION