UNIVERSIDAD NACIONAL MICAELA BASTIDAS DE APURIMAC

FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE INGENIERÍA INFORMÁTICA Y SISTEMAS

TRABAJO MONOGRAFICO UNIVERSITARIO

DE LA ASIGNATURA:

ESTRUCTURA DE DATOS

TEMA:

“METODOS DE ORDENAMIENTO- QUICK SORT”

AUTORES:

-Achulli Castillo Cristian

- Carrasco Gómez Max Raúl

- Huarancca Pérez Ronaldo

-Rayme Huacho Clinio Omar

- HUAMANHORCCO PANIURA FRISH

-Bautista Mejia Kevin Santiago

-Chahuayo Achulli Jean Aderlyn

CICLO: 2020 II

DOCENTE: ING. FRANCISCO CARI INCAHUANACO

ABANCAY, 2020

pág. 1
 UNIVERSIDAD NACIONAL MICAELA BASTIDAS DE APURIMAC
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE INGENIERÍA INFORMÁTICA Y SISTEMAS

INDICE

Contenido
INTRODUCCION..................................................................................................................................3
Historia...............................................................................................................................................4
Definición...........................................................................................................................................4
Quick sort...........................................................................................................................................5
Análisis del rendimiento de Quicksort................................................................................................7
ventajas..............................................................................................................................................9
Desventajas........................................................................................................................................9
conclucion........................................................................................................................................10
Bibliografía......................................................................................................................................11

pág. 2
 UNIVERSIDAD NACIONAL MICAELA BASTIDAS DE APURIMAC
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE INGENIERÍA INFORMÁTICA Y SISTEMAS

INTRODUCCION

Una vez más, como en sesiones anteriores. En esta ocasión hablaremos un poco sobre otro método
de ordenamiento de datos. Esta vez, estamos hablando quizá del método más efectivo para el
ordenamiento de los mismos, el QuickSort.

“Quicksort 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.

Quicksort es actualmente el más eficiente y veloz de los métodos de ordenación interna. Este
método fue creado por el científico británico Charles Antony Richard Hoare, tambien conocido
como Tony Hoare en 1960, su algoritmo Quicksort es el algoritmo de ordenamiento más
ampliamente utilizado en el mundo.

Antecedentes

Este algoritmo nace como una necesidad para reunir datos estadísticos. 1945- Zuse desarrolla un
programa de clasificación por inserción directa.

1946- John Mauchly mayor velocidad en procesos de clasificación. Demostró que a clasificación es
útil con los cálculos numéricos.

A partir de aquí se desarrollan los algoritmos de clasificación binaria y por inserción directa.

1960 – Sir Charles Antony Richard Hoare, Tony Hoare o CAR Hoare, nacido 11 de enero 1934 es
un científico informático británico, probablemente el más conocido para el desarrollo en 1960 de
Quicksort (o Hoaresort), uno de los más utilizados algoritmos de ordenación del mundo.

El Algoritmo consiste en:

Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.

Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden
todos los menores que él, y al otro los mayores.

Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda,
dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar
que le corresponderá en la lista ordenada.

La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y
otra por los elementos a su derecha.

Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un
elemento.

pág. 3
 UNIVERSIDAD NACIONAL MICAELA BASTIDAS DE APURIMAC
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE INGENIERÍA INFORMÁTICA Y SISTEMAS

Historia

 El método Quicksort fue ideado por el científico inglés Charles Anthony Hoare en
1960.
 Hoare, quien se hallaba en Rusia, trabajaba en un proyecto de traducción en
computadora (del ruso al inglés).
 Él usó este método al principio para ordenarlas palabras en ruso, para poder
traducirlas.
 Luego se observó la utilidad de este método en otros campos de la informática.
 Charles Anthony Hoare, el desarrollador del Quicksort.

Definición

 Se trata de un método de ordenamiento de intercambio.

 También se le conoce como método rápido o método de ordenación por partición.
 Es considerado el más rápido de todos los métodos de ordenamiento, aun en el peor
de los casos; de ahí su nombre (inglés para Ordenamiento Rápido).
 Actualmente es uno de los más usados por su eficiencia y velocidad para la
ordenación interna.
 Se basa en la premisa Divide y Vencerás, es decir, divide el problema en
subproblemas.
 También usa la recursividad y la iteración dentro de su algoritmo.

pág. 4
 UNIVERSIDAD NACIONAL MICAELA BASTIDAS DE APURIMAC
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE INGENIERÍA INFORMÁTICA Y SISTEMAS
Quick sort

