¿Qué es una clasificación rápida determinista?

Question

He estado leyendo sobre Quicksort y descubrí que a veces se lo denomina "Quicksort determinista".

¿Es esta una versión alternativa del Quicksort normal?¿Cuál es la diferencia entre un Quicksort normal y un Quicksort determinista?

Answer 1

El ordinario ( "determinista") ordenación rápida puede tener un comportamiento muy pobre en conjuntos de datos particulares (por ejemplo, una aplicación que recoge el primer elemento sin clasificar tiene O (n ^ 2) complejidad del tiempo en datos ya-ordenada).

aleatorizado ordenación rápida (que selecciona al azar un pivote, en lugar de elegir de manera determinista) se utiliza a veces para dar un mejor rendimiento esperada a lo largo todos conjuntos de datos.

Answer 2

ordenación rápida se ejecuta en O(n log n) espera / tiempo promedio, pero O(n^2) peor de los casos. Esto ocurre si el pivote elegido es consistentemente ya sea el mínimo o el máximo.

Lo ideal sería que desea seleccionar la mediana como su pivote. Si encontrar la mediana directa es demasiado costoso (por lo general este es el caso si usted está tratando de utilizar la clasificación rápida), lo que ha hecho comúnmente en cambio, es tomar el promedio de tres elementos potenciales de pivote, o de lo contrario sólo debes elegir un elemento aleatorio como su pivote .

Este último método hace que quicksort no determinista debido a la aleatoriedad inherente al proceso de selección de pivote.

Answer 3

En general, un algoritmo de clasificación es "determinista" si ordena consistentemente los elementos exactamente en el mismo orden cada vez.Dado un conjunto de registros para ordenar por identificación (asc):

  1 Censu
  11 Marju
  4  Cikku
  11 Lonzu

entonces, un algoritmo de clasificación podría devolver Censu, Cikk, Marju, Lonzu o Censu, Cikku, Lonzu, Marju como clasificaciones correctas.Una clasificación determinista es aquella que siempre devuelve el mismo orden.Este no tiene por qué ser siempre el caso.En el caso de la clasificación rápida, se 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 resultar costoso).Sin embargo, esto tiene un costo:tu búsqueda ya no es determinista.

Answer 4

Su origen puede (y debe) dar su propia definición, pero en general un quicksort determinista es uno donde se elige el pivote a través de una fórmula que no depende de números aleatorios. Por ejemplo, siempre se descubre el elemento medio o siempre la primera, o algo así. Esto significa que su rendimiento será siempre el mismo (al menos en teoría, aunque en la práctica la diferencia no debe ser demasiado grande), no importa cuántas veces se ejecuta en la misma entrada. Un medio quicksort aleatorizados que está utilizando números aleatorios al elegir el pivote, es decir, el rendimiento no puede ser (fácilmente) prevé para diferentes carreras en la misma entrada.

Answer 5

Tiene que ver con la partición (o el paso de división del famoso Divide and Conquer que se utiliza en la clasificación rápida).Si cada vez que el último (o el primer elemento o elemento en cualquier posición, solo que tiene que estar en la misma posición cada vez que se divide el conjunto de datos) se utiliza como pivote para la partición, entonces se trata de una clasificación rápida determinista.Si el pivote se elige al azar, entonces se trata de una clasificación rápida aleatoria.

Aquí hay un nota de lectura que lo transmite.

Espero que ayude

salud

Answer 6

Los adjetivos comunes delante de la clasificación rápida son deterministas y aleatorios.Determinista significa que la clasificación rápida siempre ordenará el mismo conjunto de datos de la misma manera, mientras que una clasificación rápida aleatoria usa aleatorización y rara vez ordenará los mismos datos exactamente 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 clasificación rápida determinista, los pivotes se eligen eligiendo siempre el pivote en el mismo índice relativo, como el primer, último o medio elemento, o utilizando la mediana de cualquier número de opciones de elementos predeterminados.Por ejemplo, un método común es elegir la mediana del primer, último y medio elemento como pivote.Incluso con el método de mediana de 3 que acabo de describir, ciertos conjuntos de datos pueden dar fácilmente una complejidad temporal O(N^2).Un conjunto de datos de ejemplo es el llamado conjunto de datos de tubos de órgano:

array = [1,2,3,4,5,6,7,8,9,10,9,8,7,6,5,4,3,2,1]

Aleatorizado

Las clasificaciones rápidas aleatorias pueden elegir solo un pivote aleatorio o utilizar la mediana de un número determinado de pivotes elegidos al azar.Todavía existe la posibilidad de una complejidad temporal O (N ^ 2), pero la probabilidad es mucho, mucho menor y se vuelve más pequeña a medida que aumenta el tamaño del conjunto de datos.

Answer 7

Además de lo que muchos otros ya les han dicho sobre cómo se implementa una clasificación rápida determinista y una no determinista, creo que un aspecto mucho más importante de este tipo es que, con determinista Quicksort, siempre tienes el mismo orden de registros cuando las claves chocan, mientras que con no determinista Quicksorts, el orden de dichos registros puede ser diferente cada vez que ejecuta la clasificación.

Supongo que no deberías utilizar la clasificación rápida no determinista cuando tienes claves no únicas.