ordenamiento


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 elementos en un tiempo proporcional a n log n.
Índice [ocultar]
1 Descripción del algoritmo
1.1 Demostración de un caso particular
1.1.1 Algoritmo en C
1.1.2 Algoritmo en Java
1.2Técnicas de elección del pivote
1.3 Técnicas de reposicionamiento
1.4 Transición a otro algoritmo
2 Ejemplo
3 Véase también
4 Enlaces externos
Descripción del algoritmo[editar · editar fuente]

El algoritmo trabaja 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 maneraque a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto 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 delpivote, 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).
En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente dependedel pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos está ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente.

En el caso promedio, el orden es O(n·log n).
No es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo se centren en la elección del pivote.Demostración de un caso particular[editar · editar fuente]
Algoritmo en C[editar · editar fuente]
int colocar(int *v, int b, int t)
{
int i;
int pivote, valor_pivote;
int temp;

pivote = b;
valor_pivote = v[pivote];
for (i=b+1; i p && i < der) {
i++;
}
while (aray[j] izq) {
j--;}

if(i == izq && j == i){
QuickSort(aray, izq + 1, der);
}
if(i == der && j == i)
QuickSort(aray, izq, der - 1);

if (i < j) {
swap(aray, i, j);
}
}
return j;
}

private void Swap(int[] A, int i, int j){
int aux = A[i];A[i] = A[j];
A[j] = aux;
}
Supongamos que el número de elementos a ordenar es una potencia de dos, es decir, n = 2^k para algún natural k. Inmediatamente k = log_2(n), donde k es el número de divisiones que realizará el algoritmo.
En la primera fase del algoritmo habrá n comparaciones. En la segunda fase el algoritmo instanciará dos sublistas de tamaño aproximadamente n/2. Elnúmero total de comparaciones de estas dos sublistas es: 2(n/2) = n. En la tercera fase el algoritmo procesará 4 sublistas más, por tanto el número total de comparaciones en esta fase es 4(n/4) = n.
En conclusión, el número total de comparaciones que hace el algoritmo es:
n + n + n + .....+n = kn, donde k = log_2(n), por tanto el tiempo de ejecución del algoritmo en el mejor caso es O(n.log_2...