El método de ordenación rápida (Quicksort) para ordenar los elementos del array se basa
en el hecho de que es más rápido y fácil ordenar dos listas pequeñas que una lista grande.
Su nombre se debe a que este método, en general, puede ordenar una lista de datos mucho más
rápido que cualquier otro método de la bibliografía.
El método se basa en la estrategia típica de "divide y vencerás". El array a ordenar se
divide en dos partes: una contendrá todos los valores menores o iguales a un cierto valor
(que se suele denominar pivote) y la otra con los valores mayores que dicho valor. El
primer paso es dividir el array original en dos subarrays y un valor que sirve de separación,
esto es, el pivote. Así, el array se dividirá en tres partes:
• La parte izquierda, que contendrá valores inferiores o iguales al pivote.
• El pivote.
• La parte derecha, que contiene valores superiores o iguales al pivote.
Inicialmente, las partes izquierda y derecha no estarán ordenadas, excepto en el caso de
que estén compuestas por un único elemento. Consideremos, por ejemplo, la lista de
valores:
28 21 37 23 19 14 26
elegimos como pivote del 23. Recorremos el array desde la izquierda y buscamos un
elemento mayor que 23 (encontramos el 28). A continuación, recorremos el array en sentido
descendente empezando por el extremo derecho y buscamos un valor menor que
23 (encontramos el 14). Se intercambian esto los valores y se produce la lista:
14 21 37 23 19 28 26
se sigue recorriendo el array por la izquierda y se encuentra otro número que es mayor que
23: el 37; continuamos al recorrido por la izquierda y encontramos otro valor menor que
23: 19. Volvemos a cambiar sus posiciones:
14 21 19 23 37 28 26
en este punto todos los valores que están a la izquierda del pivote son menores que él, y
todos los que están a su derecha son mayores. Ninguno de los dos subconjuntos de valores
está ordenado. En este momento procesamos cada uno de los dos subconjuntos de valores

pág. 5
 UNIVERSIDAD NACIONAL MICAELA BASTIDAS DE APURIMAC
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE INGENIERÍA INFORMÁTICA Y SISTEMAS
del mismo modo que el inicial: elegimos un valor de pivote y lo ordenamos de tal modo
que todo los que sean mayores que el pivote esté a la derecha y todos los que sean
menores a la izquierda. Así, si cogemos el primer conjunto de datos:
14 21 19
y tomamos como pivote el 14 obtenemos:
14 19 21
del mismo modo, procesamos el otro conjunto de datos. Cuando el tamaño de los
conjuntos de datos que se sitúan a la izquierda y a la derecha del valor tomado como pivote
es 0 o 1 habremos terminado el procedimiento de ordenación. La corrección de este
algoritmo se base en los siguientes hechos:
• El subconjunto de elementos menores que el pivote se ordenará correctamente, en
virtud del proceso recursivo.
• El mayor elemento en el subconjunto de
elementos menores no es mayor que el
pivote, debido a cómo se realiza la
partición.
• El menor elemento en el subconjunto de elementos mayores no es menor que el pivote, debido a
cómo se realiza la partición.
• El subconjunto de elementos mayores se ordena correctamente, en virtud del
proceso recursivo.

pág. 6
 UNIVERSIDAD NACIONAL MICAELA BASTIDAS DE APURIMAC
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE INGENIERÍA INFORMÁTICA Y SISTEMAS
Análisis del rendimiento de Quicksort
El mejor caso para Quicksort se presenta cuando el pivote divide al conjunto en dos
subconjuntos de igual tamaño. En este caso tendremos dos llamadas recursivas con un
tamaño igual a la mitad del original y el tiempo de ejecución es O (TAM*log (TAM2)).
Ya que los subconjuntos de igual tamaño son los mejores para Quicksort, es de esperar que
los de muy distinto tamaño sean los peores y, efectivamente, así es. Suponiendo, por
ejemplo, que el elemento que se toma como pivote es el menor del conjunto el subconjunto
de la izquierda (elementos menores) estará vacío, y el de la derecha (elementos mayores)
contendrá a todos los elementos menos al pivote. Poniéndonos en el peor de los casos,
aquél en el que siempre obtenemos uno de los dos subconjuntos vacíos y el otro contiene
n-1 elementos, la complejidad del algoritmo sería O (TAM2).
En el caso medio, si el algoritmo es implementado cuidadosamente y los subconjuntos de
elementos generados en cada partición contienen aproximadamente el mismo número de
elementos, puede demostrarse que el tiempo de ejecución es O (TAM*log (TAM2)).
Para conseguir esta implementación cuidadosa es crucial determinar adecuadamente el
elemento pivote.
Una elección muy popular para el elemento pivote, que puede degradar notablemente el
rendimiento del algoritmo, es emplear el primer elemento de la izquierda. Este pivote es
aceptable si la entrada es completamente aleatoria, pero si la entrada ya está ordenada, o
está ordenada en orden inverso, este pivote proporciona la peor división posible. Una
elección más razonable es elegir como elemento pivote el elemento central de del array.
Metodología de la programación (I) 26/27
Lo ideal, sería elegir el valor mediano del array; esto es, aquel valor que ordenando en
orden decreciente o creciente la lista de elementos quedaría justo en el medio (por tanto,
este es el pivote ideal). Sin embargo, el cálculo de la mediana de una lista de elementos es
excesivamente costosa para incorporarse al algoritmo; esto lleva calcular aproximaciones
tomando un subconjunto de los elementos del array. En muchas ocasiones se emplea la
"partición con la mediana de tres", en esta partición se emplea como pivote la mediana de
los elementos primero, último y punto medio del array.
Otro factor que afecta de modo crítico la eficiencia del algoritmo es qué hacer con aquellos

