Clase 9(Metodos de Ordenamiento)

#include <iostream>
using namespace std;
#include<stdio.h>
#include <math.h>
#include <stdlib.h>
#define max 100
#define MAX 100
#define n 9
/*PARTE DEL METODO DE MERGE SORT */
struct lista
{
   int numero;
   struct lista *sig;
};

typedef struct lista LISTATYPE;
typedef LISTATYPE * LISTAPTR;

void CreaLista (LISTAPTR *);
void AVerLaLista (LISTAPTR);
void FreeLista (LISTAPTR *);
void MS (int, int, LISTAPTR *);
void mezcla (int, int, int, int, LISTAPTR *);
/*PARTE DEL METODO DE MERGE SORT*/
void mostrar (int A[],int x);
void quicksort (int A[], int inf, int sup);
//id radixsort(int x[], int n);
void shakesort (int A[], int m);
void mostrarshake(int A[],int x);
void SortHeap(int[], int);
void BURBUJA();
void SHELL();
void SELDIR();
void QUICK();
void RADIX();
void MERGES();
void SHAKE();
void INSORT();
void MONTICULO();

int i,m,k,j,A[max],menor;

void aleatorios()
{
cout<<"\nOriginal:";
srand(time(NULL));
for(i=0;i<n;i++)
{
  A[i]= (1 + rand() % 15);
  cout<<"\t"<<A[i];
}

}


int main()
{
  int op;
   do{
  cout<<" M E T O D O S      DE    O R D E N A M I E N T O";
  cout<<"\n________________________________________________________________________________\n";
  cout<<"\n1.-BURBUJA                  2.SHELL SORT               3.QUICK SORT \n";
  cout<<"4.-SELECCION DIRECTA        5.RADIX                    6.MERGE SORT (o MEZCLA) \n";
  cout<<"7.-SHAKE SORT (o SACUDIDA)  8.HEAP SORT(o MONTICULO)   9. INSORT (o INSERCION DIRECTA)  \n";
  cout<<"____________________________________________________________________________________ \n";
  cout<<"                                                      PROGRAMADO NESTOR CALDERON.";
  aleatorios();
  //gotoxy(15,20);

  op=4;
  switch(op)
{
case 1: BURBUJA();op=0; break;
case 2: SHELL();op=0; break;
case 3: QUICK();op=0; break;
case 4: SELDIR();op=0; break;

}
}while(op!=0);
return 0;

}


// BURBUJA.
void BURBUJA()
{


for(i=0;i<n;i++)
  {
    for(j=0;j<n-1;j++)
    {
      if(A[i]>A[j])
       {
m=A[i];
A[i]=A[j];
A[j]=m;
       }
    }

  }
  cout<<"\nBurbuja: ";
  for(i=0;i<n;i++)
  {
   cout<<"\t"<<A[i];
  }



}

//SHELL SORT.
void SHELL()
{

int cont,pasos,temp,i;

for(cont=n/2;cont!=0;cont/=2)
for(pasos=1;pasos!=0;)
{
pasos=0;
for(i=cont;i<n;i++)
if(A[i-cont]>A[i])
{
temp=A[i];
A[i]=A[i-cont];
A[i-cont]=temp;
pasos++;
}
}
cout<<"\nSHELL SORT:";
for(i=0;i<n;i++)
   {
    cout<<"\t"<<A[i];

   }

}

//SELECCION DIRECTA.
void SELDIR()
{
   cout<<"\nSeleccion Directa:\n";
  
  for(i=0;i<=n-1;i++)
    {
      menor=A[i];
      k=i;
      for(j=i+1;j<n;j++)
{
   if(A[j]<menor)
     {
      menor=A[j];
      k=j;
     }
}

    A[k]=A[i];
    A[i]=menor;

    }
   cout<<"\t";
   for(i=0;i<n;i++)
   {
   cout<<"\t"<<A[i];
   }

}

//QUICK SORT."\t"
void quicksort (int A[], int inf, int sup)
{
     int elem_div = A[sup];
     int temp ;
     int i = inf - 1, j = sup;
     int cont = 1;
     if (inf >= sup)
  return;
     while (cont)
  {
  while (A[++i] < elem_div);
  while (A[--j] > elem_div);
  if (i < j)
       {
       temp = A[i];
       A[i] = A[j];
       A[j] = temp;
       }
  else
      cont = 0;
  }
     temp = A[i];
     A[i] = A[sup];
     A[sup] = temp;
     quicksort (A, inf, i - 1);
     quicksort (A, i + 1, sup);
}

void mostrar (int A[],int x)
{
     int i;
     cout<<"\nmostrar ";
     for (i=0; i<x; i++)
     cout<<"\t"<<A[i];
    
     //getch();
}

