La ordenación rápida implica la selección de un elemento de una lista y a continuación reordenar todos los elementos restantes de la sublista. De tal modo que todos los elementos que son más pequeños que el elemento dado se ponen en una sublista y todos los elementos que son más grandes que el elemento dado se ponen en una segunda sublista. Por consiguiente. El método elige un elemento denominado pivote pone en una sub lista todos los elementos mayores que el pivote y los elementos más pequeños en otra sublista.
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 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.
Imagen:
Codigo:
Quicksort.cpp:
#include<iostream>
#include"Quicksort.h"
using namespace std;
void main(){
int i;
Quicksort q;
int c;
cout<<"cuantos datos: ";
cin>>c;
for(i=0;i<c;i++){
system("cls");
cout<<"dato["<<i+1<<"]: ";
cin>>q.lista[i];
} system("cls");
cout<<endl;
q.quicksort(q.lista,0,c-1);
/**/cout<<endl;
cout<<endl<<"Arreglo ordenado"<<endl<<endl;
for(i=0;i<c;i++){
cout<< q.lista[i]<<" ";
}cout<<endl<<endl;
system("pause>null");
}
Quicksort.h:
#include<iostream>
#include<windows.h>
using namespace std;
#define MAX 100
class Quicksort{
public:
int i,j,pivote,centro,primero,ultimo,temp;
int lista[MAX];
void quicksort(int[] ,int ,int );
};
void Quicksort::quicksort(int lista[],int primero,int ultimo){
centro=(primero+ultimo)/2;
pivote=lista[centro];
i=primero;
j=ultimo;
cout<<endl<<endl<<"****************************************************"<<endl<<endl<<"ARREGLO: "<<endl<<endl;
for(int k=primero; k<=ultimo; k++){
cout<<lista[k]<<"\t";
}
cout<<endl<<endl<<"pivote: "<<pivote<<endl<<"primero: "<<primero<<endl<<"ultimo: "<<ultimo<<endl;
Sleep(1500);cout<<endl;
do{
while(lista[i]<pivote){i++;}
while(lista[j]>pivote){j--;}
if(i<=j){
cout<<endl<<"Cambio de "<<lista[i]<<" por "<<lista[j]<<endl;
temp=lista[i];
lista[i]=lista[j];
lista[j]=temp;
i++;
j--;
}
}while(i<=j);
if(primero<j){
quicksort(lista,primero,j);
}
if(i<ultimo){
quicksort(lista,i,ultimo);
}
}
Descarga el código fuente desde aquí.