pág. 7
 UNIVERSIDAD NACIONAL MICAELA BASTIDAS DE APURIMAC
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE INGENIERÍA INFORMÁTICA Y SISTEMAS
datos que son iguales al pivote. Si, por ejemplo, sistemáticamente colocamos los datos que
son mayores que el pivote en el subconjunto de la derecha esto puede llevarnos a realizar
particiones desproporcionadas cuando un dato se repite un número excesivo de veces. El
caso extremo será cuando todos los elementos de la lista a particionar sean iguales al
pivote. En este hipotético caso la partición sería la peor de las posibles: una lista estaría
vacía y la otra contendría todos los elementos.
A simple vista, podría parecer absurdo que un programa informático tuviera que ordenar
una lista de valores iguales. Sin embargo, no lo es tanto: supongamos que tenemos que
ordenar una lista con un millón de datos enteros comprendidos entre el 0 y 999. Si
realizamos la ordenación mediante Quicksort y suponemos una distribución uniforme de
los datos llegarán un momento en el que, tras varias llamadas recursivas, nuestro problema
consista en ordenar 1000 listas de, aproximadamente, unos 1000 valores cada una de ellas.
Estos valores serán en su mayor parte iguales: habrá una lista con todo 0s, una con todo
1s,..., y una con todo 999s. Llegado este momento, es obvia la importancia de que nuestra
implementación de Quicksort gestione adecuadamente conjuntos de datos iguales.
La mejor estrategia en este caso es intercambiar los elementos iguales que estén a ambos
lados del pivote: si al buscar un elemento menor que el pivote en el subconjunto de la
izquierda encontramos un elemento igual al pivote lo intercambiaremos por un elemento
mayor o igual que el pivote del subconjunto de la derecha. A pesar del aparente derroche
de operaciones que, en caso de que ambos elementos intercambiados sean iguales, no hace
nada en la práctica, es mejor gestionar esta situación de este modo y no añadir código
adicional que cheque la ocurrencia de esta situación y que, inevitablemente, penalizaría la
eficiencia del algoritmo.

pág. 8
 UNIVERSIDAD NACIONAL MICAELA BASTIDAS DE APURIMAC
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE INGENIERÍA INFORMÁTICA Y SISTEMAS

ventajas
 Muy rápido.

 No requiere memoria adicional.

 Quicksort, es uno de los algoritmos de ordenamiento más rápido que se conoce. Sin
embargo, la diferencia entre el mejor de los casos y el peor de los casos es muy notable.

 Quicksort suele considerarse muy elegante, siendo incluso el motivo del libro del autor y
programador Greg Wilson, titulado “Beautiful Code”.

Desventajas
 Implementación un poco más complicada.

 Recursividad (utiliza muchos recursos).

 Mucha diferencia entre el peor y el mejor caso.

 El peor caso ocurre cuando el arreglo ya está ordenada, porque cada llamada genera sólo un
subarreglo (todos los elementos son menores que el elemento de división). En este caso el
rendimiento se degrada a O(n2).

 Una de sus desventajas, es que es un poco más difícil de implementar que los algoritmos
promedio. A pesar de esto, debido a su alta eficiencia, Quicksort sigue siendo el algoritmo
de ordenamiento más popular.

pág. 9
 UNIVERSIDAD NACIONAL MICAELA BASTIDAS DE APURIMAC
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE INGENIERÍA INFORMÁTICA Y SISTEMAS
conclucion
El algoritmo de ordenamiento rápido permite ordenar una lista en menor tiempo promedio
en comparación a otros algoritmos como bubblesort, sin embargo, en el peor caso la
ganancia es el mismo.

Así mismo, es necesario considerar la ubicación del pivote en cada iteración, ya que éste
determina los elementos menores a la izquierda, y los valores mayores a la derecha, con el
objetivo de reducir la complejidad del algoritmo al usar la técnica de divide y vencerás.

pág. 10
 UNIVERSIDAD NACIONAL MICAELA BASTIDAS DE APURIMAC
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE INGENIERÍA INFORMÁTICA Y SISTEMAS

Bibliografía
•Aho, Alfred V. "Estructuras de Datos y Algoritmos". Addison Wesley
Iberoamericana. 1988.
•Cairó/Guardati. "Estructuras de Datos". McGraw-Hill. México. 1993
•Joyanes Aguilar, Luis."Fundamentos de Programación. Algoritmos y
Estructura de Datos". McGraw Hill.
•Lipschutz, Seymour. "Estructura de Datos". Serie Schaum en Computación.
McGraw-Hill.
•Loomis, Mary E.S. "Estructura de Datos y Organización de Archivos". Prentice
Hall. México. 1991.

pág. 11