La ordenación rápida de varias teclas , también conocida como ordenación rápida de base de tres vías , [1] es un algoritmo para ordenar cadenas . Este híbrido de ordenamiento rápido y ordenamiento por radix fue sugerido originalmente por P. Shackleton, como se informa en uno de los artículos seminales de CAR Hoare sobre ordenamiento rápido ; [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]
Descripción
El algoritmo de ordenación rápida de radix 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]
algoritmo de tipo (a: array de cadenas, d: número entero) es si la longitud (a) ≤ 1 o d ≥ K luego regreso p: = pivote (a, d) i, j: = partición (a, d, p) (Nótese una asignación simultánea de dos variables). ordenar (a [0: i), d) ordenar (a [i: j), d + 1) ordenar (a [j: longitud (a)), d)
La función pivote debe devolver un solo carácter. Bentley y Sedgewick sugieren elegir la mediana de a [0] [d], ..., a [longitud (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 usa en la ordenación rápida de tres vías ordinaria : reorganiza un modo que todos a [0], ..., a [i − 1] tienen un elemento en la posición d que es menor que p , a [i], ..., a [j − 1] tienen p en la posición d , y las cadenas de j en adelante tienen un d 'elemento 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 de bandera nacional holandesa para aliviar esto. [5] )
Las implementaciones prácticas de la ordenación rápida de varias teclas pueden beneficiarse de las mismas optimizaciones que normalmente se aplican a la ordenación rápida: pivoteo de mediana de tres, cambio a ordenación por inserción para arreglos pequeños, etc. [6]
Ver también
- Clasificación de bandera estadounidense : otra variante de clasificación de radix que es rápida para la clasificación de cadenas
- Árbol de búsqueda ternario : el ordenamiento rápido de radix de tres vías es isomorfo a esta estructura de datos de la misma manera que el ordenamiento rápido es isomorfo a los árboles de búsqueda binarios [3]
Notas
- ^ Una forma de hacerlo sin alterar la representación en memoria de las cadenas es indexarlas usando una función que devuelva -1 o algún otro valor pequeño cuando el índice está fuera de rango.
- ^ Las matrices y cadenas tienen un índice cero. Una porción de matriza [i: j) produce el subarreglo de un de yo a j (exclusivo) y se supone que es una operación de tiempo constante sin copia.
Referencias
- ^ Este artículo incorpora material de dominio público del documento NIST : Black, Paul E. "Multikey Quicksort" . Diccionario de algoritmos y estructuras de datos .
- ^ Hoare, CAR (1962). "Clasificación rápida" . Computación. J. 5 (1): 10–16. doi : 10.1093 / comjnl / 5.1.10 .
- ^ a b c Bentley, Jon; Sedgewick, Robert (1997). Algoritmos rápidos para ordenar y buscar cadenas (PDF) . Proc. Anual ACM-SIAM Symp. sobre algoritmos discretos (SODA). ISBN 0-89871-390-0.
- ^ Manzini, Giovanni; Ferragina, Paolo (2004). "Ingeniería de un algoritmo de construcción de matriz de sufijo ligero". Algoritmica . 40 : 33–50. CiteSeerX 10.1.1.385.5959 . doi : 10.1007 / s00453-004-1094-1 .
- ^ Kim, Eunsang; Park, Kunsoo (2009). "Mejora de Quicksort de varias claves para ordenar cadenas con muchos elementos iguales". Cartas de procesamiento de información . 109 (9): 454–459. doi : 10.1016 / j.ipl.2009.01.007 .
- ^ Bentley, Jon; Sedgewick, Robert (1998). "Clasificación de cadenas con Quicksort Radix de tres vías" . Diario del Dr. Dobb .