En el Quick Sort, ¿cómo se puede verificar que ya se hizo correctamente el primer reacomodo de la lista antes de cualquier llamada recursiva?
Respuestas
Respuesta:
hola, Desde que existe la ciencia de la computación, uno de los mayores problemas con los que los ingenieros se encontraban en su día a día, era el de ordenar listas de elementos. Por su causa, diversos algoritmos de ordenación fueron desarrollados a lo largo de los años y siempre existió un intenso debate entre los desarrolladores sobre cual de todos los algoritmos de ordenación era el más rápido.
El debate finalizó abruptamente en 1960 cuando Sir Charles Antony Richard Hoare, nativo de Sri Lanka y ganador del premio Turing en 1980, desarrolló el algoritmo de ordenación QuickSort casi por casualidad mientras ideaba la forma de facilitar la búsqueda de palabras en el diccionario.
El algoritmo QuickSort se basa en la técnica de "divide y vencerás" por la que en cada recursión, el problema se divide en subproblemas de menor tamaño y se resuelven por separado (aplicando la misma técnica) para ser unidos de nuevo una vez resueltos.
Características del Algoritmo QuickSort
En la práctica, es el algoritmo de ordenación más rápido conocido, su tiempo de ejecución promedio es O(n log (n)), siendo en el peor de los casos O(n2), caso altamente improbable. El hecho de que sea más rápido que otros algoritmos de ordenación con tiempo promedio de O(n log (n)) ( como SmoothSort o HeapSort ) viene dado por que QuickSort realiza menos operaciones ya que el método utilizado es el de partición.
Explicación abstracta del funcionamiento de QuickSort
Se elige un elemento v de la lista L de elementos al que se le llama pivote.
Se particiona la lista L en tres listas:
L1 - que contiene todos los elementos de L menos v que sean menores o iguales que v
L2 - que contiene a v
L3 - que contiene todos los elementos de L menos v que sean mayores o iguales que v
Se aplica la recursión sobre L1 y L3
Se unen todas las soluciones que darán forma final a la lista L finalmente ordenada. Como L1 y L3 están ya ordenados, lo único que tenemos que hacer es concatenar L1, L2 y L3
Aunque este algoritmo parece sencillo, hay que implementar los pasos 1 y 3 de forma que se favorezca la velocidad de ejecución del algoritmo.