javascript - ordenar - ¿Existe un método de caja negra para detectar si un algoritmo de clasificación es estable?
ordenamiento de burbuja js (4)
En JavaScript (de alguna manera aplicable en otra parte), donde no sabe en qué implementación de destino se está ejecutando su código, hay una manera de detectar características si el algoritmo de clasificación subyacente (de Array.sort ) es estable o no, sabiendo solo que sigue la especificación ?
Pude encontrar 2 pruebas en el kit web (1) (2) , pero ¿qué tan confiables son esas pruebas? (¿Se podría hacer esta verificación con un PCP ?) Estoy buscando una solución que sea matemáticamente válida.
Este es un problema difícil, ya que un algoritmo de clasificación más avanzado puede cambiar los subalgoritmos según la longitud de la matriz de origen (como Timsort). He estado confundido ya que todas las pruebas que he realizado han demostrado que la ordenación de Google Chrome es estable, pero toda la documentación que he visto dice que es inestable ( la fuente te dirá por qué).
(Normalmente, utilizo esta estrategia para hacer que mi ordenación sea estable; tiene un impacto en el rendimiento pequeño pero a veces notable)
Código fuente para clasificar en varias implementaciones:¿Por qué arriesgarlo? Para la mayoría de los conjuntos de datos razonables, una implementación javascript de la ordenación de fusión debería ser lo suficientemente rápida. Recoge un par y haz un benchmark con ellos y usa el mejor.
Ejecutar una pequeña prueba interna, para comprobar? Puede usar el ejemplo de "cartas de juego por rango, luego por traje" de Wikipedia para verificar la estabilidad.
Consulte: https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
No sé cuántas tarjetas necesitas para verificar la estabilidad, ¿tal vez 5 o menos?
La prueba de caja negra no se puede usar para determinar que un programa satisface cualquier criterio a menos que pueda probar todas las entradas posibles relevantes para el criterio. Una caja negra es libre de tener simplemente una tabla de búsqueda que asigna entradas a salidas (vea el error de Pentium FDIV para un error en la tabla de búsqueda del mundo real), por lo que no puede estar seguro de que sus pruebas excluyan la posibilidad de que alguna otra entrada desencadene una violación.
Matemáticamente sonoro, ¿eh? Eso requeriría que cada camino en el algoritmo se demuestre que sea estable, y cada combinación de ellos. Para cualquier dato posible.
Seguro que existen algoritmos como ese, pero lo más probable es que fueron creados para cumplir con ese requisito. Así que si lo es, probablemente dice que está en algún lugar.
En cuanto a una prueba para probar algo así, eso probablemente se encuentre bajo problemas similares como un problema de detención.