Scribd
Cargar
95 vistas9 páginas

Guía de Quick Sort para Programadores

El algoritmo Quick Sort ordena un vector de forma eficiente en la mayoría de los casos. Se elige un elemento del vector como pivote y se reorganizan los elementos menores y mayores que el pivote a sus lados, colocando al pivote en su posición correcta. Luego se aplica el mismo proceso de manera recursiva a las sublistas izquierda y derecha. Tiene una complejidad de O(n log n) en promedio.

Cargado por

Gudi Escobar
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPTX, PDF, TXT o lee en línea desde Scribd
95 vistas9 páginas

Guía de Quick Sort para Programadores

El algoritmo Quick Sort ordena un vector de forma eficiente en la mayoría de los casos. Se elige un elemento del vector como pivote y se reorganizan los elementos menores y mayores que el pivote a sus lados, colocando al pivote en su posición correcta. Luego se aplica el mismo proceso de manera recursiva a las sublistas izquierda y derecha. Tiene una complejidad de O(n log n) en promedio.

Cargado por

Gudi Escobar
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPTX, PDF, TXT o lee en línea desde Scribd

Quick Sort

DANIEL ESCOBAR
Quick Sort

 Es un algoritmo de ordenamiento creado por el


científico británico Charles Hoare

 Este algoritmo consiste en elegir un dato de un


vector y ubicarlo en el sitio que le corresponde en
base a un criterio de ordenamiento.

 Luego de ordenar este dato, ordenaremos los datos


que quedaron antes y después de este.

 Este algoritmo tiene una eficiencia de O(𝑛 log 𝑛) en la


mayoría de los casos, en su peor caso tiene una
eficiencia de O(02 ) aunque estos son casos muy
esporádicos.
Algoritmo
Quick Sort
 El algoritmo puede variar
dependiendo de como
quiera elegir el pivote, es
decir el numero que
queremos ordenar, en este
caso mostraremos el
algoritmo ordenando el dato
en la primera posición.
Algoritmo
Quick Sort
 Es un algoritmo tipo Void
puesto que no queremos
retornar algo, solo queremos
ordenar el vector en
cuestión.
 Los parámetros m y n
significan:

m: posición inicial
n: posición final
Algoritmo
Quick Sort
 En las instrucciones desde 6
hasta 17 se coloca el dato
elegido en la posición
correcta, y como señalamos
anteriormente, en este caso
será el primer elemento del
vector.
 Ordenaremos el siguiente vector:

Luego de la seguir las instrucciones hasta la 12


llegaremos a lo siguiente:

Ejemplo
Como el valor de i es menor que el de j ejecutamos la
instrucción 14 y quedaremos con lo siguiente:
 Regresamos a evaluar el ciclo y al ser la i
menor que la j continuamos y luego de
ejecutar quedaremos con lo siguiente:

Ejemplo  Nuevamente la i es menor que la j por lo tanto


hacemos el intercambio y quedaremos con lo
siguiente:
 Una vez mas entramos en el ciclo debido a
que se cumple la condición y quedaremos
con lo siguiente:

Ejemplo
 Una ves llegamos a la instrucción 13 la condición no se
cumple, al igual que la condición de la instrucción 6 por
tanto salimos del ciclo y ejecutamos el intercambio de
la instrucción 17.
Referencias:

 Flórez Rueda Roberto. Algoritmia II. (2010) Recuperado el 07 de Abril


de 2019.

 GeeksForGeeks. QuickSort. Recuperado el 07 de Abril de 2019 de:


https://www.geeksforgeeks.org/quick-sort/

También podría gustarte