Arreglando esta implementación incorrecta de Bingo Sort
Mientras estudiaba el Ordenamiento por Selección, me encontré con una variante conocida como Ordenamiento Bingo. Según esta entrada de diccionario aquí, el Ordenamiento Bingo es:
Una variante del ordenamiento por selección que ordena elementos encontrando primero el valor más pequeño, luego moviendo repetidamente todos los elementos con ese valor a su ubicación final y encontrando el valor más pequeño para el siguiente paso.
Basándome en la definición anterior, he creado la siguiente implementación en Python:
def ordenamiento_bingo(array, ascendente=True):
from operator import lt, gt
def comp(x, y, func):
return func(x, y)
i = 0
while i < len(array):
valor_min = array[i]
j = i + 1
for k in range(i + 1, len(array), 1):
if comp(array[k], valor_min, (lt if ascendente else gt)):
valor_min = array[k]
array[i], array[k] = array[k], array[i]
elif array[k] == valor_min:
array[j], array[k] = array[k], array[j]
j += 1
i = j
return array
Sé que esta implementación tiene problemas. Cuando ejecuto el algoritmo en un array extremadamente pequeño, obtengo un array ordenado correctamente. Sin embargo, al ejecutar el algoritmo con un array más grande, obtengo un array que está mayormente ordenado pero con colocaciones incorrectas aquí y allá. Para replicar el problema en Python, se puede ejecutar el algoritmo con la siguiente entrada:
datos_prueba = [[randint(0, 101) for i in range(0, 101)],
[uniform(0, 101) for i in range(0, 101)],
["a", "aa", "aaaaaa", "aa", "aaa"],
[5, 5.6],
[3, 2, 4, 1, 5, 6, 7, 8, 9]]
for conjunto_datos in datos_prueba:
print(conjunto_datos)
print(ordenamiento_bingo(conjunto_datos, ascendente=True, mutation=True))
print("\n")
No puedo identificar el error ya que llevo mucho tiempo analizando este algoritmo y no soy realmente experto en estas cosas. No pude encontrar una implementación del Ordenamiento Bingo en línea, excepto un proyecto de graduación de pregrado escrito en 2020. Cualquier ayuda que pueda apuntarme en la dirección correcta sería muy apreciada.
davy.ai
Solución de problemas de la implementación de Bingo Sort
El Bingo Sort es una variante del algoritmo de ordenación por selección. Ordena los elementos encontrando el valor mínimo, moviendo todos los elementos con ese valor a su posición final, y luego encuentra el siguiente valor mínimo para el siguiente paso.
La implementación de Bingo Sort en Python proporcionada parece tener un problema con la ordenación de matrices más grandes, lo que resulta en colocaciones incorrectas. Para identificar el problema, el algoritmo se ejecuta en varios conjuntos de pruebas, incluyendo tipos enteros, flotantes y cadenas.
Al ejecutar la prueba, el algoritmo devolvió resultados que estaban en su mayoría ordenados pero con algunas colocaciones incorrectas. El problema puede ser un fallo en la forma en que el algoritmo maneja los elementos con el valor mínimo.
Para solucionar el problema, el código debe modificarse para mover todos los elementos con el valor mínimo a su posición final antes de pasar al siguiente valor mínimo. Una solución potencial podría ser realizar un seguimiento de los índices de los valores mínimos en una lista separada y mover todos los elementos a su posición final después de encontrar los valores mínimos para el paso actual.
Dado que el problema parece estar en la implementación de Python, puede ser útil ver otras implementaciones de Bingo Sort para comparar e identificar cualquier diferencia. El proyecto de pregrado proporcionado en las fuentes puede ser una buena referencia para esto.