SORT_TIM

/*Џа®Ја ¬¬  б®авЁагҐв ¬ ббЁў Ё§ 25000 н«Ґ¬Ґ­в®ў 5 ¬Ґв®¤ ¬Ё:
  Їг§ламЄ®ўл© ¬Ґв®¤®¬,¬Ґв®¤®¬ ®вЎ®а ,ўбв ўЄЁ,¬Ґв®¤®¬ Ґ««  Ё •®а .
  Ќ  нЄа ­ ўлў®¤Ёвмбп ўаҐ¬п б®авЁа®ўЄЁ Є ¦¤л¬ Ё§ ¬Ґв®¤®ў.*/
#include<stdio.h>
#include<conio.h>
#include<iostream.h>
#include<stdlib.h>
#include<time.h>

const n=25000;
clock_t start1,end1,start2,end2,start3,end3,start4,end4,start5,end5;
double zz1;
int zx;

int   *a=new int[n];
int   *q=new int[n];
int   *w=new int[n];
int   *s=new int[n];
int   *p=new int[n];

//дг­ЄжЁп ᮧ¤ Ґв ¬ ббЁў
void *sozdanie(int *b,int k)
{
 int i,j,l;
 for(i=0;i<k;i++)
 b[i]=random(300);
 return b;
		 }

/*дг­ЄжЁп б®авЁагҐв ¬ ббЁў Їг§ламЄ®ўл¬ ¬Ґв®¤®¬
  ‘ ¬л© е७®ўл© ¬Ґв®¤.‘а ў­Ёў Ґв ᬥ¦­лҐ н«Ґ¬Ґ­вл Ё ЇаЁ ­Ґ®Ўе®¤Ё¬®бвЁ
  Ёе ЇҐаҐбв ў«пҐв.ЋзҐ­м ¬Ґ¤«Ґ­­л©,зв® ўЁ¤­® Ї® ўаҐ¬Ґ­Ё.*/
void *puz(int *b,int k)
{
  int i,j,t;
     for(i=0;i<k-1;i++)
      for(j=i+1;j<k;j++)
	if(b[i]>b[j])
	 {
	  t=b[i];
	  b[i]=b[j];
	  b[j]=t;
		   }
	return b;
		      }

/*дг­ЄжЁп б®авЁагҐв ¬ ббЁў ¬Ґв®¤®¬ ®вЎ®а 
  Ќ е®¤Ё¬ ¬Ё­Ё¬ «м­л© н«Ґ¬Ґ­в Ё ¬Ґ­пҐ¬ ҐЈ® ¬Ґбв ¬Ё б ЇҐаўл¬ н«Ґ¬Ґ­в®¬ ¬ ббЁў .
  ‡ вҐ¬ Ё§ ®бв ўиЁебп n-1 н«Ґ¬Ґ­в®ў ЁйҐ¬ ­ Ё¬Ґ­миЁ© ¬Ґ­пҐ¬ ҐЈ® ¬Ґбв ¬Ё б® ўв®-
  ал¬ н«Ґ¬Ґ­в®¬ ¬ ббЁў  Ё в Є ¤ «ҐҐ.ЌҐ ­  ¬­®Ј® «гзиҐ Їг§ламЄ®ў®© б®авЁа®ўЄЁ.*/
void *otbor(int *b,int k)
{
 int i,m,l,t,r;
   for(i=0;i<k-1;++i)
    {
     m=0;
     l=i;
     t=b[i];
	    for(r=i+1;r<k;++r)
	    {
	       if(b[r]<t)
	       {
		l=r;
		t=b[r];
		m=1;
		    }
		      }
     if(m)
     {
      b[l]=b[i];
      b[i]=t;
	     }
		    }
		    return b;
		       }

/*дг­ЄжЁп б®авЁагҐв ¬ ббЁў ¬Ґв®¤®¬ ўбв ўЄЁ
  ‘­ з «  б®авЁаговбп ЇҐаўле ¤ў  н«Ґ¬Ґ­в .‡ вҐ¬ ЎҐаҐвбп ваҐвЁ© н«Ґ¬Ґ­в Ёбв ўЁ-
  вмбп ў Ї®ап¤Є®ўго Ї®§ЁжЁо,ᮮ⢥вбўгойго ҐЈ® Ї®«®¦Ґ­Ёо ®в­®бЁвҐ«м­® ЇҐаўле
  ¤ўге.‡ вҐ¬ ў нв®в бЇЁб®Є ўбв ў«пҐвбп зҐвўҐавл© н«Ґ¬Ґ­в Ёв Є ¤ «ҐҐ.ЌҐ¬­®Ј®
  «гзиҐ а Ў®в Ґв,祬 ЇҐаўле ¤ў  ¬Ґв®¤ ,  Ґб«Ё ¬ ббЁў Ї®звЁ гЇ®а冷祭­л©,в®
  ¬Ґв®¤ а Ў®в Ґв ў®®ЎйҐ ®в«Ёз­®. randome-¤ Ґв Ў®«ҐҐ Ё«Ё ¬Ґ­ҐҐ гЇ®а冷祭­л©
  ¬ ббЁў.*/
