Holas, hoy voy a hablar sobre el método de Ordenación rápida “QUICKSORT”.
Bueno hoy en la Universidad para una materia, teníamos que que dar una explicación sobre este método, así que voy a poner la información básica, código, ejemplos, etc.. Sobre el mismo, tal vez a alguien le sirve.
Bueno comencemos con un poco de teoría:
El ordenamiento rápido (quicksort en inglés) 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. Esta es la técnica de ordenamiento más rápida conocida. Fue desarrollada por C. Antony R. Hoare en 1960. 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).
El algoritmo fundamental es el siguiente:
• 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. 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).
• En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de 0(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas.
• 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.
Ahora manos a la obra, el Pseudocódigo:
función quicksort
i=l
j=r
x=a[(l+r) div 2]
mientras i =< j hacer
mientras a[i]<x hacer
i=i+1
fin_mientras
mientras a[j]>x hacer
j=j-1
fin_mientras
si i =< j entonces
aux= a[i]
a[i]= a[j]
a[j]= aux
fin_si
fin_mientras
fin_funcion
Ahora el código en basic: (tiene definido un vector de pruebas)
dim a(7)
a(1)=18
a(2)=11
a(3)=27
a(4)=88
a(5)=9
a(6)=4
a(7)=16
call quickSort 1,7
for i=1 to 7
print a(i);" "
next i
sub quickSort izq,der
i=izq
j=der
pivote=a(int((izq+der)/2))
do
while a(i)<pivote
i=i+1
wend
while a(j)>pivote
j=j-1
wend
if (i<=j) then
aux=a(i)
a(i)=a(j)
a(j)=aux
i=i+1
j=j-1
end if
loop while i<=j
if izq<j then call quickSort izq,j
if i<der then call quickSort i,der
end sub
Por ultimo el código en C: (no podía faltar):
#include <conio.h>
#include <stdio.h>
#include <stdlib.h> //libreria con el prototipo de la funcion rand()
int quicksort_iterativo(int A[],int ini,int fin){
int _ini_,_fin_,pos,aux,band;
_ini_=ini;
_fin_=fin;
pos=ini;
band=1;
while (band==1){
band=0;
while((A[pos]<=A[_fin_])&&(pos!=_fin_)){
_fin_--;
}
if (pos!=_fin_){
aux=A[pos];A[pos]=A[_fin_];
A[_fin_]=aux;
pos=_fin_;
while ((A[pos]>=A[_ini_])&&(pos!=_ini_)){
_ini_++;
}
if(pos!=_ini_){
band=1;
aux=A[pos];
A[pos]=A[_ini_];
A[_ini_]=aux;
pos=_ini_;
}
}
}
if ((pos-1)>ini){
quicksort_iterativo(A,ini,pos-1);
}
if (fin>(pos+1)){
quicksort_iterativo(A,pos+1,fin);
}
return 0;
}
void main(){
int A[10],c;
clrscr();
randomize();
for(c=1;c<=10;c++){
A[c]=rand()%10;
printf("%d, ",A[c]);
}
printf("\nValores ordenados: \n");
quicksort_iterativo(A,1,10);
for(c=1;c<=10;c++){
printf("%d, ",A[c]);
}
getch();
}
Bueno para terminar, no sacamos un 10 
y les dejo aquí los links para que se descarguen si quieren, una presentación con un ejemplo y el código en basic.
Codigo Basic
PPS
Espero que les sea útil
Saludos dag
Parte de la informacion extraida de: Libro Fundamentos de programación – Luis Joyanes Aguilar, Mis Algoritmos