void QUICK()
{
    cout<<"\nQUICKSORT ";
quicksort (A, 0, n-1);
mostrar (A,n);

}

//RADIX
/*void RADIX()
{
//clrscr();
  int x[50];
  //int x[50] = {NULL}, i;
  //static int n;

  int n,i;
  int Veces;
  cout<<"******ORDENACION POR RADIX******\n";
  printf("\nCUANTOS NUMEROS DESEAS ORDENAR : ");
  Veces=7;;
  
  cout<<"\nINGRESE LOS "<<Veces<<" NUMEROS.\n\n";
  
  for (n = 0;n<Veces; n++)
  x[n]=8;//o diferente 
   if ((x[n]=0)) 
   {
   }
   //break;
  if (n)
    radixsort (x, n);
    cout<<"\n";
    cout<<"La ORDENACION RADIX DE "<<Veces<<" ELEMENTOS:\n\n";
  for (i = 0; i < n; i++)
    printf("A[%d] : %d \n",i,x[i]);
}

void radixsort(int x[], int n)
{
  int front[10], rear[10];
  struct {
    int info;
    int next;
  } node[MAX];
  int exp, first, i, j, k, p, q, y;
    for (i = 0; i < n-1; i++) {
    node[i].info = x[i];
    node[i].next = i+1;
  }
  node[n-1].info = x[n-1];
  node[n-1].next = -1;
  first = 0;
  for (k = 1; k < 5; k++) {
       for (i = 0; i < 10; i++) {
      rear[i] = -1;
      front[i] = -1;
    }

    while (first != -1) {
      p = first;
      first = node[first].next;
      y = node[p].info;
     exp = pow(10, k-1);
       j = (y/exp) % 10;
       q = rear[j];
      if (q == -1)
front[j] = p;
      else
node[q].next = p;
      rear[j] = p;
    }

    for (j = 0; j < 10 && front[j] == -1; j++);
      ;
    first = front[j];
while (j <= 9) {
    for (i = j+1; i < 10 && front[i] == -1; i++);
;
      if (i <= 9)
      {
p = i;
node[rear[j]].next = front[i];
      }
      j = i;
    }
    node[rear[p]].next = -1;
  }


  for (i = 0; i < n; i++) {
    x[i] = node[first].info;
    first = node[first].next;
  }
}
*/


//METODO DE MERGE SORT (O MEZCLA)
void MERGES()
{
   LISTAPTR inicio= NULL;

   CreaLista(&inicio);
   MS(0,MAX-1,&inicio);
   printf("\n\nNUMEROS ORDENADOS\n-------------------\n");
   AVerLaLista(inicio);
   FreeLista(&inicio);
}


void CreaLista (LISTAPTR *inicio)
{
  
   LISTAPTR nuevo, temp;

   cout<<"\n****** METODO DE MERGE SORT******\n\n";
   cout<<"CUANTOS NUMEROS DESEAS ORDENAR (MINIMO=6) : ";
  
   cout<<"\n";

   for (i=0; i<n; i++)
      {
cout<<"Capturar "<<"["<<i<<"] : ";
A[i]=34;
nuevo= (LISTAPTR) malloc(sizeof(LISTATYPE));
nuevo->sig= NULL;
nuevo->numero= A[i];
if (*inicio == NULL)
    *inicio= nuevo;
else
    {
       temp= *inicio;
       while (temp->sig != NULL)
  temp= temp->sig;
       temp->sig= nuevo;
    }
      }
}

void AVerLaLista (LISTAPTR inicio)
{


   if (inicio != NULL)
      {

printf("\n \t %d ",inicio->numero);
AVerLaLista(inicio->sig);
      }
}

void FreeLista (LISTAPTR *inicio)
{
   LISTAPTR temp= *inicio;

   if (*inicio != NULL)
      {
FreeLista(&((*inicio)->sig));
free(temp);
      }
}

void MS (int ini, int fin, LISTAPTR *inicio)
{
   int m, m1;

   if (ini < fin)
      {
m= (ini+fin)/2;
m1= m+1;
MS(ini,m,&(*inicio));
MS(m1,fin,&(*inicio));
mezcla(ini,m,m1,fin,&(*inicio));
      }
}

