Clasificación rápida en Java

En esta guía, veremos la teoría y cómo implementar un Quicksort de un solo pivote en Java con un análisis de complejidad de tiempo y espacio.

Introducción

Sorting es una de las técnicas fundamentales utilizadas en la resolución de problemas, especialmente en aquellos relacionados con la escritura e implementación de algoritmos eficientes.

Por lo general, la clasificación se combina con la búsqueda, lo que significa que primero clasificamos elementos en la colección dada, luego buscamos algo dentro de ella, ya que generalmente es más fácil buscar algo en una colección ordenada, en lugar de una sin clasificar, ya que puede hacer conjeturas informadas e imponer suposiciones sobre los datos.

Hay muchos algoritmos que pueden ordenar elementos de manera eficiente, pero en esta guía echaremos un vistazo a la teoría subyacente y cómo implementar Quicksort en Java.

Dato curioso: Desde JDK7, el algoritmo utilizado para [clasificación lista para usar en JVM para arreglos](http://hg.openjdk.java.net/jdk7/jdk7/jdk/file/tip/src/share /classes/java/util/Arrays.java) es un Quicksort de doble pivote.

Quicksort en Java

Quicksort es un algoritmo de clasificación que pertenece al grupo de algoritmos divide y vencerás, y es in situ (sin necesidad de estructuras de datos auxiliares), no estable (no garantiza el orden relativo de los elementos del mismo valor después de la clasificación) algoritmo de clasificación.

Los algoritmos de divide y vencerás descomponen recursivamente un problema en dos o más subproblemas del mismo tipo, haciéndolos más simples de resolver. El desglose continúa hasta que un problema es lo suficientemente simple como para resolverlo por sí solo (a esto lo llamamos el caso base).

Se ha demostrado que este algoritmo da los mejores resultados cuando se trabaja con arreglos grandes y, por otro lado, cuando se trabaja con arreglos más pequeños, un algoritmo como Clasificación de selección podría resultar más útil eficiente.

Quicksort modifica la idea base de Selection Sort, de modo que en lugar de un mínimo (o un máximo), en cada paso del camino, un elemento se coloca en el lugar al que pertenece en la matriz ordenada.

Este elemento se llama pivote. Sin embargo, si quisiéramos usar el enfoque de divide y vencerás y reducir el problema de ordenar la matriz a un grupo más pequeño de dos sub-matrices, debemos cumplir con lo siguiente: mientras colocamos nuestro pivote en ella\ En el lugar de la matriz, necesitamos agrupar el resto de los elementos en dos grupos más pequeños: los que están a la izquierda del pivote son menores o iguales que él, y los que están a la *derecha * son más grandes que el pivote.

Este es en realidad el paso clave del algoritmo, llamado particionamiento, e implementarlo de manera eficiente es imprescindible si queremos que nuestro Quicksort también sea eficiente.

Antes de discutir cómo funciona Quicksort, debemos abordar cómo elegimos qué elemento es el pivote. El escenario perfecto es que siempre elegimos el elemento que divide la matriz en mitades exactas. Sin embargo, dado que esto es casi imposible de lograr, podemos abordar este problema de diferentes maneras.

Por ejemplo, el pivote puede ser el primero o el último elemento en la matriz (o una sub-matriz) que estamos procesando actualmente. Podemos elegir un elemento mediano como pivote, o incluso elegir un elemento aleatorio para que desempeñe el papel.

Tenemos una variedad de formas de realizar esta tarea, y el enfoque que tomaremos en este artículo es elegir siempre el primero (es decir, el elemento más a la izquierda de la matriz) como pivote. Ahora pasemos a un ejemplo y expliquemos cómo funciona todo.

Visualización de Quicksort

Supongamos que tenemos la siguiente matriz:

array

En este ejemplo, el pivote en la primera iteración será 4, ya que la decisión es elegir el primer elemento de la matriz como pivote. Ahora viene la partición: necesitamos colocar 4 en la posición en la que se encontrará en la matriz ordenada.

El índice de esa posición será 2, por lo que después de la primera partición, nuestra matriz se verá así:

array

{.icon aria-hidden=“true”}

Nota: Es notable que los elementos ubicados a la izquierda y a la derecha del pivote no están ordenados como deberían.

Esto es de esperar: cada vez que particionamos una matriz que no es el caso base (es decir, de tamaño 1), los elementos se agrupan en un orden aleatorio.

Lo importante es lo que discutimos anteriormente: los elementos a la izquierda del pivote son menores o iguales, y los elementos a la derecha son más grandes que el pivote. Eso no quiere decir que no se puedan clasificar en el primer grupo, aunque es poco probable que aún pueda suceder.

Continuamos y vemos que aquí se activa divide y vencerás: podemos dividir nuestro problema original en dos más pequeños:

array

Para el problema de la izquierda, tenemos una matriz de tamaño 2 y el elemento pivote será 2. Después de colocar el pivote en su lugar (en la posición 1), obtenemos una matriz [1, 2] después de la cual no tenemos más casos para el lado izquierdo del problema, ya que los únicos dos subcasos de [1, 2] son [1] y [2] que son ambos casos base. Con esto terminamos con el lado izquierdo de los subcasos y consideramos esa parte del arreglo ordenada.

Ahora, para el lado derecho, el pivote es 13. Dado que es el mayor de todos los números de la matriz que estamos procesando, tenemos la siguiente configuración:

array

A diferencia de antes, cuando el pivote dividió nuestra matriz en dos subcasos, aquí solo hay un caso: [8, 10, 7, 5]. El pivote ahora es 8 y debemos llevarlo a la posición 5 en la matriz:

array

El pivote ahora divide la matriz en dos subcasos: [7, 5] y [10]. Dado que [10] es de tamaño 1, ese es nuestro caso base y no lo consideramos en absoluto.

El único subarreglo que queda es el conjunto de [7, 5]. Aquí, 7 es el pivote, y después de llevarlo a su posición (índice 4), a su izquierda en la posición 3 está solo 5. No tenemos más subcasos y aquí es donde termina el algoritmo.

Después de ejecutar Quicksort, tenemos la siguiente matriz ordenada:

templateniz

Este enfoque también tiene en cuenta los duplicados en la matriz, ya que todos los elementos que quedan del pivote son menores o iguales que el propio pivote.

Implementando Quicksort en Java

Con una buena intuición de cómo funciona Quicksort, podemos continuar con una implementación. En primer lugar, repasaremos la parte principal del programa que ejecutará Quicksort.

Dado que Quicksort es un algoritmo de divide y vencerás, naturalmente se implementa de forma recursiva, aunque también podrías hacerlo de forma iterativa (cualquier función recursiva también se puede implementar de forma iterativa), aunque la implementación no es tan clara:

1
2
3
4
5
6
7
static void quicksort(int[] arr, int low, int high){
    if(low < high){
        int p = partition(arr, low, high);
        quicksort(arr, low, p-1);
        quicksort(arr, p+1, high);
    }
}

{.icon aria-hidden=“true”}

Nota: low y high representan los márgenes izquierdo y derecho de la matriz que se está procesando actualmente.

El método partition(arr, low, high) particiona el arreglo, y tras su ejecución, la variable p almacena la posición del pivote después de la partición.

Este método solo se invoca cuando estamos procesando matrices que tienen más de un elemento, por lo tanto, la partición solo tiene lugar si bajo < alto.

Dado que Quicksort funciona en el lugar, el conjunto múltiple inicial de elementos que se pueden encontrar dentro de la matriz permanece sin cambios, pero hemos logrado exactamente lo que pretendíamos hacer: agrupar elementos más pequeños o iguales a la izquierda del pivote y más grandes que el pivote a la derecha.

Luego, llamamos al método quicksort recursivamente dos veces: para la parte de la matriz de low a p-1 y para la parte de p+1 a high.

Antes de discutir el método partition(), en aras de la legibilidad, implementaremos una función swap() simple que intercambia dos elementos en la misma matriz:

1
2
3
4
5
static void swap(int[] arr, int low, int pivot){
    int tmp = arr[low];
    arr[low] = arr[pivot];
    arr[pivot] = tmp;
}

Ahora, profundicemos en el código del método partition() y veamos cómo hace lo que hemos explicado anteriormente:

1
2
3
4
5
6
7
8
9
static int partition(int[] arr, int low, int high){
    int p = low, j;
    for(j=low+1; j <= high; j++)
        if(arr[j] < arr[low])
            swap(arr, ++p, j);

    swap(arr, low, p);
    return p;
}

Cuando el bucle for termina de ejecutarse, j tiene el valor high+1, lo que significa que los elementos en arr[p+1, high] son mayores o iguales que el pivote. Debido a esto, es necesario que hagamos un intercambio más de los elementos en la posición low y p, trayendo el pivote a su posición correcta en la matriz (es decir, la posición p).

Lo último que debemos hacer es ejecutar nuestro método quicksort() y ordenar una matriz. Usaremos la misma matriz que usamos en el ejemplo anterior, y llamar a quicksort(arr, low, high) ordenará la parte arr[low, high] de la matriz:

1
2
3
4
5
public static void main(String[] args) {
    int[] arr = {4, 8, 1, 10, 13, 5, 2, 7};
    // Sorting the whole array
    quicksort(arr, 0, arr.length - 1); 
}

Esto resulta en:

1
1, 2, 3, 4, 5, 7, 8, 10, 13

Complejidad de Quicksort

Quicksort, así como otros algoritmos que aplican la táctica de divide y vencerás, tiene una complejidad de tiempo de O(nlogn). Sin embargo, en comparación con algo como Ordenar por fusión, que tiene la complejidad de tiempo del peor de los casos de O(nlogn), Quicksort teóricamente puede tener el peor de los casos. caso de O(n^2).

La complejidad depende de cuánto tiempo nos tome elegir eficientemente un pivote, lo que a veces puede ser tan difícil como ordenar la matriz en sí, y dado que esperamos que la elección de un pivote sea O (1), generalmente no podemos garantía de que en cada paso del camino estaremos eligiendo el mejor pivote posible.

Aunque el peor de los casos de Quicksort puede ser O(n^2), la mayoría de las estrategias de elección de pivote se implementan de tal manera que no impiden demasiado la complejidad, razón por la cual la complejidad promedio de Quicksort es O(inicio de sesión). Está ampliamente implementado y utilizado, y el nombre en sí mismo es un homenaje a sus capacidades de rendimiento.

Por otro lado, donde Quicksort supera sin dudas a Merge Sort es la complejidad del espacio: Merge Sort requiere espacio O(n) porque usa una matriz separada para la fusión, mientras que Quicksort ordena en el lugar y tiene la complejidad espacial de O(1).

Conclusión

En este artículo, hemos cubierto cómo funciona el algoritmo Quicksort, cómo se implementa y discutimos su complejidad. Aunque la elección del pivote puede "hacer o deshacer" este algoritmo, generalmente se considera como uno de los algoritmos de clasificación más eficientes y se usa ampliamente cuando necesitamos clasificar matrices con una gran cantidad de elementos.

Licensed under CC BY-NC-SA 4.0