Presentación #2

Quick Sort

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.

Ejemplos

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))

Video