Ordenación rápida bidireccional

El algoritmo de ordenación rápida bidireccional es una versión mejorada de la ordenación rápida aleatorizada. El proceso de partición utiliza dos índices (i, j) para recorrer el array, y coloca los<velementos a la izquierda de la posición apuntada por el índice i, y coloca los>velementos a la derecha de la posición apuntada por el índice j,vrepresenta el valor pivote.

Instrucciones de aplicabilidad

La complejidad temporal y espacial es la misma que la de la ordenación rápida aleatorizada. Para arrays con muchos elementos repetidos, usar la ordenación rápida aleatorizada de la sección anterior es muy ineficiente; después de la partición, las longitudes de los subarrays de datos mayores o menores que el pivote pueden quedar extremadamente desequilibradas, e incluso puede degenerar enO(n*2)un algoritmo de complejidad temporal O(n^2). Para este caso, se puede utilizar el algoritmo de ordenación rápida bidireccional.

Diagrama del proceso

Usando dos índices (i, j) para recorrer nuestra secuencia, colocamos los<=velementos a la izquierda de la posición apuntada por el índice i, y colocamos los>=velementos a la derecha de la posición apuntada por el índice j, equilibrando los subarrays de ambos lados.

Código de ejemplo en Java

Descarga del paquete de código fuente:Download

Código del archivo QuickSort2Ways.java:

package ejemplo;

/**
* Ordenación rápida bidireccional
 */
public class QuickSort2Ways {

    // Código central --- inicio
    private static int partition(Comparable[] arr, int l, int r){
        // Elegir aleatoriamente un valor como pivote en el rango arr[l...r]
        swap( arr, l , (int)(Math.random()*(r-l+1))+l );
        Comparable v = arr[l];
        // arr[l+1...i) <= v; arr(j...r] >= v
        int i = l+1, j = r;
        while( true ){
            while( i <= r && arr[i].compareTo(v) < 0 )
                i ++;
            while( j >= l+1 && arr[j].compareTo(v) > 0 )
                j --;
            if( i > j )
                break;
            swap( arr, i, j );
            i ++;
            j --;
        }
        swap(arr, l, j);
        return j;
    }
    // Código central --- fin

    // Ordenar recursivamente el rango arr[l...r] usando ordenación rápida
    private static void sort(Comparable[] arr, int l, int r){
        if (l >= r) {
            return;
        }
        int p = partition(arr, l, r);
        sort(arr, l, p-1 );
        sort(arr, p+1, r);
    }

    public static void sort(Comparable[] arr){

        int n = arr.length;
        sort(arr, 0, n-1);
    }

    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    // Probar QuickSort
    public static void main(String[] args) {

        // El algoritmo de ordenación rápida bidireccional también es un algoritmo de complejidad O(n log n)
        // Puede procesar fácilmente datos del orden de 1 millón en menos de 1 segundo

        // Quick Sort también es un algoritmo de complejidad O(n log n)
        // Puede procesar fácilmente datos del orden de 1 millón en menos de 1 segundo
        int N = 1000000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        sort(arr);
        SortTestHelper.printArray(arr);

    }
}

Explicación detallada del principio del algoritmo

El núcleo de la ordenación rápida bidireccional reside en sumétodo de partición de dos punteros. A diferencia de la ordenación rápida de una vía (que solo escanea desde un extremo), usa dos punteros que escanean desde el principio y el final del subarray a ordenar hacia el centro, asegurando que los elementos iguales no sean empujados todos hacia un solo lado.

Núcleo: proceso de partición bidireccional

Supongamos que queremos ordenar el arrayarren el que los índices desdeleftllegarrightconstituyen la parte a ordenar.

Selección del valor pivote: desdearr[left...right]elegir aleatoriamente un elemento como valor pivote.pivot. La aleatorización tiene como objetivo evitar el peor caso en arrays ordenados.

Inicialización de los punteros：

  • i = left + 1: el puntero que escanea de izquierda a derecha, buscando el primermayor o igual a pivotelemento.
  • j = right: el puntero que escanea de derecha a izquierda, buscando el primermenor o igual a pivotelemento.

