Bead sort , también llamado gravity sort , es un algoritmo de ordenamiento 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 digitales como analógicas de bead sort pueden lograr un tiempo de ordenamiento de O ( n ); sin embargo, la implementación de este algoritmo tiende a ser significativamente más lenta en software y solo se puede usar para ordenar listas de números enteros positivos . Además, parecería que incluso en el mejor de los casos, el algoritmo requiere espacio O ( n2 ) .
La operación de clasificación de cuentas se puede comparar con la manera 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 una disposición de este tipo 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 la fila en cuestión; 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 que las cuentas caigan, las filas representan ahora los mismos números enteros en orden. La fila 1 contiene el número más grande del conjunto, mientras que la fila n contiene el más pequeño. Si se ha seguido la convención mencionada anteriormente de filas que contienen una serie de cuentas en los polos 1.. k y dejando los polos k +1.. m vacíos, seguirá siendo el caso aquí.
La acción de dejar que las cuentas "caigan" en nuestro ejemplo físico ha permitido que los valores más grandes de las filas superiores se propaguen a las filas 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 es seguro que sucederá, ya que la fila a no contiene cuentas en esas posiciones para evitar que las cuentas de la fila a+1 caigan.
El mecanismo subyacente a la ordenación por cuentas es similar al que hay detrás de la ordenación por conteo ; la cantidad de cuentas en cada polo corresponde a la cantidad de elementos con un valor igual o mayor que el índice de ese polo.
La clasificación de cuentas se puede implementar con cuatro niveles generales de complejidad, entre otros:
Al igual que el ordenamiento por pigeonhole , el ordenamiento por cuentas es inusual en el sentido de que, en el peor de los casos, puede tener un rendimiento más rápido que O ( n log n ), el rendimiento más rápido posible para un ordenamiento por comparación en el peor de los casos. Esto es posible porque la clave para un ordenamiento por cuentas es siempre un entero positivo y el ordenamiento por cuentas explota su estructura.
Esta implementación está escrita en Python ; se supone que input_listserá una secuencia de números enteros. La función devuelve una nueva lista en lugar de modificar la que se le pasó, pero se puede modificar de forma trivial para que funcione en el lugar de manera eficiente.
def beadsort ( input_list ): """Ordenamiento de 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 descartado las cuentas. Para destransponer, contamos la # 'fila inferior' de cuentas descartadas, luego imitamos la eliminación de esta # fila restando 1 de cada 'columna' de la lista transpuesta. # Cuando una columna no alcanza el nivel suficiente para la fila actual, # su valor en transposed_list será <= 0. for i in range ( len ( input_list )): # Contar valores > i es como decimos cuántas cuentas hay en la # 'fila inferior' actual. Tenga en cuenta que los valores booleanos de Python se pueden # evaluar como números 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 ; } } }