El quicksort multiclave , también conocido como quicksort de tres vías por radix , [1] es un algoritmo para ordenar cadenas . Este híbrido de quicksort y radix sort fue sugerido originalmente por P. Shackleton, como se informó en uno de los artículos seminales de CAR Hoare sobre quicksort ; [2] : 14 su encarnación moderna fue desarrollada por Jon Bentley y Robert Sedgewick a mediados de la década de 1990. [3] El algoritmo está diseñado para explotar la propiedad de que en muchos problemas, las cadenas tienden a tener prefijos compartidos .
Uno de los usos del algoritmo es la construcción de matrices de sufijos , por lo que fue uno de los algoritmos más rápidos en 2004. [4]
El algoritmo de ordenación rápida de tres vías ordena una matriz de N ( punteros a) cadenas en orden lexicográfico . Se supone que todas las cadenas tienen la misma longitud K ; si las cadenas tienen una longitud variable, deben rellenarse con elementos adicionales que sean menores que cualquier elemento de las cadenas. [a] El pseudocódigo para el algoritmo es entonces [b]
El algoritmo sort(a: matriz de cadenas, d: entero) es si length(a) ≤ 1 o d ≥ K entonces devuelve p := pivote(a, d) i, j := partición(a, d, p) (Obsérvese la asignación simultánea de dos variables). ordenar(a[0:i), d) ordenar(a[i:j), d + 1) ordenar(a[j:longitud(a)), d)
A diferencia de la mayoría de los algoritmos de ordenación de cadenas que examinan muchos bytes de una cadena para decidir si una cadena es menor, igual o igual que otra cadena y luego centran su atención en otro par de cadenas, la ordenación rápida de múltiples claves examina inicialmente solo un byte de cada cadena de la matriz, byte d, inicialmente el primer byte de cada cadena. La llamada recursiva utiliza un nuevo valor de dy pasa una submatriz donde cada cadena de la submatriz tiene exactamente la misma parte inicial: los caracteres antes de character d.
La función pivot debe devolver un solo carácter. Bentley y Sedgewick sugieren elegir la mediana de a[0][d], ..., a[length(a)−1][d] o algún carácter aleatorio en ese rango. [3] La función de partición es una variante de la que se utiliza en el ordenamiento rápido de tres vías ordinario : reorganiza a de modo que todos los a[0], ..., a[i−1] tengan un elemento en la posición d que sea menor que p , a[i], ..., a[j−1] tengan p en la posición d , y las cadenas a partir de j tengan un elemento d 'ésimo mayor que p . (La función de partición original sugerida por Bentley y Sedgewick puede ser lenta en el caso de elementos repetidos; se puede utilizar una partición con la bandera nacional holandesa para aliviar esto. [5] )
Las implementaciones prácticas de ordenamiento rápido de múltiples claves pueden beneficiarse de las mismas optimizaciones que se aplican típicamente al ordenamiento rápido: pivoteo de mediana de tres, cambio a ordenamiento por inserción para matrices pequeñas, etc. [6]
Este artículo incorpora material de dominio público de Paul E. Black. "Multikey Quicksort". Diccionario de algoritmos y estructuras de datos . NIST .