Definición:
El ordenamiento rápido (Quicksort en inglés) es un algoritmo basado en la técnica de divide y vencerás, no solo nos sirve para organizar una lista de datos desorganizados, si no también, para optimizar el tiempo que se ocupa en realizar esta labor, ya que permite ordenar "n" elementos en un tiempo proporcional de O(n log n), lo cual es muy eficiente.
Funcionamiento:
Primero tenemos que elegir un elemento al azar al que llamaremos pivote.
Después de elegir el pivote analizaremos y empezaremos acomodarlos de tal manera que los elementos menores al pivote van del lado izquierdo y los mayores del derecho :
•elemento < pivote ="">
•elemento > pivote = Derecha
De esta forma obtendremos la posición del pivote elegido y a partir de ahí ordenaremos los demás elementos que del pivote se dividen en 2 sublistas las cual de igual manera elegimos un pivote y lo ordenamos como la primera ves y así sucesivamente se irán dividiendo en 2 sublistas pero cada ves menores lo haremos siempre que tenga mas de un elemento y después ya nos queda ordenada.
Mejor y Peor Caso:
•En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n·log n).
•En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del arreglo, y el arreglo que le pasamos está ordenado, siempre va a generar a su izquierda un arreglo vacío, lo que es ineficiente.
Pseudocódigo:
funcion quicksort(arreglo)
variables lista, menor, mayor, elemento
if longitud(arreglo) ≤ 1
return arreglo
else
//seleccionar un valor pivote en el arreglo
for each elemento en arreglo
if elemento < pivote entonces añadir “elemento” a menor
else añadir “elemento” a mayor
return concadenar_lista(quicksort(menor), pivot, quicksort(mayor))