Bucle de escaneo e intercambio：

  • whileEl bucle, con la condicióni <= j。
  • el bucle internowhilewhile: haga queise mueva continuamente hacia la derecha, hasta quearr[i] >= pivot。
  • el bucle internowhilewhile: haga quejse mueva continuamente hacia la izquierda, hasta quearr[j] <= pivot。
  • En este punto,arr[i]es un elemento "grande" que no debería estar en la mitad izquierda,arr[j]es un elemento "pequeño" que no debería estar en la mitad derecha.
  • Si en este momentoi <= j, entonces intercambiearr[i]yarr[j], luegoi++, j--, continúe con el bucle externo.

Colocación del pivote y retorno del punto de partición：

  • Cuando el bucle termina,iyjse han cruzado (j < i). En este momentoarr[left](es decir, el pivote) necesita ser colocado en la posición correcta.
  • va aarr[left]yarr[j]Intercambie. Porquejla posición final donde se detiene, cuyo elemento apuntado esel último elemento menor o igual que el pivote.
  • Devolverjcomo nuevo punto de partición. En este momento,arr[left...j-1] <= pivot，arr[j+1...right] >= pivot, yarr[j] == pivot。

Ordenación recursiva

Una vez obtenido el punto de particiónp, para el subarray izquierdoarr[left...p-1]y para el subarray derechoarr[p+1...right]se ejecuta recursivamente el proceso anterior, hasta que la longitud del subarray sea 1.

Implementación del código

Entendamos concretamente la ordenación rápida bidireccional mediante una implementación completa en Java.

1. Función principal de ordenación

Ejemplo

public class TwoWayQuickSort {

    // Interfaz pública de ordenación
    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return; // Manejo de casos límite: si el array está vacío o tiene un solo elemento, no necesita ordenación
        }
        quickSort(arr, 0, arr.length - 1); // Llamar a la función recursiva de ordenación rápida
    }

    // Función recursiva de ordenación rápida
    private static void quickSort(int[] arr, int left, int right) {
        // Condición de terminación recursiva: cuando el límite izquierdo es mayor o igual que el límite derecho, el subarray ya está ordenado o vacío
        if (left >= right) {
            return;
        }
       
        // Paso clave: realizar la partición bidireccional y devolver el índice del punto de partición
        int p = partition(arr, left, right);
       
        // Ordenar recursivamente la mitad izquierda (left, p-1)
        quickSort(arr, left, p - 1);
        // Ordenar recursivamente la mitad derecha (p+1, right)
        quickSort(arr, p + 1, right);
    }
}

2. Núcleo: función de partición bidireccional

Esta es la parte central del algoritmo; por favor, estúdiala detenidamente junto con el diagrama de flujo y los comentarios anteriores.

Ejemplo

    // Función de partición bidireccional
    private static int partition(int[] arr, int left, int right) {
        // 1. Seleccionar aleatoriamente el pivote e intercambiarlo con la posición left, para evitar el peor caso en arrays ordenados
        int randomIndex = left + (int)(Math.random() * (right - left + 1));
        swap(arr, left, randomIndex);
        int pivot = arr[left]; // Valor pivote
       
        // 2. Inicializar los dos punteros
        // i: escanea de izquierda a derecha, buscando elementos >= pivot
        // j: escanea de derecha a izquierda, buscando elementos <= pivot
        int i = left + 1;
        int j = right;
       
        // 3. Bucle principal: mientras i y j no se hayan cruzado
        while (i <= j) {
            // 3.1 Mover el puntero izquierdo i: encontrar el primer elemento >= pivot
            // Nota: límite i <= right, para evitar salir del array
            while (i <= right && arr[i] < pivot) {
                i++;
            }
            // 3.2 Mover el puntero derecho j: encontrar el primer elemento <= pivot
            // Nota: límite j >= left+1, porque la posición left es el propio pivot
            while (j >= left + 1 && arr[j] > pivot) {
                j--;
            }
           
            // 3.3 Comprobar el estado de los punteros
            // Si i > j, el escaneo ha terminado y las particiones izquierda y derecha están listas, no es necesario intercambiar
            if (i > j) {
                break;
            }
           
            // 3.4 Intercambiar arr[i] y arr[j]
            // En este momento arr[i] >= pivot, arr[j] <= pivot; intercambiarlos hace que los elementos grandes y pequeños vuelvan a su lugar
            swap(arr, i, j);
            // Después del intercambio, mover los punteros para continuar escaneando
            i++;
            j--;
        }
       
        // 4. Colocar el pivote en su posición final correcta j
        // Después del bucle, j apunta al último elemento <= pivot
        swap(arr, left, j);
       
        // 5. Devolver el índice j del punto de partición
        return j;
    }
   
    // Función auxiliar: intercambia la posición de dos elementos en el array
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

