METODOS DE ORDENAMIENTO

[theyasav]

METODOS DE ORDENAMIENTO
http://www.infount.tk/

Código: Seleccionar todo

1. #include<conio.h>


2. #include<iostream>


3. #include<stdlib.h>


4. #include<time.h>


5. #include<math.h>


6. #define MAX_LLAVE 1000000


7.  


8. using namespace std;


9.                                     //DECLARACION DE FUNCIONES


10. void burbuja (int,int *);


11. void burbujam(int, int *);


12. void seleccion(int,int *);


13. void shelldes(int,int *);


14. void inserccion(int,int *);


15. void shell(int,int *);


16. void merge(int *, int, int);


17. void mezcla(int *, int, int,int);


18. void rapida(int *,int, int);


19. int partir(int *,int, int);


20.  


21. int *generarAleatorios(int N);


22. int getMilisegundos(clock_t c);


23.  


24. double comp=0;


25.                                            


26. void pasar(int *,int *, int);


27.  


28.                                     //PROGRAMA PRINCIPAL


29.  


30. int main()


31. {


32.  int N,opcion1,opcion2;


33.  


34.  int *A =(int*)malloc(N*sizeof(double));


35.  clock_t t1, t2;


36.  


37.  int tiempo=0;


38.  long i;


39.  //PRESENTACION


40.  


41.  cout<<"\t\t....:::::UNIVERSIDAD NACIONAL DE TRUJILLO::::...."<<endl;


42.  cout<<"\t\t\t--------ESTRUCTURA DE DATOS--------"<<endl;


43.  cout<<"\t\t\t\tESCUELA DE INFORMATICA"<<endl<<endl;


44.  cout<<"\t\t\t\tALGORITMOS DE ORDENACION"<<endl<<endl;


45.  


46.  


47.  cout<<"\t\t\tINGRESA NUMERO DE DATOS:----->";


48.  cin>>N;


49.  


50.  


51.  A=generarAleatorios(N);


52.  


53.  


54.  cout<<endl<<endl<<"\t                 MENU 1:"<<endl;


55.  cout<<"\t   1_-ORDENAR ALEATORIAMENTE (Caso Normal)"<<endl;


56.  cout<<"\t   2_-ORDENAR ASCENDENTEMENTE (Mejor Caso)"<<endl;


57.  cout<<"\t   3_-ORDENAR DESCENDENTEMENTE (Peor Caso)"<<endl;


58.  cout<<"\t   4_-SALIR"<<endl;


59.  do


60.    {


61.     cout<<"\t\t-----Ingrese opcion:";


62.     cin>>opcion1;


63.    


64.    }


65.  while(opcion1<1||opcion1>4);


66.  


67.  switch(opcion1)


68.  {


69.        case 1:


70.               cout<<endl<<endl<<"ELEMENTOS ORDENADOS ALEATORIAMENTE:------->"<<endl;


71.                   break;


72.  


73.        case 2:


74.                   shell(N,A);


75.                   comp=0;


76.                   cout<<endl<<endl<<"ELEMENTOS ORDENADOS ASCENDENTEMENTE:------->"<<endl;


77.                   break;


78.  


79.        case 3:


80.                   shelldes(N,A);


81.                   cout<<endl<<endl<<"ELEMENTOS ORDENADOS DESCENDENTEMENTE:------->"<<endl;


82.                       break;


83.  


84.        case 4:


85.               exit(1);


86.              


87.        default:


88.                cout<<"La opcion no es correcta";


89.        }


90.  


91.  


92.  


93.  


94.  cout<<endl<<endl<<"\t              MENU 2 "<<endl;


95.  cout<<"\t   1_-ORDENAMIENTO BURBUJA SIMPLE"<<endl;


96.  cout<<"\t   2_-ORDENAMIENTO BURBUJA MEJORADO"<<endl;


97.  cout<<"\t   3_-ORDENAMIENTO SELECCION"<<endl;


98.  cout<<"\t   4_-ORDENAMIENTO INSERCCION"<<endl;


99.  cout<<"\t   5_-ORDENAMIENTO SHELL"<<endl;


100.  cout<<"\t   6_-ORDENAMIENTO MEZCLA"<<endl;


101.  cout<<"\t   7_-ORDENAMIENTO RAPIDO"<<endl;


102.  cout<<"\t   8_-SALIR"<<endl;


103.  


104.            


105.  cout<<endl<<endl<<"\t---->Ingrese Una Opcion Del 1-8:";


106.  cin>>opcion2;


107.  


108.  


109.  switch(opcion2)


110.       {


111.        case 1:


112.                   t1=clock();


113.                   burbuja(N,A);


114.                   t2=clock();


115.                   tiempo=getMilisegundos(t2-t1);


116.                   cout<<endl<<"[_____METODO BURBUJA SIMPLE_____]";


117.                   cout<<endl<<"TIME          :"<<tiempo;


118.                   cout<<endl<<"COMPARACIONES :"<<comp;


119.                   break;


120.  


121.        case 2:


122.                   t1=clock();


123.                   burbujam(N,A);


124.                   t2=clock();


125.                   tiempo=getMilisegundos(t2-t1);


126.                   cout<<endl<<"[_____METODO BURBUJA MEJORADO_____]";


127.                   cout<<endl<<"TIME          :"<<tiempo;


128.                   cout<<endl<<"COMPARACIONES :"<<comp;


129.                   break;


130.  


131.        case 3:


132.  


133.                   t1=clock();


134.                   seleccion(N,A);


135.                   t2=clock();


136.                   tiempo=getMilisegundos(t2-t1);


137.                   cout<<endl<<"[_____METODO SELECCION_____]";


138.               cout<<endl<<"TIME          :"<<tiempo;


139.                   cout<<endl<<"COMPARACIONES :"<<comp;


140.                   break;


141.  


142.        case 4:        


143.                   t1=clock();


144.                   inserccion(N,A);


145.                   t2=clock();


146.                   tiempo=getMilisegundos(t2-t1);


147.                   cout<<endl<<"[_____METODO INSERCCION_____]";


148.               cout<<endl<<"TIME          :"<<tiempo;


149.                   cout<<endl<<"COMPARACIONES :"<<comp;


150.                   break;


151.  


152.        case 5:          


153.                   t1=clock();


154.                   shell(N,A);


155.                   t2=clock();


156.                   tiempo=getMilisegundos(t2-t1);


157.                   cout<<endl<<"[_____METODO SHELL_____]";


158.                   cout<<endl<<"TIME          :"<<tiempo;


159.                   cout<<endl<<"COMPARACIONES :"<<comp;


160.                   break;


161.        


162.        case 6:              


163.               t1=clock();


164.                   merge(A,0,N-1);


165.                   t2=clock();


166.                   tiempo=getMilisegundos(t2-t1);


167.                   cout<<endl<<"[_____METODO MEZCLA_____]";


168.               cout<<endl<<"TIME          :"<<tiempo;


169.                   cout<<endl<<"COMPARACIONES :"<<comp;


170.                   break;


171.              


172.            case 7:          


173.               t1=clock();


174.                   rapida(A,0,N-1);


175.                   t2=clock();


176.                   tiempo=getMilisegundos(t2-t1);


177.                   cout<<endl<<"[_____METODO RAPIDO_____]";


178.               cout<<endl<<"TIME          :"<<tiempo;


179.                   cout<<endl<<"COMPARACIONES :"<<comp;


180.                   break;


181.            


182.         case 8:


183.                exit(1);      


184.        


185.            default:


186.                    cout<<"La opcion no es correcta"<<endl<<endl;


187.        }


188.  


189.  


190.            


191.  


192.  


193. cout<<endl<<endl;


194.  


195.  


196.         system("PAUSE");


197.  return EXIT_SUCCESS;


198.  


199. }