void mezcla (int ini, int m, int m1, int fin, LISTAPTR *inicio)
{
   LISTAPTR ci, cj;
   int i, j, k= 0, kC[MAX];

   ci= cj= *inicio;
   for (i=k; i<ini; i++,ci=ci->sig);
   for (j=k; j<m1; j++ ,cj=cj->sig);
   kC[k]= k;

   while (i<=m || j<=fin)
      {
if (i > m)
    {
       kC[k]= cj->numero;
       j++;
       cj= cj->sig;
    }
else
    if (j > fin)
       {
  kC[k]= ci->numero;
  i++;
  ci= ci->sig;
       }
    else
       if (ci->numero < cj->numero)
  {
     kC[k]= ci->numero;
     i++;
     ci= ci->sig;
  }
       else
  {
     kC[k]= cj->numero;
     j++;
     cj= cj->sig;
  }
k++;
      }

   for (ci=*inicio,i=k-k; i<ini; i++,ci=ci->sig);
   for (k=0; i<=fin; i++, k++,ci=ci->sig)
      ci->numero= kC[k];
}


//SHAKE SORT(o SACUDIDA)
void shakesort (int A[], int m)
{
    int intercambio;
    int i,izq,der,aux;
    intercambio = m-1;
    izq=1;
    der=m-1;
     if(izq<=der)
       for(i=der;i>=izq;i--)
{
       if(A[i-1]>A[i])
{
   aux=A[i-1];
   A[i-1]=A[i];
   A[i]=aux;
   intercambio=i;
}
}
    izq=intercambio+1;
    for(i=izq;i<der+1;i--)
     {
       if(A[i-1]>A[i])
  {
   aux=A[i-1];
   A[i-1]=A[i];
   A[i]=aux;
   intercambio=i;
  }
       der=intercambio-1;
     }
}
void mostrarshake(int A[],int x)
{
     //int i,n;
     cout<<"\nmostrar shake:";
     for (i=0; i<x; i++)
     cout<<"\t"<<A[i];
    
     //getch();
}

void SHAKE()
{
   int s;
   s=7;
   cout<<"\nOriginal:";
srand(time(NULL));
for(i=0;i<7;i++)
{
  A[i]= (1 + rand() % 15);
  cout<<"\t"<<A[i];
}
     shakesort(A,s);
     mostrarshake (A,s);
}

//INSORT o (INSERCION DIRECTA)
/*
void INSORT()
{
  int x,aux,k,n,A[MAX];

   //clrscr();
cout<<"******METODO DE INSERCION DIRECTA (O INSORT)******\n\n";
cout<<"CUANTOS NUMEROS DESEAS ORDENAR : ";
n=7;
cout<<"\n";
for(x=0;x<n;x++)
{
  cout<<"CAPTURANDO "<<"["<<x<<"] : ";
  A[x]=64;
  
}


for(x=0;x<n;x++)
   {
     aux=A[x];
     k=x-1;
     while(k>=0 && aux<A[k])
     {
       A[k+1]=A[k];
       k--;
     }
     A[k+1]=aux;
   }
  cout<<"\n NUMEROS ORDENADOS\n--------------------\n";
  for(x=0;x<n;x++)
  {
   cout<<" A["<<A[x]<<"]\n";

  }

}

//METODO DEL MONTICULO
void MONTICULO()

    {
int i, arr_num_items;
int n;
int arr[MAX];
//clrscr();
printf("\t*******METODO DE HEAP SORT o (MONTICULO)*******\n\n");
printf("CUANTOS NUMEROS DESEAS ORDENAR :");
//cin>>n;
n=7;
for(i=0;i<n;i++)
  {
   cout<<"CAPTURANDO A["<<i<<"] :";
   arr[i]=666;
   //c////in>>arr[i];

  }

arr_num_items = n;
for(i=arr_num_items; i>1; i--)
{
SortHeap(arr, i - 1);
}
printf("\nNUMEROS ORDENADOS\n----------------\n");
for (i = 0; i < arr_num_items; i++)
printf("%d\n",arr[i]);
    }
//sort heap
void SortHeap(int arr[], int arr_ubound)


{
int i,o;
int lChild, rChild, mChild, root, temp;
root = (arr_ubound-1)/2;
for(o=root;o>=0;o--)
{
    for(i=root;i>=0;i--)
{
lChild = (2*i)+1;
rChild = (2*i)+2;
if ((lChild <= arr_ubound) && (rChild <= arr_ubound))
    {
    if(arr[rChild] >= arr[lChild])
    mChild = rChild;
    else
    mChild = lChild;
}
else
    {
    if(rChild > arr_ubound)
    mChild = lChild;
    else
    mChild = rChild;
}
if (arr[i] < arr[mChild])


    {
    temp = arr[i];
    arr[i] = arr[mChild];
    arr[mChild] = temp;
}
    }
}
temp = arr[0];
arr[0] = arr[arr_ubound];
arr[arr_ubound] = temp;

    
}

*/