Bandera estadounidense clasificada

El algoritmo de ordenación por bandera americana es una variante eficiente e in situ del algoritmo de ordenación por radix que distribuye los elementos en cubetas. Los algoritmos de ordenación no comparativos, como la ordenación por radix y la ordenación por bandera americana, se utilizan normalmente para ordenar objetos grandes, como cadenas de caracteres, para los que la comparación no es una operación de tiempo unitario. ^{[ 1 ]} La ordenación por bandera americana itera a través de los bits de los objetos, considerando varios bits de cada objeto a la vez. Para cada conjunto de bits, la ordenación por bandera americana realiza dos pasadas a través del array de objetos: primero para contar el número de objetos que caerán en cada cubeta, y segundo para colocar cada objeto en su cubeta. Esto funciona especialmente bien cuando se ordena un byte a la vez, utilizando 256 cubetas. Con algunas optimizaciones, es el doble de rápido que el algoritmo de ordenación rápida para grandes conjuntos de cadenas de caracteres . ^{[ 1 ]}

El nombre " clasificación de la bandera estadounidense" proviene de una analogía con el problema de la bandera nacional holandesa en el último paso: dividir eficientemente el conjunto 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 comparaciones , como Quicksort , el algoritmo de la bandera americana se basa en la comparación directa de los bytes (representación numérica) de los objetos subyacentes. Los algoritmos de ordenación in situ, incluido el algoritmo de la bandera americana, se ejecutan sin asignar una cantidad significativa de memoria más allá de la utilizada por el array original. Esto supone una ventaja importante, tanto en ahorro de memoria como en ahorro de tiempo al evitar la copia del array.

El algoritmo de ordenación de la bandera estadounidense funciona dividiendo sucesivamente una lista de objetos en cubetas 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 la cubeta correcta utilizando el algoritmo de la bandera nacional holandesa . Sin embargo, cuando N es mayor, los objetos no se pueden intercambiar inmediatamente, ya que se desconoce dónde debe comenzar y terminar cada cubeta. El algoritmo de ordenación de la bandera estadounidense resuelve este problema realizando dos pasadas por el array. La primera pasada cuenta el número de objetos que pertenecen a cada una de las N cubetas. El inicio de cada cubeta se calcula como la suma de los tamaños de las cubetas precedentes. La segunda pasada coloca cada objeto en la cubeta correcta.

La ordenación de la bandera estadounidense es más eficiente con una base que sea potencia de 2, ya que se pueden usar operaciones de desplazamiento de bits en lugar de costosas exponenciaciones para calcular el valor de cada dígito. Al ordenar cadenas usando codificaciones de 8 o 7 bits como ASCII , es típico usar una base de 256 o 128, lo que equivale a ordenar carácter por carácter. ^{[ 1 ]}

Ordenar_bandera_americana(Array, Radix) para cada dígito D: # primera pasada: calcular recuentos Recuentos <- ceros(Radix) para el objeto X en Array: Recuento[dígito D del objeto X en base Radix] += 1 # calcular desplazamientos de cubeta Desplazamientos <- [ suma(Recuentos[0..i]) para i en 1..Radix] # intercambiar objetos para colocarlos en su lugar para el objeto X en Array: Intercambiar X al cubo que comienza en Offsets[dígito D de X en la base Radix] para cada Cubo: Ordenar bandera americana(Bucket, Radix) 

importar copiar importar matemáticasdef get_radix_val ( x : int , digit : int , radix : int ) -> int : return int ( math . floor ( x / radix ** digit )) % radixdef compute_offsets ( numbers : list [ int ], start : int , end : int , digit : int , radix : int ) -> list [ int ]: counts : list [ int ] = [ 0 for _ in range ( radix )] for i in range ( start , end ): val = get_radix_val ( numbers [ i ], digit , radix ) counts [ val ] += 1desplazamiento : int = inicio desplazamientos : lista [ int ] = [ inicio ] para i en rango ( radix ) : desplazamiento + = recuentos [ i ] desplazamientos.append ( desplazamiento )desplazamientos de retornodef swap ( numbers : list [ int ], offsets : list [ int ], start : int , end : int , digit : int , radix : int ) -> None : next_free : list [ int ] = copy . copy ( offsets ) cur_block : int = 0mientras cur_block < radix : i : int = next_free [ cur_block ] si i >= offsets [ cur_block + 1 ]: cur_block += 1 continuarradix_val : int = get_radix_val ( numbers [ i ], digit , radix ) if radix_val != cur_block : swap_to : int = next_free [ radix_val ] numbers [ i ], numbers [ swap_to ] = numbers [ swap_to ], numbers [ i ]siguiente_libre [ radix_val ] += 1def american_flag_sort_helper ( numbers : list [ int ], start : int , end : int , digit : int , radix : int ) -> None : offsets : list [ int ] = compute_offsets ( numbers , start , end , digit , radix ) swap ( numbers , offsets , start , end , digit , radix )Si el dígito es igual a 0 : devolverpara i en rango ( len ( offsets ) - 1 ): american_flag_sort_helper ( números , offsets [ i ], offsets [ i + 1 ], dígito - 1 , radix )def american_flag_sort ( numbers : list [ int ], radix : int ) -> None : for x in numbers : assert isinstance ( x , int )max_val : int = max ( números ) max_dígito : int = int ( matemáticas.piso ( matemáticas.log ( max_val , radix ) ) )​​american_flag_sort_helper ( números , 0 , len ( números ), max_digit , radix )

• Clasificación por cubos
• Ordenación rápida multiclave
• Ordenación por radix
• Problema con la bandera nacional holandesa