He estado leyendo sobre Quicksort y he encontrado que a veces se lo conoce como "Deterministic Quicksort".¿Qué es un Quicksort determinístico?
¿Es esta una versión alternativa del Quicksort normal? ¿Cuál es la diferencia entre un Quicksort normal y un Quicksort determinístico?
El Quicksort ordinario ("determinista") puede tener un comportamiento muy pobre en determinados conjuntos de datos (como ejemplo, una implementación que elige el primer elemento no clasificado tiene O (n^2) complejidad de tiempo en datos ya ordenados).
El Quicksort aleatorizado (que selecciona un pivote aleatorio, en lugar de elegir de manera determinista) se usa a veces para proporcionar un mejor rendimiento esperado sobre todos los conjuntos de datos.
Quicksort se ejecuta en O(n log n) esperado/tiempo promedio, pero O(n^2) peor caso. Esto ocurre si el pivote elegido es consistentemente el mínimo o el máximo.
Idealmente, debe seleccionar la mediana como su pivote. Si encontrar la mediana directamente es demasiado costoso (por lo general, este es el caso si estás tratando de usar la oferta), lo que comúnmente se hace es tomar la mediana de tres elementos pivote potenciales, o simplemente elegir un elemento aleatorio como pivote .
El último método hace que quicksort no sea determinista debido a la aleatoriedad inherente al proceso de selección de pivote.
Además, creo que vale la pena mencionar que, contrariamente a lo que usted pregunta, la oferta determinística tiende a ser la vía de acceso "normal", al menos con respecto a lo que se enseña en las clases porque es más fácil El pivote aleatorio suele ser una decisión tomada en el momento de la implementación con la esperanza de mejorar el rendimiento general del algoritmo. –
Su fuente puede (y debe) dar su propia definición, pero generalmente una ruta rápida determinista es aquella en la que el pivote se elige a través de una fórmula que no depende de números aleatorios. Por ejemplo, siempre elige el elemento medio o siempre el primero, o algo como esto. Esto significa que su rendimiento siempre será el mismo (en teoría, de todos modos, aunque en la práctica la diferencia no debería ser demasiado grande) sin importar cuántas veces lo ejecutes en la misma entrada. Un quicksort aleatorizado significa que está utilizando números aleatorios al elegir el pivote, lo que significa que no se puede (fácilmente) predecir el rendimiento para diferentes ejecuciones en la misma entrada.
Tiene que ver con la partición (o el paso de división de la famosa división y conquista que se utiliza en la clasificación rápida). Si cada vez que se utiliza el último (o el primer elemento o elemento en cualquier posición, solo que tiene que ser la misma posición cada vez que se divide el conjunto de datos) como pivote para la partición, entonces es Deterministic Quick sort. Si el pivote se escoge al azar, se clasificará de forma aleatoria.
Aquí hay un lecture note que lo pone al otro lado.
espero que ayude
aplausos
En general, un algoritmo de ordenación es "determinista" si ordena sistemáticamente los elementos en el mismo orden cada vez. Dado un conjunto de registros para ordenar el id (ASC):
1 Censu
11 Marju
4 Cikku
11 Lonzu
a continuación, un algoritmo de ordenación podría volver tanto Censu, cikk, Marju, Lonzu o Censu, Cikku, Lonzu, Marju, granulometrías como correctas. Un tipo determinista es uno que siempre devuelve el mismo orden. Este no siempre es el caso. En el caso de quicksort, uno puede obtener un rendimiento promedio más rápido si los pivotes se eligen al azar (lo ideal sería elegir la mediana, pero esto puede ser costoso). Sin embargo, esto tiene un costo: su búsqueda ya no es determinista.
¡me ganaste! –
Il-Bhima! Tengo que amar esos nombres muy malteses ... –
Creo que estás pensando en géneros "estables". – Martin
Además de lo que muchos otros ya se han dicho acerca de cómo se implementa una especie rápida determinista y una no-determinista es, creo que uno, mucho más importante aspecto de tal suerte, es que, con determinista clasificación rápida, se siempre tienen el mismo orden de registros cuando las claves chocan, mientras que con quicksorts no deterministas, el orden de dichos registros puede ser diferente cada vez que ejecuta el ordenamiento.
Supongo que no deberías usar el quicksorting no determinista cuando tienes claves no únicas.
Pero el quicksort no es estable de todos modos por defecto, y hacerlo estable y rápido no es una tarea trivial, ¿realmente importa? – IVlad
@ | \/ad: no estoy seguro de haber seguido ... Hay muchas maneras de hacerlo estable, pero eso significa, por supuesto, más poder computacional (tiempo) involucrado ... sin embargo, cuando las particiones se eligen determinísticamente, el El conjunto resultante siempre está en el mismo orden ... ¿no es así? (Estoy comenzando a dudar de mi propia respuesta) –
Los adjetivos comunes al frente de la oferta rápida son deterministas y aleatorios. Determinístico significa que el servicio rápido siempre clasificará el mismo conjunto de datos de la misma manera mientras que un servicio rápido aleatorio utiliza la aleatorización y rara vez ordenará los mismos datos de la misma manera (a menos que el conjunto de datos sea muy pequeño, entonces es más común) .
determinista
Todo se reduce a cómo se eligen los pivotes. En una oferta rápida determinista, los pivotes se eligen eligiendo siempre el pivote en el mismo índice relativo, como el primer elemento, el último o el medio, o utilizando la mediana de cualquier número de opciones predeterminadas de elementos. Por ejemplo, un método común es elegir la mediana de los elementos primero, último y medio como pivote. Incluso con el método de la mediana de 3 que acabo de describir, ciertos conjuntos de datos pueden dar fácilmente complejidad al tiempo O (N^2). Un ejemplo es el conjunto de datos los llamados tubos de órgano conjunto de datos:
array = [1,2,3,4,5,6,7,8,9,10,9,8,7,6,5,4,3,2,1]
aleatorios
quicksorts Randomizated pueden elegir sólo un pivote al azar o utilizar la mediana de algún número de pivotes elegido al azar. Todavía existe la posibilidad de O (N^2) complejidad de tiempo, pero la probabilidad es mucho, mucho más pequeña y se vuelve más pequeña con el aumento del tamaño del conjunto de datos.
¿Cuál es la diferencia entre las versiones deterministas y aleatorias de Quicksort? –
El sistema de decisión determinista elige el pivote determinísticamente (por ejemplo, siempre el primer elemento sin clasificar, o el elemento a la mitad). La colección rápida aleatorizada elige un elemento aleatorio sin clasificar como pivote. –
La elección del elemento de pivote. La colección rápida aleatorizada elige un índice aleatorio en la matriz para un pivote; determinista siempre elige un índice particular (es decir, l "eftmost"). –