#include <stdio.h>
#include <stdlib.h>

int dummymedian(int *a)
{
    return a[4];
}

int qsfunc(const void *a,const void *b)
{
    return *((int *)a)-*((int *)b);
}

int qsmedian(int *a)
{
    qsort(a,9,sizeof(int),qsfunc);
    return a[4];
}

int maxmedian(int *a)
{
    int i;
    int max,mp;
    for(i=0,max=0,mp=0;i<9;i++)
      {
	  if(max<a[i])
	    { max=a[i]; mp=i; }
      }
    a[mp]=0;
    for(i=0,max=0,mp=0;i<9;i++)
      {
	  if(max<a[i])
	    { max=a[i]; mp=i; }
      }
    a[mp]=0;
    for(i=0,max=0,mp=0;i<9;i++)
      {
	  if(max<a[i])
	    { max=a[i]; mp=i; }
      }
    a[mp]=0;
    for(i=0,max=0,mp=0;i<9;i++)
      {
	  if(max<a[i])
	    { max=a[i]; mp=i; }
      }
    a[mp]=0;
    for(i=0,max=0,mp=0;i<9;i++)
      {
	  if(max<a[i])
	    { max=a[i]; mp=i; }
      }
    return max;
}

int bsmedian(int *a)
{
    int i,t,f=1;
    while(f)
      {
	  f=0;
	  for(i=0;i<8;i++)
	    {
		if(a[i]<a[i+1])
		  { t=a[i]; a[i]=a[i+1]; a[i+1]=t; f=1;}
	    }
      }
    return a[4];
}

int ssmedian(int *a)
{
    int i,j,t;
    for(i=0;i<5;i++)
      for(j=i+1;j<9;j++)
	{
	    if(a[i]<a[j])
	      { t=a[i]; a[i]=a[j]; a[j]=t; }
	}
    return a[4];
}

inline int plfirststage(int *a,int &s1,int &s2,int &s3)
{
    if((a[0]>a[1])&&(a[0]>a[2]))
      { 
	  s1=a[0]; 
	  if(a[1]>a[2])
	    { s2=a[1]; s3=a[2]; }
	  else
	    { s2=a[2]; s3=a[1]; }
      }
    else if(a[1]>a[2])
      {
	  s1=a[1];
	  if(a[0]>a[2])
	    { s2=a[0]; s3=a[2]; }
	  else
	    { s2=a[2]; s3=a[0]; }
      }
    else
      {
	  s1=a[2];
	  if(a[0]>a[1])
	    { s2=a[0]; s3=a[1]; }
	  else
	    { s2=a[1]; s3=a[0]; }
      }
//    printf("%3d %3d %3d  |",s1,s2,s3);
}

int plmedian(int *a)
{
    int s1,s2,s3,s4,s5,s6,s7,s8,s9;
//    printf("\n");
    plfirststage(a+0,s1,s2,s3);
    plfirststage(a+3,s4,s5,s6);
    plfirststage(a+6,s7,s8,s9);
    int i;
    for(i=0;i<4;i++)
      {
	  if((s1>s4)&&(s1>s7))
	    { s1=s2; s2=s3; s3=0; }
	  else if(s4>s7)
	    { s4=s5; s5=s6; s6=0; }
	  else
	    { s7=s8; s8=s9; s9=0; }
      }
    if((s1>s4)&&(s1>s7))
      return s1;
    else if(s4>s7)
      return s4;
    else
      return s7;
}

