Algoritmo De Ordenamiento Interno Del Método De Quicksort

Algoritmo de ordenamiento interno del método de quicksort
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, erael 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 cualde 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 “dividey 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 resueltosCaracteristicas:
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.
Elhecho 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 elmétodo utilizado es el de partición.
Explicación abstracta
1. Se elige un elemento v de la lista L de elementos al que se le llama pivote.
2. 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 igualesque v
3. Se aplica la recursión sobre L1 y L3
4. 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...