Introducción
QuickSort es un algoritmo de clasificación Divide y Vencerás. Funciona seleccionando un elemento 'pivote' del arreglo y dividiendo los otros elementos en dos sub-arreglos, dependiendo de si son menores o mayores que el pivote. Luego, los sub-arreglos se clasifican de manera recursiva. La complejidad promedio de QuickSort es O(n log n). Es importante destacar que QuickSort no es una clasificación estable, es decir, las posiciones relativas de los elementos de clasificación iguales no se pueden preservar.
Importar la clase Arrays
En este paso, debes importar la clase java.util.Arrays. Esta clase contiene varios métodos para manipular arreglos que se utilizarán para convertir los arreglos de int a String.
import java.util.Arrays;
Definir el método partition()
Define un método auxiliar llamado partition(). El método partition() tomará un arreglo arr, un índice de inicio low y un índice de finalización high como entrada. El método partition() seleccionará un elemento como pivote y particionará los elementos de modo que todos los elementos menores que el elemento pivote estén a la izquierda del pivote y todos los elementos mayores que el pivote estén a la derecha del pivote. El elemento pivote se colocará en su posición correcta.
El método partition() devolverá el índice del elemento particionado. El elemento particionado es la posición donde se coloca el elemento pivote.
public static int partition(int[] arr, int low, int high) {
// Select the pivot element
int pivot = arr[high];
int i = (low - 1); // Índice del elemento más pequeño e indica la posición correcta del pivote encontrada hasta ahora
for (int j = low; j <= high - 1; j++) {
// Si el elemento actual es menor o igual al pivote
if (arr[j] <= pivot) {
i++; // incrementa el índice del elemento más pequeño
// intercambia arr[i] y arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// intercambia arr[i + 1] y arr[high]
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1; // Devuelve el índice de partición
}
Definir el método quicksort()
Define un método de clasificación llamado quicksort(). El método quicksort() tomará un arreglo arr, un índice de inicio low y un índice de finalización high como entrada. El método quicksort() clasificará recursivamente el arreglo arr[].
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// pi es el índice de partición, arr[p] ahora
// está en el lugar correcto
int pi = partition(arr, low, high);
// Clasifica recursivamente los elementos antes
// de la partición y después de la partición
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
Crear y asignar un arreglo de enteros
Crea y asigna arreglos de enteros para ser clasificados al campo arr.
int[] arr = {7, 9, 1, 2, 10, 15, 6};
Implementar QuickSort
Llame al método quickSort() con el campo arr como entrada, junto con el índice inicial y final del arreglo. Ordene y muestre el arreglo utilizando el método Arrays.toString(arr).
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
Probar con múltiples arreglos
Prueba tu implementación de QuickSort utilizando arreglos con diferentes características.
int[] arr1 = {7, 9, 1, 2, 10, 15, 6};
int[] arr2 = {1, 2, 3, 4, 5, 6, 7, 8};
int[] arr3 = {1};
int[] arr4 = {-5, 2,-1, 0, 11, 20, -20};
quickSort(arr1, 0, arr1.length-1);
quickSort(arr2, 0, arr2.length-1);
quickSort(arr3, 0, arr3.length-1);
quickSort(arr4, 0, arr4.length-1);
System.out.println(Arrays.toString(arr1));
System.out.println(Arrays.toString(arr2));
System.out.println(Arrays.toString(arr3));
System.out.println(Arrays.toString(arr4));
Seleccionar aleatoriamente el pivote
En este paso, necesitamos seleccionar el pivote de forma aleatoria en cada iteración para evitar el peor caso. Para lograr esto, actualizaremos el método partition() y reemplazaremos la siguiente línea:
int pivot = arr[high];
por esta línea:
int pivotIndex = low + (int)(Math.random() * ((high - low) + 1));
int pivot = arr[pivotIndex];
arr[pivotIndex] = arr[high];
arr[high] = pivot;
Probar con un elemento pivote aleatorizado
Prueba tu implementación de QuickSort utilizando elementos pivote aleatorizados.
int[] arr5 = {7, 4, 6, 10, 8, 5, 1, 3, 2, 9};
int[] arr6 = {4, 5, 10, 3, 8, 2, 1, 7, 6, 9};
int[] arr7 = {100, 200, 33, 1, 3, 400, 45, 67, 80, 13};
int[] arr8 = {12, 34, 32, 14, 55, 37, 23, 9};
quickSort(arr5, 0, arr5.length-1);
quickSort(arr6, 0, arr6.length-1);
quickSort(arr7, 0, arr7.length-1);
quickSort(arr8, 0, arr8.length-1);
System.out.println(Arrays.toString(arr5));
System.out.println(Arrays.toString(arr6));
System.out.println(Arrays.toString(arr7));
System.out.println(Arrays.toString(arr8));
Manejar casos extremos
En este paso, cubriremos los casos límite que QuickSort puede manejar. Defina estos casos límite como arreglos de enteros.
int[] arr9 = {};
int[] arr10 = {1, 1, 1, 1};
int[] arr11 = {1};
quickSort(arr9, 0, arr9.length-1);
quickSort(arr10, 0, arr10.length-1);
quickSort(arr11, 0, arr11.length-1);
System.out.println(Arrays.toString(arr9));
System.out.println(Arrays.toString(arr10));
System.out.println(Arrays.toString(arr11));
Código completo
A continuación se presenta el código completo del QuickSort en Java Lab.
import java.util.Arrays;
public class QuickSort {
public static int partition(int[] arr, int low, int high) {
int pivotIndex = low + (int)(Math.random() * ((high - low) + 1));
int pivot = arr[pivotIndex];
arr[pivotIndex] = arr[high];
arr[high] = pivot;
int i = low - 1;
for (int j = low; j <= high - 1; ++j) {
if (arr[j] <= pivot) {
++i;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void quickSort(int[] arr, int low, int high) {
if (low >= high) {
return;
}
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
public static void main(String[] args) {
System.out.println("Implementación de Quick Sort en Java\n-----------------------");
int[] arr = {7, 9, 1, 2, 10, 15, 6};
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
int[] arr1 = {7, 9, 1, 2, 10, 15, 6};
int[] arr2 = {1, 2, 3, 4, 5, 6, 7, 8};
int[] arr3 = {1};
int[] arr4 = {-5, 2,-1, 0, 11, 20, -20};
quickSort(arr1, 0, arr1.length-1);
quickSort(arr2, 0, arr2.length-1);
quickSort(arr3, 0, arr3.length-1);
quickSort(arr4, 0, arr4.length-1);
System.out.println(Arrays.toString(arr1));
System.out.println(Arrays.toString(arr2));
System.out.println(Arrays.toString(arr3));
System.out.println(Arrays.toString(arr4));
int[] arr5 = {7, 4, 6, 10, 8, 5, 1, 3, 2, 9};
int[] arr6 = {4, 5, 10, 3, 8, 2, 1, 7, 6, 9};
int[] arr7 = {100, 200, 33, 1, 3, 400, 45, 67, 80, 13};
int[] arr8 = {12, 34, 32, 14, 55, 37, 23, 9};
quickSort(arr5, 0, arr5.length-1);
quickSort(arr6, 0, arr6.length-1);
quickSort(arr7, 0, arr7.length-1);
quickSort(arr8, 0, arr8.length-1);
System.out.println(Arrays.toString(arr5));
System.out.println(Arrays.toString(arr6));
System.out.println(Arrays.toString(arr7));
System.out.println(Arrays.toString(arr8));
int[] arr9 = {};
int[] arr10 = {1, 1, 1, 1};
int[] arr11 = {1};
quickSort(arr9, 0, arr9.length-1);
quickSort(arr10, 0, arr10.length-1);
quickSort(arr11, 0, arr11.length-1);
System.out.println(Arrays.toString(arr9));
System.out.println(Arrays.toString(arr10));
System.out.println(Arrays.toString(arr11));
}
}
Resumen
Este laboratorio proporcionó una guía paso a paso para implementar el algoritmo QuickSort en Java. Aprendimos que el pivoteo es un paso crucial en QuickSort y que diferentes técnicas para seleccionar un pivote pueden afectar el rendimiento del algoritmo. QuickSort es mejor utilizado para ordenar grandes cantidades de datos. La complejidad de tiempo en el peor caso de QuickSort es O(N^2), mientras que su complejidad de tiempo en el caso promedio y el mejor caso es O(NLogN).
