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, en el mundo de habla hispana.
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 C.A. Hoare lo bautizó así.
La idea central de este algoritmo consiste en los siguiente:
Se toma un elemento x de una posición cualquiera del arreglo.
Se trata de ubicar a x 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 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 posición 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 debería iniciarse en la misma posición
donde se encuentra el elemento x, el proceso se termina ya que el elemento x, se
encuentra en la posición 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
xß44
(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
xß35
(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
xß12
(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 posición central del conjunto de
datos a analizar, el número de pasadas necesarias para ordenar es del orden de Log n.
Respecto al número de comparaciones, si el tamaño 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)
Ejecutar el método Quicksort