200.  


201.  


202.                                             //DESARROLLO DE LA FUNCIONES//


203.                                            


204.                                          


205. //Funcion para generar los numeros aleatorios


206. int *generarAleatorios(int N)


207. {


208.  int *A=new int[N];


209.  srand(time(NULL));


210.  


211.  for(int i=0;i<N;i++)


212.      A[i]=(int)((((double)rand())/RAND_MAX)*MAX_LLAVE);


213.  


214.  return A;


215. }


216.  


217. //Funcion para calcular el tiempo


218. int getMilisegundos(clock_t c)


219. {


220.  int tiempo=0;


221.  tiempo=(int)((c/(double)CLOCKS_PER_SEC)*1000);


222.  return tiempo;


223. }


224.  


225.                                                //METODOS DE ORDENAMIENTO


226.  


227.  


228.  


229. //Metodo Burbuja Simple Ascendente


230. void burbuja (int N,int *A)


231. {


232.  comp=0;


233.  int B;


234.  


235.  for (int i=N-1;i>=1;i--)


236.      for(int j=0;j<=i-1;j++)


237.          {


238.          comp++;


239.          if (A[j]>A[j+1])


240.                 {


241.                  B=A[j];


242.                  A[j]=A[j+1];


243.                  A[j+1]=B;


244.             }


245.           }


246. }


247.  


248.  


249. //Metodo Burbuja Mejorada Ascendente


250. void burbujam(int N,int *A)


251. {


252.  comp=0;


253.  int B,i,j=1;


254.  int bandera=1;


255.  while(bandera==1)


256.    {


257.  


258.       bandera=0;


259.       for(i=0;i<N-j;i++)


260.           {


261.            comp++;


262.            if (A[i]>A[i+1])


263.                   {


264.                    bandera=1;


265.                    B=A[i];


266.                    A[i]=A[i+1];


267.                    A[i+1]=B;


268.               }


269.      


270.          }j++;


271.    }


272. }


273.  


274. //Metodo Seleccion Ascendente


275. void seleccion(int N, int *A)


