Quick Sort
2
QUICKSORT El método de ordenamiento Quick Sort es actualmente el más eficiente y veloz de los métodos de ordenación interna. Es también conocido con el nombre del método rápido y de ordenamiento por partición. Este método es una mejora sustancial del método de intercambio directo y recibe el nombre de Quick Sort por la velocidad con que ordena los elementos del arreglo. Su autor .!. "oare lo bautizó as#. $a idea central de este algoritmo consiste en lo siguiente% Se toma un elemento & de una posición cualquiera del arreglo. Se trata de ubicar a & en la posición correcta del arreglo' de tal forma que todos los elementos que se encuentran a su izquierda sean menores o iguales a & y todos los elementos que se encuentren a su derec(a sean mayores o iguales a &. Se repiten los pasos anteriores pero a(ora para los conjuntos de datos que se encuentran a la izquierda y a la derec(a de la posición correcta de & en el arreglo. Ejemplo: A: 15,67,08,16,44,27,12,35 Se selecciona A[i] x=15 Pimea pasa!a "#E$%&'() A[8] *= x 35 *= 15 +o a- in.ecam/io A[7] *= x 12 *= 15 Si a- in.ecam/io A: 12,67,08,16,44,27,15,35 "&'(%#E$) A[2] = 67 = 15 Si a- in.ecam/io A:12,15,08,16,44,27,67,35 2!a Pasa!a "#E$%&'() A[6] *= x 27 *= 15 +o a- in.ecam/io A[5] *= x 44 *= 15 +o a- in.ecam/io A[4] *= x 16 *= 15 +o a- in.ecam/io A[3] *= x 08 *= 15 Si a- in.ecam/io A: 12,08,15,16,44,27,67,35 omo el ecoi!o !e iie!a a !eeca !e/ea iniciase en la misma posicin !on!e se encen .a el elemen .o x, el po ceso se .e mina -a e el elemen.o x, se encen.a en la posicin coec.a A: 12, 08, 15, 16, 44, 27, 67, 35 1e 2!o onjn.o onjn.o 16, 44, 27, 67, 35 x16
-
Upload
jorge-chavez-molina -
Category
Documents
-
view
212 -
download
0
description
ejemplo
Transcript of Quick Sort
QUICKSORT
El mtodo de ordenamiento Quick Sort es actualmente el ms eficiente y veloz de los mtodos de ordenacin interna. Es tambin conocido con el nombre del mtodo rpido y de ordenamiento por particin.Este mtodo es una mejora sustancial del mtodo de intercambio directo y recibe el nombre de Quick Sort por la velocidad con que ordena los elementos del arreglo. Su autor C.A. Hoare lo bautiz as.La idea central de este algoritmo consiste en lo siguiente:Se toma un elemento x de una posicin cualquiera del arreglo.
Se trata de ubicar a x en la posicin correcta del arreglo, de tal forma que todos los elementos que se encuentran a su izquierda sean menores o iguales a x y todos los elementos que se encuentren a su derecha sean mayores o iguales a x.
Se repiten los pasos anteriores pero ahora para los conjuntos de datos que se encuentran a la izquierda y a la derecha de la posicin correcta de x en el arreglo.Ejemplo:A: 15,67,08,16,44,27,12,35
Se selecciona A[i] x=15
Primera pasada (DER-IZQ)
A[8] >= x 35 >= 15 No hay intercambio
A[7] >= x 12 >= 15 Si hay intercambio
A: 12,67,08,16,44,27,15,35
(IZQ-DER)
A[2] < = X 67 < = 15 Si hay intercambio
A:12,15,08,16,44,27,67,35
2da. Pasada (DER-IZQ)
A[6] >= x 27 >= 15 No hay intercambio
A[5] >= x 44 >= 15 No hay intercambio
A[4] >= x 16 >= 15 No hay intercambio
A[3] >= x 08 >= 15 Si hay intercambio
A: 12,08,15,16,44,27,67,35
Como el recorrido de izquierda a derecha debera iniciarse en la misma posicin
donde se encuentra el elemento x, el proceso se termina ya que el elemento x, se
encuentra en la posicin correcta.
A: 12, 08, 15, 16, 44, 27, 67, 35
1er 2do Conjunto
Conjunto
16, 44, 27, 67, 35
x16
(DER-IZQ)
A[8]>=x No hay intercambio
A[7]>=x No hay intercambio
A[6]>=x No hay intercambio
A[5]>=x No hay intercambio
A: 12, 08, 15, 16, 44, 27, 67, 35
x44
(DER-IZQ)
A[8]>= x Si hay intercambio
A: 12, 08, 15, 16, 35, 27, 67, 44
(IZQ-DER)
A[6] < = x No hay intercambio
A[7] < = x Si hay intercambio
12, 08, 15, 16, 35, 27, 44, 67
12, 08, 15, 16, 35, 27, 44, 67
35, 27, 44, 67
x35
(DER-IZQ)
A[8] >= x No hay intercambio
A[7] >= x No hay intercambio
A[6] >= x Si hay intercambio
12, 08, 15, 16, 27, 35, 44, 67
12,08
x12
(DER-IZQ)
A[2]>=x Si hay intercambio
EL VECTOR ORDENADO:
08,12,15,16,27,35,44,67
ANALISIS DE EFICIENCIA DEL METODO DE QUICKSORT Diversos estudios realizados sobre el comportamiento del mismo demuestran que si se escoge en cada pasada el elemento que ocupa la posicin central del conjunto de datos a analizar, el nmero de pasadas necesarias para ordenar es del orden de Log n. Respecto al nmero de comparaciones, si el tamao del arreglo es una potencia de 2, en la primera pasada realizar (n-1) comparaciones, en la 2 pasada realizar (n-1)/2 comparaciones, pero en 2 conjuntos diferentes, en la tercera pasada realizar (n-1)/4 comparaciones pero en 4 conjuntos diferentes y as sucesivamente.
Por lo tanto: C = (n-1) + 2(n -1)/2 + 4(n - 1)/4 + ....... + (n - 1)(n - 1)/(n - 1)
Lo cual es lo mismo que: C= (n - 1) + (n- 1) + ....... + (n - 1)
