MÉTODO DE ORDENAMIENTO QUICKSORT PDF

Preview

Summary

Eduardo Andrés Medina Ramírez Angel Robles Pérez MÉTODO DE ORDENAMIENTO QUICKSORT ¿QUÉ ES QUICKSORT? HISTORIA DEL MÉTODO QUICKSORT  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 co...

Description

Eduardo Andrés Medina Ramírez Angel Robles Pérez

MÉTODO DE ORDENAMIENTO QUICKSORT

¿QUÉ ES QUICKSORT?

HISTORIA DEL MÉTODO QUICKSORT 

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 ordenar las palabras en ruso, para poder traducirlas.  Luego se observó la utilidad de este método en otros campos de la informática.

HISTORIA DEL MÉTODO QUICKSORT 

Charles Anthony Hoare, el desarrollador del Quicksort.

DEFINICIÓN DEL MÉTODO QUICKSORT 

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

DEFINICIÓN DEL MÉTODO QUICKSORT 

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 sub-problemas.  También usa la recursividad y la iteración dentro de su algoritmo.

ALGORITMO DEL QUICKSORT

ALGORITMO DEL QUICKSORT 

El algoritmo del método Quicksort se realiza en arreglos de elementos iguales (números, letras, palabras, etc.). 1) Se inicia tomando un elemento X al que se le llamará pivote. Este elemento puede ser cualquiera dentro del arreglo. Generalmente se toma el primer elemento, aunque también se suele tomar el último o un valor cercano a la media.

ALGORITMO DEL QUICKSORT 2) Se

trata de ubicar la posición correcta dentro del arreglo. Se comienza una revisión de los elementos del arreglo, comenzando por el final. a. Si se halla un valor igual o mayor al pivote, se continúa con el siguiente. b. Si se halla un valor menor al pivote, se intercambian.

ALGORITMO DEL QUICKSORT 2) Se

trata de ubicar la posición correcta dentro del arreglo. Se comienza una revisión de los elementos del arreglo, pero comenzando ahora por el principio. a. Si se halla un valor igual o menor al pivote, se continúa con el siguiente. b. Si se halla un valor mayor al pivote, se intercambian.

ALGORITMO DEL QUICKSORT 2) Se

trata de ubicar la posición correcta dentro del arreglo. Se deben efectuar los recorridos de comparación e intercambio, alternándose a cada intercambio e iniciando con el elemento en el que se quedó al momento del intercambio. Se termina este proceso hasta que el recorrido no realiza ningún intercambio.

ALGORITMO DEL QUICKSORT 2) Se

trata de ubicar la posición correcta dentro del arreglo. Esto significa que el pivote llegó a su posición final, partiendo el arreglo en dos conjuntos.  El primer conjunto contiene elementos cuyo valor es menor o igual al valor del pivote.  El segundo conjunto contiene elementos cuyo valor es mayor o igual al valor del pivote.

ALGORITMO DEL QUICKSORT 3) Se

repiten los pasos anteriores, pero ahora para los conjuntos de datos que se encuentran a la izquierda y a la derecha de la posición correcta del pivote en el arreglo (usando ya sea recursividad o iteración). 4) El proceso termina cuando todos los elementos se encuentran en su posición correcta en el arreglo.

EJEMPLO DEL QUICKSORT

EJEMPLO DEL QUICKSORT 

El siguiente es un arreglo de números enteros.  Son 5 elementos en el arreglo. C: 0 I: 0

15

67

8

27

35

EJEMPLO DEL QUICKSORT 

El pivote es el círculo rojo. El elemento a checar el azul. C: 1  35 > 15. Sí. I: 0  No hay intercambio.

15

67

8

27

35

EJEMPLO DEL QUICKSORT 

El pivote es el círculo rojo. El elemento a checar el azul. C: 2  27 > 15. Sí. I: 0  No hay intercambio.

15

67

8

27

35

EJEMPLO DEL QUICKSORT 

El pivote es el círculo rojo. El elemento a checar el azul. C: 3  8 > 15. No. I: 1  Debe haber intercambio.

15

67

8

27

35

EJEMPLO DEL QUICKSORT 

El pivote es el círculo rojo. El elemento a checar el azul. C: 4  67 < 15. No. I: 2  Debe haber intercambio.

8

67

15

27

35

EJEMPLO DEL QUICKSORT 

El pivote ya llegó a su destino (cuadrado rojo).  Se debe hacer el método a la C: 4 derecha e izquierda del pivote. I: 2  Primero, a la izquierda.

8

15

67

27

35

EJEMPLO DEL QUICKSORT 

Como es un sub-arreglo de un elemento, el elemento ya llegó a su destino. C: 4 I: 2

8

15

67

27

35

EJEMPLO DEL QUICKSORT 

El pivote es el círculo rojo. El elemento a checar el azul. C: 5  35 > 67. No. I: 3  Debe haber intercambio.

8

15

67

27

35

EJEMPLO DEL QUICKSORT 

El pivote es el círculo rojo. El elemento a checar el azul. C: 6  27 < 67. Sí. I: 3  No hay intercambio.

8

15

35

27

67

EJEMPLO DEL QUICKSORT 

El pivote ya llegó a su destino (cuadrado rojo).  Se debe hacer el método sólo a la C: 6 izquierda del pivote, ya que no hay I: 3 nada a la derecha.

8

15

35

27

67

EJEMPLO DEL QUICKSORT 

El pivote es el círculo rojo. El elemento a checar el azul. C: 7  27 > 35. No. I: 4  Debe haber intercambio.

8

15

35

27

67

EJEMPLO DEL QUICKSORT 

El pivote ya llegó a su destino (cuadrado rojo).  Se debe hacer el método sólo a la C: 7 izquierda del pivote, ya que no hay I: 4 nada a la derecha.

8

15

27

35

67

EJEMPLO DEL QUICKSORT 

Como es un sub-arreglo de un elemento, el elemento ya llegó a su destino. C: 7 I: 4

8

15

27

35

67

EJEMPLO DEL QUICKSORT 

No hay elementos que ordenar.  El arreglo está completamente ordenado.  Se hicieron 7 comparaciones.  Se hicieron 4 intercambios.

8

15

27

35

67

PARA MÁS INFORMACIÓN…

PARA MÁS INFORMACIÓN… 

AHO, Alfred V., et. al., Estructuras de Datos y Algoritmos, México: Addison-Wesley Iberoamericana, 1988, 438 págs., ISBN 968444-345-5  CAIRÓ, Osvaldo y GUARDATI, Silvia, Estructuras de Datos, México: McGraw-Hill Interamericana, 2006, 488 págs., ISBN 970-105-908-5

PARA MÁS INFORMACIÓN… 

GALVE, Javier, et. al., Algorítmica. Diseño y Análisis de Algoritmos Funcionales e Imperativos, España: Addison-Wesley Iberoamericana, 1993, 502 págs., ISBN 847897-116-5  KRUSE, Robert L., Estructuras de Datos y Diseño de Programas, México: Prentice-Hall Hispanoamericana, 1988, 488 págs., ISBN 968-880-085-6

¡GRACIAS POR SU ATENCIÓN!...