Algoritmos de clasificación rápida en Java - Programa para implementar Quick Sort

Tabla de contenido:

Anonim

Introducción a los algoritmos de clasificación rápida en Java

La ordenación rápida en java, también conocida como la ordenación de intercambio de partición, es un algoritmo de clasificación de divide y vencerás. La ordenación rápida es un buen ejemplo de un algoritmo que hace el mejor uso de los cachés de la CPU, debido a su naturaleza de división y conquista. El algoritmo de clasificación rápida es uno de los algoritmos de clasificación más utilizados, especialmente para ordenar las listas grandes y la mayoría de los lenguajes de programación lo han implementado. En el algoritmo Quicksort, los datos originales se dividen en dos partes que se ordenan individualmente y luego se fusionan para producir datos ordenados.

Consideremos que la matriz (8, 6, 3, 4, 9, 2, 1, 7) debe clasificarse utilizando la clasificación rápida.

Pasos para implementar algoritmos de clasificación rápida

1. Elija un elemento llamado pivote de la matriz. Generalmente, el elemento del medio se elige como pivote. Tomemos 4 como pivote.

2. Reorganice la matriz en dos partes de modo que los elementos menores que el pivote lleguen antes del pivote y los elementos mayores que el pivote aparezcan después del pivote. Se siguen los siguientes pasos:

  • Elija el elemento más a la izquierda, es decir, 8, ya que 4 es el pivote y 8 es más de 4, 8 debe moverse a la derecha de 4, en el lado derecho dejamos 7 ya que es mayor que 4 y elige 1 para intercambiar con 8, por lo tanto, después de cambiar la matriz se convierte en: 1, 6, 3, 4, 9, 2, 8, 7
  • Elija el siguiente elemento izquierdo, es decir, 6, ya que 4 es el pivote y 6 es más de 4, 6 debe moverse a la derecha de 4, en el lado derecho dejamos 7, 8 ya que son mayores que 4 y seleccionamos 2 para intercambiar con 6, por lo tanto, después de intercambiar la matriz se convierte en: 1, 2, 3, 4, 9, 6, 8, 7
  • Ahora, dado que todos los elementos a la izquierda del pivote son menores que el pivote y todos los elementos a la derecha del pivote son mayores que el pivote, hemos terminado con 4 como pivote.

3. Aplique recursivamente los pasos 1 y 2 para el subconjunto izquierdo (conjunto con elementos menores que el pivote) y para el subconjunto derecho (conjunto con elementos más que el pivote). Si la matriz contiene solo uno o cero elementos, entonces la matriz se considera variada.

Programa para implementar algoritmos de clasificación rápida

Aquí hay un programa de Java para ordenar una matriz de enteros utilizando un algoritmo de ordenación rápida.

Código:

import java.lang.*;
import java.util.*;
public class Main (
private int array();
private int length;
public void sort(int() inputArrayArr) (
if (inputArrayArr == null || inputArrayArr.length == 0) (
return;
)
this.array = inputArrayArr;
length = inputArrayArr.length;
performQuickSort(0, length - 1);
)
private void performQuickSort(int lowerIndex, int higherIndex) (
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number
// middle element taken as pivot
int pivot = array(lowerIndex+(higherIndex-lowerIndex)/2);
// Divide into two subarrays
while (i <= j) (
/**
* In each iteration, find an element from left side of the pivot which
* is greater than the pivot value, and also find an element
* From right side of the pivot which is less than the pivot value. Once the search
* is complete, we exchange both elements.
*/
while (array(i) < pivot) (
i++;
)
while (array(j) > pivot) (
j--;
)
if (i <= j) (
swapNumbers(i, j);
//move index to next position on both sides
i++;
j--;
)
)
// call performQuickSort() method recursively
if (lowerIndex < j)
performQuickSort(lowerIndex, j);
if (i < higherIndex)
performQuickSort(i, higherIndex);
)
private void swapNumbers(int i, int j) (
int temp = array(i);
array(i) = array(j);
array(j) = temp;
)
public static void main(String args())(
Main quickSort = new Main();
int() inputArray = (8, 6, 3, 4, 9, 2, 1, 7);
quickSort.sort(inputArray);
System.out.println("Sorted Array " + Arrays.toString(inputArray));
)
)

Salida:

Ventajas de los algoritmos de clasificación rápida

Las siguientes son las ventajas del algoritmo de ordenación rápida:

  • Excelente localidad de referencia: la localidad de referencia es la capacidad de un procesador de acceder a la misma ubicación de memoria de forma repetitiva durante un corto período de tiempo. La ordenación rápida en Java proporciona una excelente localidad de referencia debido al número muy pequeño de errores de caché, que en las arquitecturas modernas es fundamental para el rendimiento.
  • La ordenación rápida es paralelizable: una vez que se completa el paso inicial de particionar una matriz en regiones más pequeñas, todas las submatrices individuales se pueden clasificar independientemente en paralelo. Debido a esta razón, la ordenación rápida funciona mejor.

Análisis de complejidad de ordenación rápida

Quicksort es un algoritmo rápido y recursivo de cola que funciona según el principio de divide y vencerás. Aquí está su análisis de complejidad en el Mejor, Medio y Peor Caso:

  • Mejor complejidad del caso: si una matriz o una lista contiene n elementos, la primera ejecución necesitará O (n). Ahora la clasificación de las dos submatrices restantes requiere 2 * O (n / 2). Esto concluye la complejidad de O (n logn) en el mejor de los casos.
  • Complejidad de caso promedio : El caso promedio de clasificación rápida es O (n log n).
  • Complejidad del peor de los casos: elegir el primero o el último causaría el peor rendimiento para los datos casi ordenados o casi ordenados al revés. La ordenación rápida realiza O (n 2) en el peor de los casos.

En Java, matrices. El método Sort () utiliza un algoritmo de ordenación rápida para ordenar una matriz.

Artículos recomendados

Esta es una guía de Algoritmos de clasificación rápida en Java. Aquí discutimos los pasos para implementar, las ventajas y el análisis de complejidad de un algoritmo de clasificación rápida en Java junto con el programa. También puede consultar los siguientes artículos para obtener más información:

  1. Ordenar por inserción en Java
  2. bucle do-while en Java
  3. JComponent en Java
  4. Cuadrados en Java
  5. Intercambio en PHP
  6. Ordenar en C #
  7. Ordenar en Python
  8. Algoritmo de C ++ | Ejemplos de algoritmo C ++