Ahorcado

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 delarreglo. 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 igualesa 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 seencuentra 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

Quicksort en acción sobre una lista de números aleatorios. Las líneas horizontales son valores pivote.
El ordenamiento rápido (quicksort en inglés) es un algoritmo creado por el científico británico en computación C. A. R. Hoare basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementosen un tiempo proporcional a n log n.
Descripción del algoritmo
El algoritmo funciona de la siguiente forma:
* 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 colocadostanto 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. Una vez terminado este proceso todos los elementos estarán ordenados.
Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.
* En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n·log n)....