Algoritmo de clasificación Divide y Vencerás QuickSort eficiente

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).