Sắp xếp và so sánh thời gian các giải thuật !!!

[huyhd7]

Xây dựng chuơng trình với các chương trình con sau:
1. Nhập n số thực (từ bàn fím, hoặc nhập ngẫu nhiên, hoặc nhập từ file)
2. Sắp xếp n số thực ( theo phương pháp đổi chỗ, Quick Sort, Heap Sort) và tính thời gian thực hiện (theo % giây)
3. So sánh thời gian thực hiện của từng giải thuật. (cái này e thấy khó nhất)

Câu 3 chưa ai làm được. hehe

[nhc1987]

Câu hỏi này có ai đó đã post rồi. Phiền bạn search trước khi hỏi.

[huyhd7]

Bài của em viết đó, mong các bác tham khảo và giúp đỡ, còn phần tính thời gian em vẫn chưa làm được.

#include <conio.h>
#include <stdio.h>
#include <iostream.h>
#include <stdlib.h>
#include <mem.h>

#define MAX 3267
#define size sizeof(int)

  void GioiThieu();
  void chonlua_kieunhap();
  void chonlua_pp();
  void banphim();
  void ngaunhien();
  void creatfile();
  void filetep();
  void dcho(int&,int&);
  void sx_doicho(int);
  void phanhoach(int,int,int&);
  void sx_quick(int,int);
  void Adjust(int,int);
  void time_1();
  void time_2();
  void time();
  void hienthi(int);
  void doicho();
  void quick();
  void heapsort();
  void menu_kieunhap(char);
  void menu_pp(char);

  int i,j,n,a[MAX],*index;
  char chon1,chon2,t;
  float time1,time2;
  char ten[15];
  FILE *f;

  void main()
       {
	  GioiThieu();
	  do{
	     chonlua_kieunhap();
	     menu_kieunhap(chon1);
	     chonlua_pp();
	     menu_pp(chon2);
	     cout<<"Thoat chuong trinh ko (Y/N) ? : ";
	     cin>>chon1;
	  }while((chon1 == 'n') ||(chon1 == 'N'));
       }

  void GioiThieu()
       {
	 clrscr();
	 cout<<"***********************************************************************"<<endl;
	                                    
	 cout<<"***********************************************************************"<<endl;
       }
  void chonlua_kieunhap()
       {
	 cout<<"     Hay chon lua cach de nhap : "<<endl;
	 cout<<"        1.Nhap tu ban phim\n";
	 cout<<"        2.Nhap ngau nhien\n";
	 cout<<"        3.Nhap tu file \n";
	 cout<<"        4.Thoat\n";
	 cout<<"     Lua chon cua ban :";
	 cin>>chon1;
       }
  void chonlua_pp()
       {
	 clrscr();
	 cout<<"Bai toan sap xep bang cac phuong phap :\n";
	 cout<<"1.Kieu doi cho\n";
	 cout<<"2.Kieu quick sort\n";
	 cout<<"3.Kieu heap sort\n";
	 cout<<"Thoat cho nhe no \n";
	 cout<<"Lua chon cua ban : ";
	 cin>>chon2;
       }
  void banphim()
       {
	 cout<<"Nhap vao tong so phan tu : ";cin>>n;
	   for (i=0;i<n;i++)
	       {
		 cout<<"\nNhap vao phan tu thu "<<i<<" : ";
		 cin>>a[i];
	       }
       }
  void ngaunhien()
       {
	 randomize();
	 cout<<"Nhap vao tong so phan tu muon tao : ";cin>>n;
	 for (i=0;i<n;i++)
	     a[i] = random(n) + 1;
       }
  void creatfile()
       {
	 cout<<"Nhap vao ten file can tao : ";cin>>ten;
	 f = fopen(ten,"wb");
	   for (i=0;i<n;i++)
	       {
		 cout<<"\nNhap vao phan tu thu "<<i<<" : ";
		 cin>>a[i];
	       }
	 fwrite(&a,size,n,f);
	 fclose(f);
       }
  void filetep()
       {
	 creatfile();
	 cout<<"\nCho biet ten file lay du lieu : ";cin>>ten;
	 f = fopen(ten,"rb");
	 fread(&a,size,n,f);
	 fclose(f);
       }
  void dcho(int &w,int &z)
       {
	 int tg = w;
	 w = z;
	 z = tg;
       }
  void sx_doicho(int m)
       {
	 for (i=0;i<m-1;i++)
	   for (j=i+1;j<m;j++)
	     if ( a[i] > a[j] )
		dcho(a[i],a[j]);
       }
  void phanhoach(int low,int up,int& pivot)
       {
	int pivotval=a[low];
	int i=low;
	int j=up;
	while(i<j)
	  {
	    while(a[i]<=pivotval && i<up) i++;
	    while(a[j]>pivotval)  j--;
	    if(i<j) dcho(a[i],a[j]);
	  };
	dcho(a[low],a[j]);pivot=j;
       }
  void sx_quick(int i,int j)
       {
	 int k;
	 if ( i<j )
	    {
	      phanhoach(i,j,k);
	      sx_quick(i,k-1);
	      sx_quick(k+1,j);
	    }
       }
  void Adjust(int first,int last)
       {
	  int r = first;
	  while ( r <= (last / 2))
	    if ( last == 2*r)
	       {
		 if (a[r] <a[last]) dcho(a[r],a[last]);
		 r = last;
	       }
	    else if ( ( a[r] <a[2*r] ) && (a[2*r] >= a[2*r+1]))
	       {
		 dcho(a[r],a[2*r]);
		 r = 2*r;
	       }
	    else if ( (a[r] < a[2*r+1]) && (a[2*r+1] > a[2*r]))
	       {
		 dcho(a[r],a[2*r+1]);
		 r = 2*r+1;
	       }
	    else r = last;


       }
  void time_1()
       {

       }
  void time_2()
       {
       }
  void time()
       {
       }
  void hienthi(int m)
       {
	 cout<<"\nKet qua sort : ";
	   for (i=0;i<m;i++)
	     cout<<a[i]<<"   ";
	 cout<<endl;
       }
  void doicho()
       {
	 GioiThieu();
	 cout<<"Chuong trinh sort bang phuong phap doi cho"<<endl;
	 sx_doicho(n);
	 hienthi(n);
	 time();
       }
  void quick()
       {
	 GioiThieu();
	 cout<<"Chuong trinh sort bang phuong phap Quick"<<endl;
	 sx_quick(0,n-1);
	 hienthi(n);
	 time();
       }
  void heapsort()
       {
	 int i;
	 GioiThieu();
	 cout<<"Chuong trinh sort bang phuong phap heap"<<endl;
	   for(i=n/2;i>=0;i--)
	     Adjust(i,n);
	   for (i=n;i>0;i--)
	       {
		 dcho(a[1],a[i]);
		 Adjust(1,j-1);
	       }
	 hienthi(n);
	 time();
       }
  void menu_kieunhap(char chon)
       {
	  switch (chon)
	      {
		case '1' : banphim();break;
		case '2' : ngaunhien();break;
		case '3' : filetep();break;
		case '4' : exit(0);
	      }
       }
  void menu_pp(char chon)
       {
	  switch (chon)
	      {
		case '1' : doicho();break;
		case '2' : quick();break;
		case '3' : heapsort();break;
		case '4' : exit(0);
	      }
       }

