Introduccion

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

Quicksort es actualmente el más eficiente y veloz de los métodos de ordenación interna.

Este método fue creado por el científico británico Charles Antony Richard Hoare, tambien conocido como Tony Hoare en 1960, su algoritmo Quicksort es el algoritmo de ordenamiento más ampliamente utilizado en el mundo.

 A continuación, encontraras todo lo relacionado a este método de ordenación.

Antecedentes

Este algoritmo nace como una necesidad para reunir datos estadísticos.

• 1945- Zuse desarrolla un programa de clasificación por inserción directa.



Jonh Mauchly

• 1946- John Mauchly mayor velocidad en procesos de clasificación. Demostró que a clasificación es útil con los cálculos numéricos.

A partir de aquí se desarrollan los algoritmos de clasificación binaria y por inserción directa.

Charles Antony Richard Hoare

• 1960 - Sir Charles Antony Richard Hoare, Tony Hoare o CAR Hoare, nacido 11 de enero 1934 es un científico informático británico, probablemente el más conocido para el desarrollo en 1960 de Quicksort (o Hoaresort),uno de los más utilizados algoritmos de ordenación del mundo.

Aplicaciones

• Es utilizado en algunas empresas para ordenar productos, agrupar datos estadísticos.
• Ingresar ciertos datos (en desorden) tenga que sacar la mediana (Estadística)

Tiempo En Ejecucion

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 depende del 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.

Algoritmo

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

Simulacion

Clic aqui para descargar.

Codigo

#include<stdio.h>
#include<conio.h>
#define MAX 12


void quicksort(int[],int,int);


void main()
{
 int i,vector[MAX]={5,7,10,4,21,8,11,9,1,6,70,14};
 clrscr();
 printf("Antes de Quicksort: ");
 for(i=0;i<MAX;i++)
  printf(" %d ",vector[i]);
 printf("\n\n");
 quicksort(vector,0,(MAX-1));
 printf("Despues de Quicksort: ");
 for(i=0;i<MAX;i++)
  printf(" %d ",vector[i]);
 getch();
}


void quicksort(int vec[], int inf, int sup)
{
 int i=inf;
 int j=sup;
 int y=0;
 int pivote=vec[(inf+sup)/2];
 do
 {
while(vec[i]<pivote)
i++;
while(vec[j]>pivote)
j--;
if(i <= j)
{
y=vec[i];
vec[i]=vec[j];
vec[j]=y;
i++;
j--;
}
 } while(i<=j);
 if(inf<j)
  quicksort(vec,inf,j);
 if(i<sup)
  quicksort(vec,i,sup);
}