Clasificación de cuentas

El algoritmo de ordenación por gravedad , también llamado ordenación por cuentas , es un algoritmo de ordenación natural desarrollado por Joshua J. Arulanandham , Cristian S. Calude y Michael J. Dinneen en 2002 y publicado en The Bulletin of the European Association for Theoretical Computer Science . ^{[ 1 ]} Tanto las implementaciones de hardware digital como analógica de la ordenación por cuentas pueden alcanzar un tiempo de ordenación de O ( n ); sin embargo, la implementación de este algoritmo tiende a ser significativamente más lenta en software y solo puede usarse para ordenar listas de enteros positivos . Además, parece que incluso en el mejor de los casos, el algoritmo requiere un espacio de O ( n ² ).

La operación de clasificación de cuentas se puede comparar con la forma en que las cuentas se deslizan sobre postes paralelos, como en un ábaco . Sin embargo, cada poste puede tener un número distinto de cuentas. Inicialmente, puede ser útil imaginar las cuentas suspendidas en postes verticales. En el Paso 1, se muestra dicha disposición utilizando n=5 filas de cuentas en m=4 postes verticales. Los números a la derecha de cada fila indican el número que representa dicha fila; las filas 1 y 2 representan el entero positivo 3 (porque cada una contiene tres cuentas), mientras que la fila superior representa el entero positivo 2 (ya que solo contiene dos cuentas). ^{[ notas 1 ]}

Si dejamos caer las cuentas, las filas representan ahora los mismos números enteros ordenados. La fila 1 contiene el número mayor del conjunto, mientras que la fila n contiene el menor. Si se ha seguido la convención mencionada anteriormente de que las filas contengan una serie de cuentas en los polos 1 a k y dejen vacíos los polos k +1 a m , esto seguirá siendo así.

En nuestro ejemplo físico, al permitir que las cuentas "caigan", los valores mayores de las filas superiores se propagan a las inferiores. Si el valor representado por la fila a es menor que el valor contenido en la fila a+1 , algunas de las cuentas de la fila a+1 caerán en la fila a ; esto sucederá con seguridad, ya que la fila a no contiene cuentas en esas posiciones que impidan la caída de las cuentas de la fila a+1 .

El mecanismo subyacente a la ordenación por abalorios es similar al de la ordenación por conteo ; el número de abalorios en cada polo corresponde al número de elementos con un valor igual o superior al índice de ese polo.

La clasificación de cuentas se puede implementar con cuatro niveles generales de complejidad, entre otros:

• O (1): Todas las cuentas se mueven simultáneamente en la misma unidad de tiempo, como ocurriría en el ejemplo físico simple anterior. Esta es una complejidad abstracta y no se puede implementar en la práctica.
• O (): En un modelo físico realista que utiliza la gravedad, el tiempo que tardan las cuentas en caer es proporcional a la raíz cuadrada de la altura máxima, que es proporcional a n.${\displaystyle {\sqrt {n}}}$
• O (n): Las cuentas se mueven fila por fila. Este es el caso utilizado en las soluciones de hardware analógicas y digitales .
• O (S), donde S es la suma de los enteros en el conjunto de entrada: Cada cuenta se mueve individualmente. Este es el caso cuando la ordenación de cuentas se implementa sin un mecanismo que ayude a encontrar espacios vacíos debajo de las cuentas, como en las implementaciones de software.

Al igual que el algoritmo de ordenación por palomas , el algoritmo de ordenación por cuentas es inusual porque, en el peor de los casos, puede ser más rápido que O ( n log n ), el rendimiento más rápido posible para un algoritmo de ordenación por comparación en el peor de los casos. Esto es posible porque la clave para el algoritmo de ordenación por cuentas siempre es un entero positivo y este algoritmo aprovecha su estructura.

Esta implementación está escrita en Python ; se asume que input_listserá una secuencia de enteros. La función devuelve una nueva lista en lugar de modificar la que se le pasa como argumento, pero se puede modificar fácilmente para que funcione de manera eficiente in situ.

def beadsort ( input_list ): """Ordenar cuentas.""" return_list = [] # Inicializa una 'lista transpuesta' para que contenga tantos elementos como # el valor máximo de la entrada; en efecto, toma la columna 'más alta' # de cuentas de entrada y la coloca plana transposed_list = [ 0 ] * max ( input_list ) for num in input_list : # Para cada elemento (cada 'columna de cuentas') de la lista de entrada, # 'coloca las cuentas planas' incrementando tantos elementos de la # lista transpuesta como la altura de la columna. # Estos se acumularán sobre las adiciones anteriores. transposed_list [: num ] = [ n + 1 for n in transposed_list [: num ]] # Ahora hemos soltado las cuentas. Para destransponer, contamos la # 'fila más baja' de cuentas soltadas, luego simulamos la eliminación de esta # fila restando 1 de cada 'columna' de la lista transpuesta. # Cuando una columna no alcanza la altura suficiente para la fila actual, # su valor en transposed_list será <= 0. for i in range ( len ( input_list )): # Contar valores > i es como sabemos cuántas cuentas hay en la # fila inferior actual. Tenga en cuenta que los booleanos de Python pueden # evaluarse como enteros; True == 1 y False == 0. return_list . append ( sum ( n > i for n in transposed_list )) # La lista resultante se ordena en orden descendente return return_list

También podemos implementar el algoritmo usando Java . ^{[ 2 ]}

public static void beadSort ( int [] a ) { // Encuentra el elemento máximo int max = a [ 0 ] ; for ( int i = 1 ; i < a . length ; i ++ ) { if ( a [ i ] > max ) { max = a [ i ] ; } } // Asignando memoria int [][] beads = new int [ a . length ][ max ] ; // Marca las cuentas for ( int i = 0 ; i < a . length ; i ++ ) { for ( int j = 0 ; j < a [ i ] ; j ++ ) { beads [ i ][ j ] = 1 ; } } // Mueve las cuentas hacia abajo for ( int j = 0 ; j < max ; j ++ ) { int sum = 0 ; para ( int i = 0 ; i < a . length ; i ++ ) { suma += cuentas [ i ][ j ] ; cuentas [ i ][ j ] = 0 ; } para ( int i = a . length - 1 ; i >= a . length - suma ; i -- ) { a[ i ] = j + 1 ; } } }

• "Bead-Sort: Un algoritmo de ordenación natural" (PDF) . Archivado del original (PDF) el 9 de agosto de 2017. Consultado el 1 de enero de 2005 . (114 KiB ) 
• Ordenación de cuentas en MGS Archivado el 28/07/2011 en Wayback Machine , una visualización de una ordenación de cuentas implementada en el lenguaje de programación MGS Archivado el 14/06/2009 en Wayback Machine
• Clasificación de cuentas en MathWorld
• Visualización interactiva de clasificación de cuentas