3. Pruebas y verificación

Probemos nuestra implementación con un array que contiene elementos repetidos.

Ejemplo

public class Main {
    public static void main(String[] args) {
        // Caso de prueba 1: array con muchos elementos repetidos
        int[] arr1 = {4, 2, 2, 8, 3, 3, 1, 5, 3, 2};
        System.out.println("Antes de ordenar: " + Arrays.toString(arr1));
        TwoWayQuickSort.sort(arr1);
        System.out.println("Después de ordenar: " + Arrays.toString(arr1));
       
        // Caso de prueba 2: array grande generado aleatoriamente
        int[] arr2 = new int[20];
        Random rand = new Random();
        for (int i = 0; i < arr2.length; i++) {
            arr2[i] = rand.nextInt(50); // Generar números aleatorios entre 0 y 49, es muy probable que haya repetidos
        }
        System.out.println("\n"Antes de ordenar el array aleatorio: " + Arrays.toString(arr2));
        TwoWayQuickSort.sort(arr2);
        System.out.println("Después de ordenar el array aleatorio: " + Arrays.toString(arr2));
       
        // Verificar si el resultado de la ordenación es correcto
        for (int i = 1; i < arr2.length; i++) {
            if (arr2[i] < arr2[i-1]) {
                System.out.println("¡Error de ordenación!");
                return;
            }
        }
        System.out.println("¡Verificación de ordenación superada!");
    }
}

Ejemplo de salida de datos de prueba：

排序前: [4, 2, 2, 8, 3, 3, 1, 5, 3, 2]
排序后: [1, 2, 2, 2, 3, 3, 3, 4, 5, 8]

随机数组排序前: [17, 33, 12, 48, 8, 2, 41, ...]
随机数组排序后: [2, 8, 12, 17, 33, 33, 41, 48, ...]
排序结果验证通过！

Análisis y comparación de algoritmos

Complejidad temporal

  • Caso promedio: $O(n \log n)$. La ordenación rápida bidireccional distribuye los elementos repetidos de manera equilibrada, haciendo que el árbol de recursión esté relativamente balanceado.
  • Peor caso: $O(n^2)$. Aunque la selección aleatoria del pivote reduce en gran medida la probabilidad, cuando cada partición está extremadamente desequilibrada (por ejemplo, cada vez el pivote es el valor mínimo o máximo actual), aún puede aparecer el peor caso.
  • Mejor caso：$O(n \log n)$. Cada partición puede dividir el arreglo de manera uniforme.

Complejidad espacial

  • Principalmente el espacio ocupado por la pila de llamadas recursivas.
  • La profundidad media es $O(\log n)$, y en el peor caso la profundidad es $O(n)$.
  • Por lo tanto,La complejidad espacial promedio es $O(\log n)$, y la peor es $O(n)$.。

Estabilidad

Quicksort (incluido el quicksort de doble vía) no es un algoritmo de ordenamiento estable. Porque durante el proceso de partición, el intercambio de elementos no adyacentes altera el orden relativo original de los elementos iguales.

Comparación entre ordenación rápida de una vía, bidireccional y de tres vías

Características Quicksort de una vía (Lomuto) Quicksort de doble vía Quicksort de triple vía
Método de partición Un solo puntero escanea de izquierda a derecha Dos punteros escanean desde ambos extremos hacia el centro Tres punteros, dividen el arreglo en<pivot, =pivot, >pivottres partes
Manejo de elementos repetidos Malo, puede provocar particiones desequilibradas Bueno, puede distribuir de manera equilibrada los elementos repetidos Óptimo, puede manejar de una vez todos los elementos iguales al valor pivote
Complejidad del código Simple Medio Ligeramente complejo
Escenarios de aplicación Enseñanza, sin/pocos elementos repetidos Uso general, especialmente adecuado para escenarios con posibles elementos repetidos Escenarios con gran cantidad de elementos repetidos

Más ejemplos de código

Otras extensiones