void *vstavka(int *b,int k)
{
  int i,t,r;
  for(i=1;i<k;++i)
  {
   t=b[i];
	 for(r=i-1;r>=0 && t<b[r];r--)
	 b[r+1]=b[r];
   b[r+1]=t;
	    }
	    return b;
		     }

/*дг­ЄжЁп б®авЁагҐв ¬ ббЁў ¬Ґв®¤®¬ Ґ«« 
  ђ Ў®в Ґв §­ зЁвҐ«м­® Ўлбв॥,祬 ЇаҐ¤л¤гйЁҐ ¬Ґв®¤л.‘­ з «  б®авЁаговбп н«Ґ-
  ¬Ґ­вл,®вбв ойЁҐ ¤агЈ ®в ¤агЈ  ­  9 Ї®§ЁжЁ©,§ вҐ¬ ­  5,3,2,1.*/
void *Shell(int *b,int k)
{
  int i,x,j,gap,m;
  char a[5];
  a[0]=9; a[1]=5; a[2]=3; a[3]=2; a[4]=1;
     for(m=0;m<5;m++)
     {
      gap=a[m];
	   for(i=gap;i<k;i++)
	   {
	    x=b[i];
		  for(j=i-gap;x<b[j] && j>=0;j=j-gap)
		  b[j+gap]=b[j];
	    b[j+gap]=x;
		       }
			   }
	       return b;
				 }

//дг­ЄжЁп б®авЁагҐв ¬ ббЁў ¬Ґв®¤®¬ •®а 
void *Hoare(int *b,int left,int right)
{
 int i,j,x,y;
 i=left; j=right;
 x=b[(left+right)/2];
 do
   {
    while(b[i]<x && i<right) i++;
    while(x<b[j] && j>left) j--;

      if(i<=j)
      {
       y=b[i];
       b[i]=b[j];
       b[j]=y;
       i++; j--;
		}
				    }
     while(i<=j);
     if(left<j) Hoare(b,left,j);
     if(i<right) Hoare(b,i,right);
				   }



void main()
{
     randomize();
     sozdanie(a,n);

  textbackground(0);
  clrscr();
  window(20,5,60,15);
  textbackground(15);
  clrscr();
  textcolor(4);
  gotoxy(7,2);
  cprintf("‚лЎЁаҐвҐ ¬Ґв®¤ б®авЁа®ўЄЁ:");
  textcolor(10);
  gotoxy(7,4);
  cprintf("1-Џг§ламЄ®ўл© ¬Ґв®¤ б®авЁа®ўЄЁ");
  gotoxy(7,5);
  cprintf("2-ЊҐв®¤ ®вЎ®а ");
  gotoxy(7,6);
  cprintf("3-ЊҐв®¤ ўбв ўЄЁ");
  gotoxy(7,7);
  cprintf("4-ЊҐв®¤ Ґ«« ");
  gotoxy(7,8);
  cprintf("5-ЊҐв®¤ •®а ");
  gotoxy(20,9);
  cin>>zx;
	  switch (zx)
	  {
	   case 1:   start1 = clock();
		     puz(a,n);
		     end1 = clock();
		     zz1=(end1 - start1) / CLK_TCK;  break;
	   case 2:   start2 = clock();
		     otbor(a,n);
		     end2 = clock();
		     zz1=(end2 - start2) / CLK_TCK;  break;
	   cae 3:   start3 = clock();
		     vstavka(a,n);
		     end3 = clock();
		     zz1=(end3 - start3) / CLK_TCK;  break;
	   case 4:   start4 = clock();
		     Shell(a,n);
		     end4 = clock();
		     zz1=(end4 - start4) / CLK_TCK;  break;
	   case 5:   start5 = clock();
		     Hoare(a,0,n-1);
		     end5 = clock();
		     zz1=(end5 - start5) / CLK_TCK;  break;
							       }
  textbackground(0);
  clrscr();
  window(5,3,35,7);
  textbackground(5);
  clrscr();
  textcolor(14);
  gotoxy(3,2);
  cprintf("‚६п б®авЁа®ўЄЁ: %f",zz1);
  getch();
  window(36,10,78,23);
  textbackground(6);
  clrscr();
  textcolor(15);
  gotoxy(6,2);
  cprintf("‘।­ЁҐ १г«мв вл б®авЁа®ўЄЁ");
  gotoxy(4,3);
  cprintf("¤«п ўбҐе ¬Ґв®¤®ў:");
  gotoxy(4,6);
  cprintf("Џг§ламЄ®ўл© ¬Ґв®¤ б®авЁа®ўЄЁ  12.747253");
  gotoxy(4,7);
  cprintf("ЊҐв®¤ ®вЎ®а                   8.791209 ");
  gotoxy(4,8);
  cprintf("ЊҐв®¤ ўбв ўЄЁ                 5.714286 ");
  gotoxy(4,9);
  cprintf("ЊҐв®¤ Ґ««                    2.087912 ");
  gotoxy(4,10);
  cprintf("ЊҐв®¤ •®а                     0.054945 ");
  getch();
	  }