int plmedian2(int *a)
{
    int s2,s3,s5,s6,s8,s9;
    register int s1,s4,s7;
    plfirststage(a+0,s1,s2,s3);
    plfirststage(a+3,s4,s5,s6);
    plfirststage(a+6,s7,s8,s9);
    int i;

    if((s1>s4)&&(s1>s7))
      { s1=s2; s2=s3; s3=0; }
    else if(s4>s7)
      { s4=s5; s5=s6; s6=0; }
    else
      { s7=s8; s8=s9; s9=0; }

    if((s1>s4)&&(s1>s7))
      { s1=s2; s2=s3; s3=0; }
    else if(s4>s7)
      { s4=s5; s5=s6; s6=0; }
    else
      { s7=s8; s8=s9; s9=0; }

    if((s1>s4)&&(s1>s7))
      { s1=s2; s2=s3; s3=0; }
    else if(s4>s7)
      { s4=s5; s5=s6; s6=0; }
    else
      { s7=s8; s8=s9; s9=0; }

    if((s1>s4)&&(s1>s7))
      { s1=s2; s2=s3; s3=0; }
    else if(s4>s7)
      { s4=s5; s5=s6; s6=0; }
    else
      { s7=s8; s8=s9; s9=0; }


    if((s1>s4)&&(s1>s7))
      return s1;
    else if(s4>s7)
      return s4;
    else
      return s7;
}

int plmedian3(int *a)
{
    int s[12]; s[3]=s[7]=s[11]=0;
//    printf("\n");
    plfirststage(a+0,s[0],s[1],s[2]);
    plfirststage(a+3,s[4],s[5],s[6]);
    plfirststage(a+6,s[8],s[9],s[10]);
    int i,*s1=s,*s2=s+4,*s3=s+8;

    for(i=0;i<4;i++)
      {
	  if((*s1>*s2)&&(*s1>*s3))
	    s1++;
	  else if(*s2>*s3)
	    s2++;
	  else
	    s3++;
      }
    if((*s1>*s2)&&(*s1>*s3))
      return *s1;
    else if(*s2>*s3)
      return *s2;
    else
      return *s3;
}


inline unsigned int plfirststage4(int *a)
{
    unsigned int s;
    if((a[0]>a[1])&&(a[0]>a[2]))
      { 
	  s=a[0]<<16; 
	  if(a[1]>a[2])
	    s |= (a[1]<<8)|(a[2]);
	  else
	    s |= (a[2]<<8)|(a[1]);
      }
    else if(a[1]>a[2])
      {
	  s=a[1]<<16; 
	  if(a[0]>a[2])
	    s |= (a[0]<<8)|(a[2]);
	  else
	    s |= (a[2]<<8)|(a[0]);
      }
    else
      {
	  s=a[2]<<16;
	  if(a[0]>a[1])
	    s |= (a[0]<<8)|(a[1]);
	  else
	    s |= (a[1]<<8)|(a[0]);
      }
    return s<<8;
}

int plmedian4(int *a)
{
    unsigned int s1,s2,s3;
//    printf("\n");
    s1=plfirststage4(a+0);
    s2=plfirststage4(a+3);
    s3=plfirststage4(a+6);
    int i;
    for(i=0;i<4;i++)
      {
	  if((s1>s2)&&(s1>s3))
	    s1=s1<<8;
	  else if(s2>s3)
	    s2=s2<<8;
	  else
	    s3=s3<<8;
//    printf("\n%X %X %X\n",s1,s2,s3);

      }
    if((s1>s2)&&(s1>s3))
      return s1>>24;
    else if(s2>s3)
      return s2>>24;
    else
      return s3>>24;
}

int plmedian5(int *a)  // 4 をループ展開
{
    unsigned int s1,s2,s3;
//    printf("\n");
    s1=plfirststage4(a+0);
    s2=plfirststage4(a+3);
    s3=plfirststage4(a+6);

    if((s1>s2)&&(s1>s3))
      s1=s1<<8;
    else if(s2>s3)
      s2=s2<<8;
    else
      s3=s3<<8;

    if((s2>s3)&&(s2>s1))
      s2=s2<<8;
    else if(s3>s1)
      s3=s3<<8;
    else
      s1=s1<<8;

    if((s3>s1)&&(s3>s2))
      s3=s3<<8;
    else if(s1>s2)
      s1=s1<<8;
    else
      s2=s2<<8;

    if((s1>s2)&&(s1>s3))
      s1=s1<<8;
    else if(s2>s3)
      s2=s2<<8;
    else
      s3=s3<<8;



    if((s1>s2)&&(s1>s3))
      return s1>>24;
    else if(s2>s3)
      return s2>>24;
    else
      return s3>>24;
}