Chú ý phải bỏ code vào thẻ CODE ký tự {#} trên thanh công cụ. Nếu không sửa bài viết sẽ bị xóa.
posted by iamvtn

[kidkid]

Tính thời gian thì cậu nên lấy xung lock đổi ra sẽ chính xác hơn

[nanosi]

cho em hỏi bài này đã có ai giải rồi à . thế code ở đâu vậy . em search hoài mà không thấy .

[hoangtulai_hp]

#include <conio.h>
#include <stdio.h>
#include <iostream.h>
#include <stdlib.h>
#include <mem.h>

Này bạn, mình copy về Máy chạy thử sao nó báo thiếu include trên vậy bạn.

mình có file này không biết có giúp gì được cho bạn không nữa,vì mình cũng là lính mới trong lập trình C thui. Mới tham khảo buổi sáng của thầy giáo xong. hihhihi

#include <stdio.h>
#include <sys/timeb.h>
#include <time.h>
void main( void )
{
   struct _timeb timebuffer;
   _ftime( &timebuffer );
   
	

	char *timeline = ctime( & ( timebuffer.time ) );
    printf( "The time is %.19s.%hu %s", timeline, timebuffer.millitm, &timeline[20] );



	for (long i=0;i<100000;i++)
		for (long j=0;j<10000;j++);
			
				

   struct _timeb timebuffer1;
   _ftime( &timebuffer1 );

	char *timeline1 = ctime( & ( timebuffer1.time ) );
    printf( "The time is %.19s.%hu %s", timeline1, timebuffer1.millitm, &timeline1[20] );


	long milisecond = timebuffer1.millitm - timebuffer.millitm;
	long second = timebuffer1.time - timebuffer.time;

	printf("\n So giay %ld  va %ld phan tram giay",second, milisecond);

}

[hoangtulai_hp]

Mình chạy trên BC3.1 và bỏ cái include đó thì chạy đc nhưng code của thuật toán Heap Sort bị sai rùi bạn. Nó xắp xếp không có đúng, bạn coi và test lại thử coi nhé.