2009-12-04 22 views
8

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é.Algoritmo de análisis de ordenamiento previo?

¿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.

+1

Esta lentitud de la secuencia rápida con secuencias preordenadas es solo un problema, AFAIK, si la implementación es demasiado simple con respecto a la elección de un elemento de pivote. Ver http://www.cprogramming.com/tutorial/computersciencetheory/quicksort.html por ejemplo. – Dirk

Respuesta

9

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".

+0

+1 para el enlace timsort –

+0

+1 wow, timsort se ve bastante limpio. – wowest

0

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.

+2

Ese es un buen punto, pero si el pase de análisis es O (n), no dominará el tiempo de clasificación asintótico. Y si puede ayudar a evitar un O (n^2) peor tiempo de clasificación, podría ser un beneficio neto en el tiempo de clasificación para grandes conjuntos de datos. – ddaa

+1

@ddaa: Eso sería cierto para los géneros de comparación, pero la clasificación O (n) es posible con Clasificación de cubo o Clasificación de cubo. Si incluimos estos algoritmos, el tiempo de ordenación podría estar dominado por el tiempo de análisis ... –

+1

@Jason: No realizaría este análisis con los datos que está a punto de clasificar por barrido. La pregunta es acerca de elegir entre la ordenación rápida y la ordenación por inserción, y usted está planeando hacer ninguna ... –

0

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.

+0

Su mejor caso sigue siendo O (N log N), donde el tipo de inserción es O (N) para datos casi ordenados. – wowest

0

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).

3

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".

0

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.

0

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.

+0

pero la muestra falla si se ordena 1 registro en cada N, pero el registro de +1 en cada N no lo está. es posible que aún tenga que leer cada registro para ver si UNO de ellos no muestreados está descompuesto. – skamradt

+0

De acuerdo, pero estadísticamente hay muy pocas posibilidades de que la muestra se desvíe tanto de la población en general, especialmente si aleatorizas un poco N. –

0

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.)

+0

Desde mi punto de vista, el beneficio de una ordenación in situ no es tanto que ahorre * memoria *, ya que ahorra una asignación de memoria y, por lo tanto, no puede fallar. Por lo tanto, al ordenar una matriz, quicksort/heapsort/insertion sort/bubble sort tienen interfaces de usuario mejores que mergesort. Si se prefiriera mergesort a quicksort, entonces por supuesto se podría intentar asignar la memoria, y si falla, hacer un quicksort. Si de todos modos está asignando una matriz secundaria de punteros y clasificándolos, entonces está introduciendo la posibilidad de fallas allí, y por lo tanto podría permitir fallas en otros lugares. –

+0

@SteveJessop Ese es un buen punto. Sin embargo, esa preocupación, aunque sigue siendo significativa en algunos casos, también es un poco anticuada. Estoy de acuerdo en que no es trivial que el entorno externo asigne memoria de manera justa a cada programa cliente o función que lo desee. Sin embargo, incluso eso ha mejorado con el tiempo en muchos entornos. –

+0

No creo que sea realmente una cuestión de equidad, tanto como lo que sucede cuando se acaba, y si usted es robusto para eso. Si la asignación puede fallar, escriba su programa de una manera. Si, en cambio, el SO saca algo del agua hasta que tenga suficiente memoria para satisfacer la solicitud o el error de página en el primer acceso, entonces usted escribe su programa de otra manera. Algunos idiomas toman un camino intermedio, donde en teoría usted * podría * atrapar excepciones de falta de memoria y continuar, pero en la práctica no lo hace, deja que la excepción lo mate. Supongo que podría considerarse la forma "actualizada" de hacerlo ;-) –

Cuestiones relacionadas