algorithm - ordenamiento - ¿Qué algoritmos de ordenación proporcionan una aproximación aproximada/aproximada antes?
ordenamiento por intercambio (6)
¿Qué tal un radix de izquierda a derecha y parar un poco prematuramente (sin juego de palabras)?
este será el tiempo de ejecución Nb donde b es la cantidad de bits que decide examinar. Cuantos más bits examines, más ordenado será
sin clasificar:
5 0101
8 1000
4 0100
13 1101
1 0001
después de 1 bit (N):
5 0101
1 0001
4 0100
13 1101
8 1000
después de 2 bits (2N)
1 0001
5 0101
4 0100
8 1000
13 1101
y así...
¿Qué algoritmos de clasificación producen ordenamientos intermedios que son buenas aproximaciones?
Por "buena aproximación" me refiero a métricas como la tau de Kendall y la regla de Spearman para determinar qué tan "lejos" es una lista ordenada de otra (en este caso, del tipo exacto)
La aplicación particular que tengo en mente es en la que los humanos están haciendo una comparación subjetiva por pares y es posible que no puedan hacer todas las comparaciones n log n requeridas por, digamos, heapsort o el mejor caso de quicksort.
¿Qué algoritmos son mejores que otros para obtener la lista de forma aproximada / aproximada antes?
Es posible que desee verificar el algoritmo de clasificación de shell.
AFAIK es el único algoritmo que puedes usar con una comparación subjetiva (lo que significa que no tendrás ninguna pista sobre los valores de la mediana más o menos) que se acercará al tipo correcto en cada pasada.
Aquí hay más información http://en.wikipedia.org/wiki/Shell_sort
Ideé un algoritmo de clasificación NlgN que llamé "clasificación de torneos" hace algún tiempo, que encuentra los elementos de salida en orden (es decir, comienza por encontrar el primer elemento, luego encuentra el segundo elemento, etc.). No estoy seguro de que sea completamente práctico, ya que la sobrecarga de libros excede la de quicksort, merge sort, etc. pero en el benchmarking con 1,000,000 de elementos aleatorios, el recuento de comparación en realidad estuvo por debajo de una implementación estándar de biblioteca rápida (aunque no estoy seguro de cómo sería contra los más nuevos).
A los efectos de mi algoritmo, el "puntaje" de cada elemento es la cantidad de elementos que se sabe que es mejor que. Inicialmente, cada elemento tiene una puntuación de 0. Cuando se comparan dos elementos, el mejor elemento agrega a su puntaje el puntaje del otro elemento, más uno. Para ejecutar el algoritmo, declare que todos los artículos son "elegibles", y mientras quede más de un artículo elegible, compare los dos artículos elegibles con el puntaje más bajo y haga que el perdedor sea "inelegible". Una vez que todos los artículos menos uno han sido declarados inelegibles, envíe el artículo restante y luego declare elegibles todos los artículos que ese artículo haya "derrotado".
La cola de prioridad requerida para comparar los dos elementos de puntuación más baja plantea un nivel de contabilidad un tanto molesto, pero si uno ordena cosas que son caras de comparar, el algoritmo puede ser interesante.
Mi estudio completamente no científico y visual de los géneros en esta página indica que "Comb Sort" se ve bien. Parece estar llegando a una mejor aproximación con cada pase.
Sugeriría alguna versión de quicksort. Si sabe en qué rango están los datos que desea ordenar, puede seleccionar elementos dinámicos de manera inteligente y posiblemente dividir el problema en más de dos partes a la vez.
Tipo de burbuja, creo. La ventaja es que puede mejorar gradualmente el orden con barridos adicionales de los datos.