Quicksort

Quicksort el ordenamiento rápido

El método de ordenamiento Quick Sort es actualmente el más eficiente y veloz de los métodos de ordenación interna.


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

El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son en general más lentos que los iterativos, y consumen más recursos). Fue desarrollada por C. Antony R. Hoare en 1960.

Descripción del algoritmo

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

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.

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. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.

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

Analisis del algoritmo:

Estabilidad: No es estable.
Requerimientos de Memoria: No requiere memoria adicional en su forma recursiva. En su forma iterativa la necesita para la pila.

Ventajas:

Muy rápido.
No requiere memoria adicional.

Desventajas:

Implementación un poco más complicada.
Recursividad (utiliza muchos recursos).
Mucha diferencia entre el peor y el mejor caso.

Ejemplo:

}El elemento divisor será el 6:
}5 - 3 - 7 - 6 - 2 - 1 - 4
} p
}Comparamos con el 5 por la izquierda y el 4 por la derecha con el pivote.
}5 - 3 - 7 - 6 - 2 - 1 - 4
}i p j
}5 es menor que 6 y 4 NO es mayor que 6. Avanzamos la i, y la j queda donde está.
}
}5 - 3 - 7 - 6 - 2 - 1 - 4
} i p j
}3 es menor que 6 y 4 NO es mayor que 6. Avanzamos la i, y la j queda donde está.
}
}5 - 3 - 7 - 6 - 2 - 1 - 4
} i p j
}7 NO es menor que 6 y 4 NO es mayor que 6.
}
}5 - 3 - 7 - 6 - 2 - 1 - 4
} i p j