quicksort java algorithm
Este tutorial explica el algoritmo Quicksort en Java, sus ilustraciones, la implementación QuickSort en Java con la ayuda de ejemplos de código:
La técnica de clasificación Quicksort se utiliza ampliamente en aplicaciones de software. Quicksort utiliza una estrategia de divide y vencerás como la ordenación combinada.
En el algoritmo de clasificación rápida, primero se selecciona un elemento especial llamado 'pivote' y la matriz o lista en cuestión se divide en dos subconjuntos. Los subconjuntos particionados pueden o no tener el mismo tamaño.
=> Lea la serie de formación Easy Java.
VPN Alemania gratis
Las particiones son tales que todos los elementos menores que el elemento pivote están hacia la izquierda del pivote y los elementos mayores que el pivote están a la derecha del pivote. La rutina Quicksort ordena de forma recursiva las dos sublistas. Quicksort funciona de manera eficiente y también más rápida incluso para matrices o listas más grandes.
Lo que vas a aprender:
- Partición Quicksort Java
- Algoritmo de clasificación rápida Java
- Pseudocódigo para clasificación rápida
- Ilustración
- Implementación de Quicksort en Java
- Preguntas frecuentes
- Conclusión
- Lectura recomendada
Partición Quicksort Java
El particionamiento es el proceso clave de la técnica Quicksort. Entonces, ¿qué es la partición?
Dada una matriz A, elegimos un valor x llamado pivote tal que todos los elementos menores que x estén antes de x, y todos los elementos mayores que x estén después de x.
Un valor de pivote puede ser cualquiera de los siguientes:
- El primer elemento de la matriz
- El último elemento de la matriz
- El elemento medio de la matriz
- Cualquier elemento aleatorio en la matriz
Este valor de pivote se coloca en su posición adecuada en la matriz dividiendo la matriz. Por lo tanto, el resultado del proceso de 'partición' es el valor de pivote en su posición adecuada y los elementos menos que pivotan a la izquierda y elementos mayores que un pivote a la derecha.
Considere el siguiente diagrama que explica el proceso de partición.
El diagrama anterior muestra el proceso de partición de la matriz seleccionando repetidamente el último elemento de la matriz como pivote. En cada nivel, tenga en cuenta que dividimos la matriz en dos submatrices colocando pivote en su posición correcta.
A continuación, enumeramos el algoritmo y el pseudocódigo para la técnica de ordenación rápida que también incluye la rutina de partición.
Algoritmo de clasificación rápida Java
El algoritmo general para la ordenación rápida se proporciona a continuación.
|_+_|A continuación se muestra el pseudocódigo para la técnica de ordenación rápida.
Pseudocódigo para clasificación rápida
A continuación se muestra el pseudocódigo para una técnica de clasificación rápida. Tenga en cuenta que hemos proporcionado el pseudocódigo para la ordenación rápida y la rutina de partición.
|_+_|Ilustración
Veamos la ilustración del algoritmo de ordenación rápida. Tome la siguiente matriz como ejemplo. Aquí hemos seleccionado el último elemento como pivote.
Como se muestra, el primer elemento está etiquetado como bajo y el último elemento es alto.
Como es evidente en la ilustración anterior, hay dos punteros, alto y bajo, que apuntan respectivamente al último y primer elemento de la matriz. Ambos punteros se mueven a medida que avanza la clasificación rápida.
Cuando el elemento apuntado por el puntero bajo se vuelve mayor que el elemento pivote y el elemento apuntado por el puntero alto es menor que el elemento pivote, intercambiamos los elementos apuntados por el puntero bajo y alto, y cada puntero avanza 1 posición.
Los pasos anteriores se llevan a cabo hasta que ambos punteros se crucen en la matriz. Una vez que se cruzan, el elemento pivote obtiene su posición adecuada en la matriz. En este punto, la matriz está particionada y ahora podemos ordenar cada submatriz de forma independiente aplicando de forma recursiva un algoritmo de clasificación rápida a cada una de las submatrices.
Implementación de Quicksort en Java
La técnica QuickSort se puede implementar en Java utilizando recursividad o iteración. En esta sección, veremos ambas técnicas.
Clasificación rápida recursiva
Sabemos que la técnica básica de ordenación rápida ilustrada anteriormente usa la recursividad para ordenar la matriz. En la clasificación rápida recursiva después de particionar la matriz, la rutina de clasificación rápida se llama de forma recursiva para clasificar las submatrices.
La siguiente implementación demuestra la técnica de ordenación rápida mediante la recursividad.
|_+_|Producción:
Matriz original: (4, -1, 6, 8, 0, 5, -3)
Matriz ordenada: (-3, -1, 0, 4, 5, 6, 8)
Clasificación rápida iterativa
En la ordenación rápida iterativa, usamos la pila auxiliar para colocar parámetros intermedios en lugar de usar recursividad y ordenar particiones.
El siguiente programa Java implementa la ordenación rápida iterativa.
|_+_|Producción:
Matriz original: (3, 2, 6, -1, 9, 1, -6, 10, 5)
Matriz ordenada: (- 6, -1, 1, 2, 3, 6, 9, 10, 5)
Preguntas frecuentes
P # 1) ¿Cómo funciona un Quicksort?
Responder: Quicksort utiliza una estrategia de dividir y conquistar. Quicksort primero divide una matriz alrededor de un elemento pivote seleccionado y genera submatrices que se ordenan de forma recursiva.
P # 2) ¿Cuál es la complejidad temporal de Quicksort?
Responder: La complejidad de tiempo de la ordenación rápida en promedio es O (nlogn). En el peor de los casos, es O (n ^ 2) lo mismo que el orden de selección.
P # 3) ¿Dónde se usa Quicksort?
Responder: Quicksort se utiliza principalmente en aplicaciones recursivas. Quicksort es parte de C-library. Además, casi los lenguajes de programación que utilizan la ordenación incorporada implementan quicksort.
P # 4) ¿Cuál es la ventaja de Quicksort?
Responder:
- Quicksort es un algoritmo eficiente y puede ordenar fácilmente incluso una gran lista de elementos.
- Se clasifica en el lugar y, por lo tanto, no necesita espacio ni memoria adicionales.
- Se utiliza mucho y proporciona una forma eficaz de ordenar conjuntos de datos de cualquier longitud.
P # 5) ¿Por qué Quicksort es mejor que el tipo de combinación?
Responder: La razón principal por la que la ordenación rápida es mejor que la ordenación combinada es que la ordenación rápida es un método de ordenación local y no requiere espacio de memoria adicional. La clasificación por combinación requiere memoria adicional para la clasificación intermedia.
java cómo ordenar una matriz
Conclusión
Quicksort se considera el mejor algoritmo de clasificación principalmente debido a su eficiencia para clasificar incluso un gran conjunto de datos en tiempo O (nlogn).
Quicksort también es una ordenación local y no requiere espacio de memoria adicional. En este tutorial, hemos visto la implementación recursiva e iterativa de quicksort.
En nuestro próximo tutorial, continuaremos con los métodos de clasificación en Java.
=> Eche un vistazo a la guía para principiantes de Java aquí.
Lectura recomendada
- Algoritmo de búsqueda binaria en Java: implementación y ejemplos
- Matriz de Java: ¿Cómo imprimir elementos de una matriz en Java?
- Clasificación de selección en Java: algoritmo de clasificación de selección y ejemplos
- Tipos de datos de matriz: matriz int, matriz doble, matriz de cadenas, etc.
- Matriz de Java: declarar, crear e inicializar una matriz en Java
- Tutorial de JAVA para principiantes: más de 100 tutoriales prácticos en vídeo de Java
- Java Copy Array: Cómo copiar / clonar una matriz en Java
- Tutorial de longitud de matriz de Java con ejemplos de código