Ordenamiento Quicksort

Problema: dado un vector V de n elementos, se desea ordenarlos de menor a mayor

Ejemplos:

1. Si V[ ] = {1, 7, 5, 3, 2, 4, 9}; n = 7;

Salida: {1, 2, 3, 4, 5, 7, 9};

2. Si V[ ] = {1, 3, 2, 4, 8, 11, 9, 10}; n = 8;

Salida: {1, 2, 3, 4, 8, 9, 10, 11};

Idea del algoritmo:

El algoritmo se basa en dividir los n elementos del vector a ordenar en dos particiones separadas por un elemento: una partición izquierda, un elemento central denominado pivote, y una partición derecha. La partición o división se hace de tal forma que todos los elementos del primer sub-vector(partición izquierda) son menores que todos los elementos del segundo sub-vector(partición derecha). Luego el algoritmo ordena recursivamente los 2 vectores resultantes.

Código

Disponible en Enciclopedia Algoritmos C++

Ejemplo de uso

Disponible en ejemplo ordenamiento quicksort

Complejidad: O(N*Log(N))