Introducción a la ordenación rápida en Java
El siguiente artículo Quick Sort in Java proporciona un resumen del algoritmo de ordenación rápida en java. El algoritmo de clasificación rápida es uno de los algoritmos de clasificación que es eficiente y similar al algoritmo de clasificación de fusión. Este es uno de los algoritmos más utilizados para fines de clasificación en tiempo real. La complejidad de tiempo en el peor de los casos de este algoritmo es O (n 2), la complejidad de tiempo en el caso promedio es O (n log n) y la complejidad de tiempo en el mejor de los casos es O (n log n).
La complejidad del espacio si O (n log n) donde es n es el tamaño de la entrada. El proceso de clasificación implica la partición de la entrada, las iteraciones recursivas y el marcado de un elemento fundamental para cada recursión. El tipo de clasificación en este algoritmo implica una comparación de elementos adyacentes de forma iterativa.
¿Cómo funciona Quick Sort en Java?
El algoritmo de clasificación rápida se puede implementar en Java formando un pseudocódigo con una secuencia de pasos diseñados y seguidos de manera eficiente.
- El principio principal del algoritmo de clasificación rápida que funciona se basa en el enfoque de dividir y conquistar y también es un algoritmo de clasificación eficiente.
- La matriz de entrada se divide en sub-matrices y la división se basa en un elemento pivote que es un elemento central. Las submatrices a ambos lados del elemento pivote son las áreas principales donde se produce la clasificación.
- El elemento pivote central es la base para dividir la matriz en dos particiones donde la mitad izquierda de los elementos de la matriz es menor que el elemento pivote y la mitad derecha de los elementos de la matriz es mayor que el elemento pivote.
- Antes de considerar el elemento pivote, puede ser cualquiera de los elementos de una matriz. Esto normalmente se considera como el medio o el primero o el último para facilitar la comprensión. El elemento pivote puede ser aleatorio de cualquiera de los elementos de la matriz.
- En nuestro ejemplo, el último elemento de una matriz se considera un elemento pivote, donde la partición de sub-matrices comienza desde el extremo derecho de la matriz.
- Finalmente, el elemento pivote estará en su posición ordenada real después de la finalización del proceso de clasificación, donde el proceso principal de clasificación se encuentra en la lógica de partición del algoritmo de clasificación.
- La eficiencia del algoritmo depende del tamaño de los subconjuntos y de cómo están equilibrados. Cuanto más desequilibrados estén los subconjuntos, mayor será la complejidad del tiempo que conducirá a la peor de las situaciones.
- La selección de elementos dinámicos de forma aleatoria resulta en la mejor complejidad de tiempo en muchos casos en lugar de elegir un índice particular de inicio, final o medio como elementos dinámicos.
Ejemplos para implementar la ordenación rápida en Java
El algoritmo QuickSort se implementó utilizando el lenguaje de programación Java como se muestra a continuación y el código de salida se mostró debajo del código.
- El código inicialmente toma la entrada usando el método quickSortAlgo () con la matriz, el índice inicial y el índice final, es decir, la longitud de la matriz como argumentos.
- Después de llamar al método quickSortAlgo (), comprueba si el índice inicial es menor que el índice final y luego llama al método arrayPartition () para obtener el valor del elemento pivote.
- El elemento de partición contiene la lógica de organizar los elementos cada vez más pequeños alrededor del elemento pivote en función de los valores del elemento.
- Después de obtener el índice del elemento pivote después de la ejecución del método de partición, el método quickSortAlgo () se llama de forma recursiva hasta que todas las sub-matrices se particionen y clasifiquen por completo.
- En la lógica de partición, el último elemento se asigna como elemento pivote y el primer elemento se compara con el elemento pivote, es decir, el último donde los elementos se intercambian en función de si son más pequeños o más grandes.
- Este proceso de recursión ocurre hasta que todos los elementos de una matriz se particionan y ordenan, donde el resultado final es una matriz ordenada combinada.
- Los elementos se intercambian dentro de la iteración for-loop solo en el caso de que el elemento sea menor o igual que el elemento pivote.
- Después de completar el proceso de iteración, el último elemento se intercambia, es decir, el valor del elemento pivote se mueve hacia el lado izquierdo para que se realicen las nuevas particiones y se repita el mismo proceso en forma de recursión que da como resultado una serie de operaciones de clasificación en diferentes particiones posibles como una formación de sub-matrices de los elementos de matriz dados.
- El código siguiente se puede ejecutar en cualquier IDE y la salida se puede verificar cambiando el valor de la matriz en main () El método principal se usa solo con el fin de obtener la salida en la consola. Como parte de los estándares de codificación de Java, el método principal se puede eliminar a continuación y se puede crear un objeto y se puede llamar a los métodos siguientes al hacerlos no estáticos.
Implementación de código del algoritmo de ordenación rápida en Java
/*
* Quick Sort algorithm - Divide & Conquer approach
*/
public class QuickSortAlgorithm (
public static void main(String() args) (
int() array = ( 99, 31, 1, 3, 5, 561, 1, 342, 345, 454 );
quickSortAlgo(array, 0, array.length - 1);
for (int ar : array) (
System.out.print(ar + " ");
)
)
public static int arrayPartition(int() array, int start, int end) (
int pivot = array(end);
int i = (start - 1);
for (int ele = start; ele < end; ele++) (
if (array(ele) <= pivot) (
i++;
int swap = array(i);
array(i) = array(ele);
array(ele) = swap;
)
)
// Swapping the elements
int swap = array(i + 1);
array(i + 1) = array(end);
array(end) = swap;
return i + 1;
)
public static void quickSortAlgo(int() arrayTobeSorted, int start, int end) (
if (start < end) (
int pivot = arrayPartition(arrayTobeSorted, start, end);
quickSortAlgo(arrayTobeSorted, start, pivot - 1);
quickSortAlgo(arrayTobeSorted, pivot + 1, end);
)
)
)
Salida:
Conclusión
El algoritmo de clasificación rápida es eficiente pero no muy estable en comparación con otras técnicas de clasificación. La eficiencia de los algoritmos de ordenación rápida se reduce en el caso de un mayor número de elementos repetidos, lo cual es un inconveniente. La complejidad del espacio se optimiza en este algoritmo de ordenación rápida.
Artículos recomendados
Esta es una guía para la ordenación rápida en Java. Aquí discutimos cómo funciona Quick Sort en Java junto con un ejemplo e implementación de código. También puede consultar nuestros otros artículos sugeridos para obtener más información:
- Heap Ordenar en Java
- ¿Qué es un árbol binario en Java?
- Manipulación de bits en Java
- Descripción general de la fusión Ordenar en JavaScript
- Descripción general de la ordenación rápida en JavaScript
- Heap Sort en Python
- Los 6 mejores algoritmos de clasificación en JavaScript