inline int plfirststage6(int *a,unsigned char &s1,
			 unsigned char &s2,unsigned char &s3)
{
    if((a[0]>a[1])&&(a[0]>a[2]))
      { 
	  s1=a[0]; 
	  if(a[1]>a[2])
	    { s2=a[1]; s3=a[2]; }
	  else
	    { s2=a[2]; s3=a[1]; }
      }
    else if(a[1]>a[2])
      {
	  s1=a[1];
	  if(a[0]>a[2])
	    { s2=a[0]; s3=a[2]; }
	  else
	    { s2=a[2]; s3=a[0]; }
      }
    else
      {
	  s1=a[2];
	  if(a[0]>a[1])
	    { s2=a[0]; s3=a[1]; }
	  else
	    { s2=a[1]; s3=a[0]; }
      }
//    printf("%3d %3d %3d  |",s1,s2,s3);
}

int plmedian6(int *a)
{
    unsigned char s1,s2,s3,s4,s5,s6,s7,s8,s9;
    plfirststage6(a+0,s1,s2,s3);
    plfirststage6(a+3,s4,s5,s6);
    plfirststage6(a+6,s7,s8,s9);
    int i;

    if((s1>s4)&&(s1>s7))
      { s1=s2; s2=s3; s3=0; }
    else if(s4>s7)
      { s4=s5; s5=s6; s6=0; }
    else
      { s7=s8; s8=s9; s9=0; }

    if((s1>s4)&&(s1>s7))
      { s1=s2; s2=s3; s3=0; }
    else if(s4>s7)
      { s4=s5; s5=s6; s6=0; }
    else
      { s7=s8; s8=s9; s9=0; }

    if((s1>s4)&&(s1>s7))
      { s1=s2; s2=s3; s3=0; }
    else if(s4>s7)
      { s4=s5; s5=s6; s6=0; }
    else
      { s7=s8; s8=s9; s9=0; }

    if((s1>s4)&&(s1>s7))
      { s1=s2; s2=s3; s3=0; }
    else if(s4>s7)
      { s4=s5; s5=s6; s6=0; }
    else
      { s7=s8; s8=s9; s9=0; }


    if((s1>s4)&&(s1>s7))
      return s1;
    else if(s4>s7)
      return s4;
    else
      return s7;
}




typedef int medianfunc(int *a);

medianfunc *funcs[]={dummymedian,qsmedian,maxmedian,bsmedian,ssmedian,
		     plmedian,plmedian2,plmedian3,plmedian4,plmedian5,
		     plmedian6};
char *functype[]={"ダミー","Quicksort(Clib)","最大値消去x4","バブルソート",
"総当たりソート","パイプライン","pl2","pl3","pl4","pl5","pl6"};
int functypes=11;

void CheckReliability(void)
{
    int i,j,k;
    int a[9],b[9];
    for(i=0;i<1000;i++)
      {
	  for(j=0;j<9;j++)
	    { a[j]=rand()%256; printf("%3d ",a[j]); }
	  printf("|");
	  for(j=1;j<functypes;j++)
	    {
		for(k=0;k<9;k++)
		  b[k]=a[k];
		printf("%3d ",(funcs[j])(b));
	    }
	  printf("\n");
      }
}

void Benchmark(int c)
{
    int i,j;
    int a[9];
//    printf("by %s\n",functype[c]);
    for(i=0;i<3000000;i++)
      {
	  for(j=0;j<9;j++)
	    { a[j]=rand()%256; }
	  (funcs[c])(a);
      }
    return;
}

int main(int , char **argv)
{
    srand(0);
    int c=atoi(argv[1]);
    if(c<0)
      {
	  CheckReliability();
      }
    else
      Benchmark(c);
    return 0;
}