Algoritmo de análisis de ordenamiento previo?

Question

Es una cuestión bien conocida con Quicksort que cuando el conjunto de datos está en orden de clasificación o casi en orden, el rendimiento se degrada horriblemente. En este caso, Insertion Sort, que normalmente es muy lento, es fácilmente la mejor opción. La pregunta es saber cuándo usar qué.

¿Hay un algoritmo disponible para ejecutar a través de un conjunto de datos, aplicar un factor de comparación y devolver un informe sobre qué tan cerca está el conjunto de datos en orden de clasificación? Prefiero Delphi/Pascal, pero puedo leer otros idiomas si el ejemplo no es demasiado complejo.

Answer 1

Como era de esperar, se piensa mucho en esto. La técnica de la mediana de tres significa que el peor comportamiento de quicksort no ocurre para los datos ordenados, sino para los casos menos obvios.

Introsort es bastante emocionante, ya que evita el peor caso cuadrático de quicksort. En lugar de su pregunta natural, "¿cómo puedo detectar que los datos están casi ordenados?", De hecho se pregunta a sí misma a medida que avanza "¿esto toma demasiado tiempo?". Si la respuesta es sí, cambia de quicksort a heapsort.

Timsort combina el tipo de combinación con el tipo de inserción, y funciona muy bien en datos ordenados o ordenados inversamente, y en datos que incluyen subconjuntos clasificados u ordenados inversamente.

Así que probablemente la respuesta a su pregunta es: "no necesita un análisis previo al paso, necesita un algoritmo de ordenación adaptable".

Answer 2

No he oído hablar de ningún análisis de clasificación previa, pero mi opinión es que si va a analizar el conjunto de datos para analizarlo, ya está reduciendo el rendimiento de su tiempo de clasificación general.

Answer 3

Una posible solución es tomar primero, último y el elemento medio en el rango de clasificación actual (durante la operación QuickSort) y elegir el medio como elemento pivote.

Answer 4

Para analizar completamente con el fin de decidir qué algoritmo usar, va a hacer casi todo el trabajo de clasificación. Podría hacer algo como verificar los valores en un pequeño porcentaje de índices aleatorios pero en aumento (es decir, analizar una pequeña muestra de los elementos).

Answer 5

También hay SmoothSort, que aparentemente es bastante complicado de implementar, pero varía entre O (N log N) y O (N) dependiendo de cómo estén ordenados los datos para empezar.

http://en.wikipedia.org/wiki/Smoothsort

largo PDF complicado: http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF

Sin embargo, si los datos es realmente enorme y hay que acceder a él en serie, mergesort es probablemente el mejor. Siempre es O (N log N) y tiene excelentes propiedades de "localidad".

Answer 6

Usted todavía tiene que ejecutar a través de todos los registros para determinar si su ordenados o no, por lo que para mejorar el rendimiento, comience con su primer disco y ejecutar aunque el resto hasta que sea aviso que algo no ordenadas correctamente, o el fin de la lista. Si encuentra una falla, solo ordene los elementos desde esa posición hasta el final (ya que el comienzo de la lista ya está ordenado).

En cada elemento de la segunda parte, verifique si el elemento es < que el último elemento en la primera parte y, de ser así, utilice una ordenación por inserción en SÓLO la primera parte. De lo contrario, Quicksort contra todos los demás elementos en la segunda parte. De esta forma, el género está optimizado para el caso específico.

Answer 7

QuickSort Beng un problema sólo cuando el conjunto de datos es enorme y ya ordenados sobre todo, me gustaría utilizar los siguientes heurística (a la espera de una solución completa soplado):

• No se moleste si el conjunto de datos es de tamaño por debajo del umbral.

• Si tiene un acceso rápido (indexado) a los registros (elementos) tome una muestra con 1 registro en cada N registros y vea si ya están ordenados. Debe ser lo suficientemente rápido para una muestra pequeña y luego puede decidir utilizar la ordenación rápida o no.

Answer 8

Para hacer un punto conceptual que las personas aún no han hecho: Quicksort es un algoritmo de divide y vencer de sentido común con un error obvio en casos raros. Supongamos que quiere ordenar una pila de documentos estudiantiles. (Lo que tengo que hacer con cierta regularidad). En el algoritmo de la solución rápida, escoge un papel, el pivote. Luego, divida los otros documentos según estén antes o después del pivote. Luego repítelo con los dos subpilares. ¿Cuál es el error? El pivote podría ser un nombre que está cerca de un extremo de la lista en lugar de en el medio, por lo que no logrará dividirlo en dos pilas.

Merge sort es otro algoritmo de dividir y vencer que funciona en un orden diferente. Puede fusionar dos listas ordenadas en tiempo lineal. Divida los documentos en dos pilas iguales o casi iguales, luego recursivamente clasifique cada una, luego fusione. Merge sort no tiene ningún error. Una razón por la que el quicksort es más popular que merge sort es histórico: Quicksort es rápido (generalmente) y funciona sin memoria adicional. Pero en estos días, puede ser más importante guardar comparaciones que guardar memoria, y la reorganización real a menudo se abstrae permutando punteros. Si las cosas siempre hubieran sido así, entonces sospecho que el tipo de fusión simplemente habría sido más popular que el quicksort. (Y tal vez agregar "rápido" al nombre era buen vendedor.)