Ordenamiento Rápido"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. 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).
#include<iostream>
#include<string>
#define N 100
void ordrapido (int a[],int primero,int ultimo);
void ord (int a[],int n);
void entradaLista (int a[], int n);
void imprimirLista (int a[], int n);
int numero[10];
int movimientos=0;
int aux;
using namespace std;
//
int main(){
int n=sizeof(numero)/sizeof(int);
char opcion;
bool salir =false;
bool lleno=false;
int v[N];
do {
cout<<"\nIntroduzca el numero de elementos:"<<endl;
cin>>n;
} while ((n < 1) && (n > N));
while (! salir) {
cout<<"*** ORDENAMIENTO QUICKSORT ***"<<endl;
cout<<"a)INSERTAR NUMEROS"<<endl;
cout<<"b)ORDEN QUICKSORT"<<endl;
cout<<"z)Salir"<<endl;
cout<<"Elija una opcion"<<endl;
cin>>opcion;
if(opcion == 'z' || opcion == 'Z' ){
salir = true;
}else{
switch(opcion){
case 'a':
case 'A':
entradaLista(v, n);
break;
case 'B':
case 'b':
ord(v, n);
cout<<"\nLista ordenada de elementos"<<n<<endl;
imprimirLista(v, n);
break;
default:
cout << "Opcion no aceptada"<< endl;
}
}
}
system("PAUSE");
}
void entradaLista (int a[], int n)
{
for(int i=0;i<n;i++){
cout<<"VALOR"<<i+1<<endl;
cout<<"dame el numero"<<endl;
cin>>numero[i];
}
}
void ord (int a[],int n)
{
ordrapido(numero,0,n-1);
}
void ordrapido (int a[],int primero,int ultimo)
{
int i, j,central;
int pivote;
central=(primero+ultimo)/2;
pivote =numero[central];
i=primero;
j=ultimo;
do{
while(numero[i]<pivote)
{
i++;
}
while(numero[j]>pivote)
{
j--;
}
if(i<=j){
aux=numero[i];
numero[i]=numero[j];
numero[j]=aux;
i++;
j--;
}
}while(i<=j);
if(primero < j){
ordrapido(numero,primero,j);
}
if(i < ultimo){
ordrapido(numero,i,ultimo);
}
movimientos++;
}
void imprimirLista (int a[], int n)
{
int i;
cout<<" numeros ordenados:"<<"\n movimientos: "<<movimientos<<endl;
for(int i=0;i<n;i++){
cout<<"numero:\n"<<numero[i]<<endl;
//if(i<n-1)
//cout<<","<<endl;
}
system("PAUSE");
//Alejandro hdz
}
Comentarios
Publicar un comentario
Hola que tal,dime tu opinión