american gladiator.cpp

American Gladiator,You are consulting for a game show in which n contestants are pitted against n gl

#include <fstream>
#include <iostream>
#include <string>
#include <locale>
#include "math.h"
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef struct man
{
  int num;
  int value;
}man;
man *a,*b; //save contestants and gladiators value
void swap(int *a,int *b);
int Random(int i,int n); //get ranom number [i,n]
void Randomize_In_Place(man c[],int n);//generating a random permutation
int input();//Input n and generate tow array randomize in place,return the length of array
int Partition_a(int p,int r,int k);//partition a through compare with k
int Partition(int p,int r); //range [p r]
void Quicksort(int p,int r);
     
main()
{
  int i,n;
  
  n=input();
  for(i=0;i<n;i++)
    cout<<"num("<<a[i].num<<"): "<<"strength: "<<a[i].value<<endl;
  Quicksort(0,n-1);
  cout<<"The order of contestants: ";
   for(i=n-1;i>=0;i--)
    cout<<a[i].num<<" ";
   cout<<endl;
   return 0;
}




void swap(int *a,int *b)
{
  
    {
     int c=*a;
     *a=*b;
     *b=c;
    }
}

int Random(int i,int n)
{
  
   return     rand() / (RAND_MAX / (n-i+1) + 1)+i;
}
void Randomize_In_Place(man c[],int n)//generating a random permutation
{
  for(int i=0;i<n;i++)
     swap(c[i].value,c[Random(i,n-1)].value);
}

int input()//Input n and generate tow array randomize in place,return the length of array
{
  int n;
  cout<<"Please input the number of contests: ";
  cin>>n;
  a=new man[n];
  b=new man[n];
  int i;
  for(i=0;i<n;i++)
    {
      a[i].num=i;
      a[i].value=i;
      b[i].num=i;
      b[i].value=i;
      
    }
  Randomize_In_Place( a, n);
  Randomize_In_Place( b, n);  
  return n;
}
  
int Partition_a(int p,int r,int k)
{
  
  int i,j,temp;
  i=p-1;
  
  for(j=p;j<=r;j++)
    if(a[j].value<=k)
      {
       i++;
       if(a[j].value==k)
	 temp=i;
       swap(a[i].num,a[j].num);
       swap(a[i].value,a[j].value);
      }
  
  swap(a[temp].num,a[i].num);
  swap(a[temp].value,a[i].value);
  
  
  return i;
}
int Partition(int p,int r)
{
  int i,j,k;
  k=b[r].value;
  i=p-1;
  for(j=p;j<=r-1;j++)
    if(b[j].value<=k)
      {
       i++;
       swap(b[i].num,b[j].num);
       swap(b[i].value,b[j].value);
         
       }
  
  swap(b[r].num,b[i+1].num);
  swap(b[r].value,b[i+1].value);
 
  return i+1;
}
void Quicksort(int p,int r)
{
  int k,q;
  if(p<r)
    {
      k=Random(p,r); //get a value from b to compare with a
      Partition_a(p,r,b[k].value);
     
      swap(b[r].num,b[k].num);
       swap(b[r].value,b[k].value);
       
      q=Partition(p,r);
      Quicksort(p,q-1);
      Quicksort(q+1,r);
    }
}