Un ordenamiento por bandera estadounidense es una variante eficiente y local del ordenamiento por radix que distribuye los elementos en contenedores. Los algoritmos de ordenamiento no comparativos, como el ordenamiento por radix y el ordenamiento por bandera estadounidense, se utilizan normalmente para ordenar objetos grandes, como cadenas, para los que la comparación no es una operación de tiempo unitario. [1] El ordenamiento por bandera estadounidense itera a través de los bits de los objetos, considerando varios bits de cada objeto a la vez. Para cada conjunto de bits, el ordenamiento por bandera estadounidense realiza dos pasadas a través de la matriz de objetos: primero para contar la cantidad de objetos que caerán en cada contenedor y segundo para colocar cada objeto en su contenedor. Esto funciona especialmente bien cuando se ordena un byte a la vez, utilizando 256 contenedores. Con algunas optimizaciones, es el doble de rápido que el ordenamiento rápido para conjuntos grandes de cadenas . [1]
El nombre de "clasificación de la bandera estadounidense" surge por analogía con el problema de la bandera nacional holandesa en el último paso: dividir eficientemente la matriz en muchas "franjas".
Los algoritmos de ordenación en general ordenan una lista de objetos según algún esquema de ordenación. A diferencia de los algoritmos de ordenación basados en comparación , como quicksort , el ordenamiento por bandera estadounidense se basa en comparar directamente los bytes (representación numérica) de los objetos subyacentes. Los algoritmos de ordenamiento in situ, incluido el ordenamiento por bandera estadounidense, se ejecutan sin asignar una cantidad significativa de memoria más allá de la utilizada por la matriz original. Esta es una ventaja significativa, tanto en ahorro de memoria como en tiempo ahorrado al copiar la matriz.
El ordenamiento por bandera estadounidense funciona dividiendo sucesivamente una lista de objetos en grupos según el primer dígito de su representación en base N (la base utilizada se denomina radix ) . Cuando N es 3, cada objeto se puede intercambiar en el grupo correcto utilizando el algoritmo de la bandera nacional holandesa . Sin embargo, cuando N es mayor, los objetos no se pueden intercambiar de inmediato en su lugar, porque se desconoce dónde debe comenzar y terminar cada grupo. El ordenamiento por bandera estadounidense soluciona este problema haciendo dos pasadas a través de la matriz. La primera pasada cuenta la cantidad de objetos que pertenecen a cada uno de los N grupos. Luego, el comienzo de cada grupo se calcula como la suma de los tamaños de los grupos anteriores. La segunda pasada coloca cada objeto en el grupo correcto.
La clasificación de la bandera estadounidense es más eficiente con un radio que sea una potencia de 2, porque se pueden utilizar operaciones de desplazamiento de bits en lugar de exponenciaciones costosas para calcular el valor de cada dígito. Al ordenar cadenas utilizando codificaciones de 8 o 7 bits como ASCII , es típico utilizar un radio de 256 o 128, lo que equivale a ordenar carácter por carácter. [1]
Vale la pena señalar que, en el caso de textos en alfabeto inglés puro, el histograma de recuentos siempre es disperso. Según el hardware, puede que valga la pena borrar los recuentos en correspondencia con la finalización de un depósito (como en el artículo original); o puede que valga la pena mantener un depósito activo de máximo y mínimo, o una estructura de datos más compleja adecuada para matrices dispersas. También es importante utilizar un método de ordenamiento más básico para conjuntos de datos muy pequeños, excepto en casos patológicos en los que las claves pueden compartir prefijos muy largos.
Lo más crítico es que este algoritmo sigue una permutación aleatoria y, por lo tanto, es particularmente poco amigable con la memoria caché para conjuntos de datos grandes. [2] [ fuente generada por el usuario ] Es un algoritmo adecuado junto con un algoritmo de fusión de k vías . [ cita requerida ] (El artículo original se escribió antes de que la memoria caché fuera de uso común).
american_flag_sort(Matriz, Base) para cada dígito D: # primer paso: calcular recuentos Cuenta <- ceros(Radix) Para el objeto X en Array: Cuenta [dígito D del objeto X en el radio base] += 1 # Calcular los desplazamientos de los depósitos Desplazamientos <- [ suma(Counts[0..i]) para i en 1..Radix] # intercambiar objetos en su lugar Para el objeto X en Array: Intercambia X con el depósito que comienza en Offsets[dígito D de X en el Radix base] Para cada cubo: american_flag_sort(Cubo, Base)
Este ejemplo escrito en el lenguaje de programación Python realizará la ordenación de la bandera estadounidense para cualquier base de 2 o mayor. Se prefiere la simplicidad de la exposición a la programación inteligente, por lo que se utiliza la función logarítmica en lugar de técnicas de desplazamiento de bits.
desde matemáticas importar piso , registro desde copiar importar copiardef get_radix_val ( x , dígito , base ): return int ( floor ( x / base ** dígito )) % basedef calculate_offsets ( a_list , start , end , digit , radix ): counts = [ 0 para _ en rango ( radix )] para i en rango ( start , end ): val = get_radix_val ( a_list [ i ], digit , radix ) counts [ val ] += 1 offset = start offsets = [ start ] para i en rango ( radix ) : offset + = counts [ i ] offsets.append ( offset ) return offsets def swap ( una_lista , desplazamientos , inicio , fin , dígito , base ): siguiente_libre = copy ( desplazamientos ) bloque_cur = 0 mientras bloque_cur < base : i = siguiente_libre [ bloque_cur ] si i >= desplazamientos [ bloque_cur + 1 ]: bloque_cur += 1 continuar valor_base = obtener_valor_base ( una_lista [ i ], dígito , base ) si valor_base != bloque_cur : intercambiar_a = siguiente_libre [ valor_base ] una_lista [ i ], una_lista [ intercambiar_a ] = una_lista [ intercambiar_a ], una_lista [ i ] siguiente_libre [ valor_base ] += 1def american_flag_sort_helper ( una_lista , inicio , fin , dígito , base ): desplazamientos = calculate_offsets ( una_lista , inicio , fin , dígito , base ) swap ( una_lista , desplazamientos , inicio , fin , dígito , base ) if dígito == 0 : return for i in range ( len ( desplazamientos ) -1 ): american_flag_sort_helper ( una_lista , desplazamientos [ i ], desplazamientos [ i + 1 ] , dígito - 1 , base ) def american_flag_sort ( una_lista , base ): para x en una_lista : assert type ( x ) == int máx_valor = máx ( una_lista ) máx_dígito = int ( floor ( log ( máx_valor , base ))) american_flag_sort_helper ( una_lista , 0 , len ( una_lista ), máx_dígito , base )
Este artículo incorpora material de dominio público de Paul E. Black. "Ordenación por bandera estadounidense". Diccionario de algoritmos y estructuras de datos . NIST .