Quicksort (por sí mismo) es bastante poco adecuado para situaciones en las que está ordenando datos en un orden proporcionado por el usuario, y el usuario no es del todo confiable.
Por ejemplo, supongamos que usa una mediana de tres Quicksort que siempre usa la mediana de los elementos primero, medio y último de su entrada para realizar la partición. Un usuario puede organizar los elementos para que en cada paso de partición, al menos dos de esos tres elementos sean los dos más pequeños o los dos más grandes en esa entrada. En este caso, el Quicksort se convertirá en un Slowsort, con un rendimiento aproximado de O (N ^ 2).
Si el usuario puede aplicar el tipo a una entrada razonablemente grande, esto puede dar un ataque de denegación de servicio simplemente usando mucha más capacidad de cómputo de lo que normalmente esperaría.
- ¿Cuál es la vida útil típica de una aplicación de software? ¿Existe alguna directriz de 'regla general' que usan los gerentes de producto o es tan particular para cada producto que tal directriz es inútil?
- ¿Qué aplicación usas más? ¿Qué hace?
- ¿Qué software de facturación (fuera de línea / en línea) es recomendable para nuevas empresas?
- ¿Cuáles son las aplicaciones más importantes en tu teléfono?
- ¿Cuáles son los mejores programas para crear álbumes de fotos impresos?
Algunas implementaciones de Quicksort también están sujetas a otros ataques. Por ejemplo, el qsort suministrado con AT&T UNIX durante bastante tiempo no intentó encontrar la más pequeña de las dos particiones que había creado, y ordenó eso primero. Para entradas como las anteriores que resultan en particiones muy desiguales, esto puede ser peligroso. Si el usuario se asegura de que la partición más grande se clasifique primero en cada paso, el uso de la pila se vuelve directamente proporcional al tamaño de la entrada (mientras que la clasificación de la partición más pequeña primero asegura que sea proporcional al logaritmo de base dos de la entrada).
En una biblioteca estándar moderna, generalmente puede esperar ver un algoritmo modificado como introsort, que realiza un seguimiento de la profundidad de recursión y si ve que la profundidad excede un umbral predeterminado, cambiará a una ordenación de montón (la ordenación de montón es típicamente más lento que Quicsksort, pero es realmente O (N log N), es decir, incluso en el peor de los casos, su complejidad sigue siendo O (N log N).
Tenga en cuenta que Introsort no es la única alternativa para esta situación. Por ejemplo, el pdqsort (orlp / pdqsort) se introdujo recientemente con la intención de garantizar el mal comportamiento en el peor de los casos, pero manteniendo algo cercano al rendimiento esperado de Quicksort, incluso en los casos malos. Es lo suficientemente nuevo como para dudar en decir que es una panacea para todas las entradas posibles, pero creo que al menos es bastante interesante.
