quick

Q
U
I
C
K
S
O
R
T

## METODO DE ORDENAMIENTO QUICKSORT

El ordenamiento rápido (quicksort en inglés) es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n. Esta es la técnica de ordenamiento más rápida conocida. Fue desarrollada por C. Antony R. Hoare en 1960. El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son en general más lentos que los iterativos, y consumen más recursos).

## CARACTERISTICAS

- El ordenamiento por partición (Quick Sort) se puede definir en una forma más conveniente como un procedimiento recursivo.
- Tiene aparentemente la propiedad de trabajar mejor para elementos de entrada desordenados completamente, que para elementos semiordenados. Esta situación es precisamente la opuesta al ordenamiento de burbuja.
- Este tipo de algoritmos se basa en la técnica "divide y vencerás", o sea es más rápido y fácil ordenar dos arreglos o listas de datos pequeños , que un arreglo o lista grande.
- Normalmente al inicio de la ordenación se escoge un elemento aproximadamente en la mitad del arreglo, así al empezar a ordenar, se debe llegar a que el arreglo este ordenado respecto al punto de división o la mitad del arreglo.
- Se podrá garantizar que los elementos a la izquierda de la mitad son los menores y los elementos a la derecha son los mayores.
- Los siguientes pasos son llamados recursivos con el propósito de efectuar la ordenación por partición al arreglo izquierdo y al arreglo derecho, que se obtienen de la primera fase. El tamaño de esos arreglos en promedio se reduce a la mitad.
- Así se continúa hasta que el tamaño de los arreglos a ordenar es 1, es decir, todos los elementos ya están ordenados.
- En promedio para todos los elementos de entrada de tamaño n, el método hace O(n log n) comparaciones, el cual es relativamente eficiente.

  ## ¿COMO FUNCIONA QUICKSORT?

  1) El secreto de Quicksort consiste en dividir la lista original en dos listas más pequeñas. Para ello, se elige un elemento cualquiera (aunque en general se suele utilizar el que se encuentra en medio de la lista) que nos servirá como pivote.
  2) Luego se recorre toda la lista, con el objeto de colocar los elementos más pequeños que el pivote a la izquierda del mismo, y los mayores a la derecha.
  3) Las implementaciones más eficientes realizan esta tarea a la vez, recorriendo simultáneamente la lista en ambas direcciones e intercambiando entre sí cada par de elementos “descolocados” que se encuentran a su paso.
  4) Culminada esta etapa tenemos un grupo de elementos menores que el pivote, el pivote, y otro grupo compuesto por números mayores a él.

  ### EJEMPLO

  Ordenar el siguiente arreglo de numeros por el metodo QUICKSORT: 4, 20, 28, 8, 10, 18, 32, 14, 12, 2.

  #### SOLUCIÓN

  NOTA: Acomodar el arreglo de izquierda a derecha.
  Despues de eso el arreglo queda acomodado de la siguiente manera: 2, 4, 8, 10, 12, 14, 18, 20, 28, 32.

  ## VIDEO COMPLEMENTARIO

  #### Algoritmos - Ordenamiento rápido - Quick Sort

  ## REFERENCIAS ELECTRONICAS

- http://mis-algoritmos.com/ordenamiento-rapido-quicksort
- http://www.estructuradedatos.galeon.com/metodoquicksort.htm