276. {


277.  


278.  comp=0;


279.  int B;


280.      for(int i=0;i<=N-2;i++)


281.              for(int j=i+1;j<=N-1;j++)


282.              {


283.               comp++;


284.                   if (A[i]>A[j])


285.                      {


286.                       B=A[i];


287.                       A[i]=A[j];


288.                       A[j]=B;


289.                      }


290.             }


291.  


292. }


293.  


294. //Metodo Inserccion Ascendente


295. void inserccion(int N,int *A)


296. {


297.  


298.  comp=0;


299.  int i,j;


300.  int temp;


301.  


302.  


303.  for(i=1;i<=N-1;i++)


304.     {


305.      comp++;              


306.      temp=A[i];


307.      j=i-1;


308.      while(j>=0 && A[j]>temp)


309.           {


310.           A[j+1]=A[j];


311.           j--;


312.           }


313.     A[j+1]=temp;


314.     }


315.  


316. }


317.  


318.  


319. //Metodo Shell Ascendente


320. void shell(int N,int *A)


321. {


322.  comp=0;


323.  int i,j,bandera,B;


324.  


325.  


326.  for(j=N/2;j>0;j=j/2)


327.     {


328.  


329.      do


330.         {


331.              bandera=0;


332.  


333.              for(i=0;i<N-j;i++)


334.             {


335.              comp++;    


336.                      if(A[i]>A[i+j])


337.                        {


338.                         B=A[i];


339.                         A[i]=A[i+j];


340.                         A[i+j]=B;


341.                         bandera=1;


342.                        }


343.                 }


344.         }      


345.      while(bandera);


346.  


347.   }


348.  


349. }


350.  


351. //Metodo Shell Descendente


352. void shelldes(int N,int *A)


353. {


354.  int i,j,bandera,B;


355.  


356.  


357.  for(j=N/2;j>0;j=j/2)


358.     {


359.      do


360.             {


361.              bandera=0;


362.  


363.              for(i=0;i<N-j;i++)


364.                      if(A[i]<A[i+j])


365.                         {


366.                          B=A[i];


367.                          A[i]=A[i+j];


368.                          A[i+j]=B;


369.                          bandera=1;


370.                         }


371.             }


372.      while(bandera);


373.      


374.   }


375.  


376. }


377.  


378. //Metodo Mezcla Ascendente


379. void mezcla(int *A, int izq, int der, int p)


380. {


381.  


382.      int tem=der-izq+1;


383.      int B[tem];


384.      int i,j,k;


385.      i=izq;


386.      j=p+1;


387.      k=0;


388.      


389.      while ((i<=p)&&(j<=der))


390.          {


391.           comp++;


392.             if (A[i]<A[j])


393.                {


394.                B[k]=A[i];


395.                i++;


396.                }


397.             else


398.                { B[k]=A[j];


399.                 j++;


400.                 }


401.          k++;


402.          }


403.  


404.     while(i<=p)


405.           {


406.            B[k]=A[i];


407.            k++;


408.            i++;


409.           }


410.  


411.     while(j<=der)


412.          {


413.           B[k]=A[j];


414.           k++;


415.           j++;


416.          }


417.          


418.     for(int i=0;i<=der-izq;i++)


419.         A[izq+i]=B[i];


420.  


421.          


422.      


423. }


424.  


425. void merge(int *A,int izq,int der)


426. {


427.  int p;


428.  


429.  if (izq<der)


430.     {


431.      p=(izq+der)/2;


432.      merge(A,izq,p);


433.      merge(A,p+1,der);


434.      mezcla(A,izq,der,p);


435.     }


436. }


437.  


438. //Metodo Rapido Ascendente


439. int partir(int *A,int izq, int der)


440. {


441.  


442.  int B;


443.  int p=A[izq];


444.  int i=izq;


445.  int j=der-1;


446.  int aux=0;


447.  int piv=der;


448.  


449.  


450.          B=A[izq];


451.          A[izq]=A[der];


452.          A[der]=B;


453.  


454.   while(i<j)


455.        {


456.         while((A[i]<p)&&(i<j))


457.               i++;


458.        


459.  


460.         while((A[j]>p)&&(j>i))


461.               j--;


462.              


463.         comp++;


464.        


465.         if(i<j)


466.            {


467.             B=A[i];


468.                 A[i]=A[j];


469.                 A[j]=B;


470.             i++;


471.             j--;


472.            }


473.       }


474.      


475.   if(A[j]<=p)


476.      {


477.       B=A[piv];


478.           A[piv]=A[j+1];


479.           A[j+1]=B;


480.       return  j+1;


481.      }


482.      


483.   else


484.      {


485.       B=A[piv];


486.           A[piv]=A[j];


487.           A[j]=B;


488.       return j;


489.      }


490. }    


491.  


492.  


493. void rapida(int *A,int izq, int der)


494. {


495.  int k;    


496.  if(izq<der)


497.     {


498.      k=partir(A,izq,der);


499.      rapida(A,izq,k-1);


500.      rapida(A,k+1,der);


501.     }    


502. }


503.