Valentine Tài Sản của : Valentine Tiêu đề: Topic Thuật giải Sat Feb 26, 2011 10:05 amღ...............(¯™º•º†•»-»(¯`† Lớp 09CT112 Forum †´¯)«-«•†º•™¯)...............ღ
»♥(¯Ctrl¯)♥« Admin Tài Sản của : »♥(¯Ctrl¯)♥« Tiêu đề: Re: Topic Thuật giải Sat Feb 26, 2011 10:15 amღ...............(¯™º•º†•»-»(¯`† Lớp 09CT112 Forum †´¯)«-«•†º•™¯)...............ღ
Valentine Tài Sản của : Valentine Tiêu đề: Re: Topic Thuật giải Sat Feb 26, 2011 10:21 amღ...............(¯™º•º†•»-»(¯`† Lớp 09CT112 Forum †´¯)«-«•†º•™¯)...............ღ
daominhcanh Tài Sản của : daominhcanh Tiêu đề: Re: Topic Thuật giải Sat Feb 26, 2011 3:41 pmღ...............(¯™º•º†•»-»(¯`† Lớp 09CT112 Forum †´¯)«-«•†º•™¯)...............ღ #include<stdio.h> #include<conio.h> #include<iostream> #include<time.h> using namespace std; void HoanVi(int &a,int &b) { int r = a; a= b; b = r; } void Generate(int A[],int n) { srand(time(NULL)); for(int i=0; i<n; i++) A[i] = rand() % 1000 +1; } void SelectionSort(int A[],int n,int &ss,int &gan,double &tg) { ss= gan =0; clock_t bd = clock(); for(int i = 0; i< n-1; i++) { int min =i; for(int j = i+1; j<n; j++) { ss++; if(A[j] < A[min]) min = j; } if(min != i) { gan +=3; HoanVi(A[i], A[min]); } clock_t kt = clock(); tg = (double) (kt - bd)/CLOCKS_PER_SEC; } } void QuickSort(int A[],int l,int r,int &gan,double &tg) { int i = l, j = r, x = A[(l+r)/2]; clock_t bd = clock(); while(i<j) { while(A[i]<x) i++; while(A[j]>x) j--; if(i<=j) { gan += 3; HoanVi(A[i++],A[j--]); } if(l<j) QuickSort(A,l,j,gan,tg); if(i<r) QuickSort(A,i,r,gan,tg); } clock_t kt = clock(); tg = (double) (kt-bd)/CLOCKS_PER_SEC; } void Shift(int A[],int l,int r,int &ss,int &gan) { int i = l,j = 2*i + 1,x = A[i]; while(j<=r) { if(j<r) { ss++; if(A[j]<A[j+1]) j++; } if(x>=A[j]) return; gan++; A[i] = A[j]; i= j; j=2*i+1; } A[i]=x; } void CreateHeap(int A[],int n,int &ss,int &gan) { int l = n/2; int r= n-1; while(l>=0) { Shift(A,l,r,ss,gan); l--; } } void HeapSort(int A[],int n,int &ss,int &gan,double &tg) { clock_t bd = clock(); int l=0, r= n-1; CreateHeap(A,n,ss,gan); while(l<r) { gan+=3; HoanVi(A[l],A[r]); r--; Shift(A,l,r,ss,gan); } clock_t kt = clock(); tg = (double) (kt-bd)/CLOCKS_PER_SEC; } void main() { int A[100000], n = 100000, ss =1000,gan = 0; double tg; Generate(A,n); /////*SelectionSort(A,n,ss,gan,tg); ////cout<<"SeclectionSort: "<<endl;*/ //QuickSort(A,0,100,gan,tg); //cout<<"thoi gian thuc hien: "<<tg<<endl; ////cout<<"so phep so sanh: "<<ss<<endl; //cout<<"so phep gan: "<<gan<<endl; HeapSort(A,n,ss,gan,tg); cout<<"thoi gian thuc hien: "<<tg<<endl; cout<<"so phep so sanh: "<<ss<<endl; cout<<"so phep gan: "<<gan<<endl; for(int i = 1000; i<n;i++) cout<<A[i]<<" "; getch(); }
daominhcanh Tài Sản của : daominhcanh Tiêu đề: Re: Topic Thuật giải Sat Feb 26, 2011 3:42 pmღ...............(¯™º•º†•»-»(¯`† Lớp 09CT112 Forum †´¯)«-«•†º•™¯)...............ღ
Cùi Mía Tài Sản của : Cùi Mía Tiêu đề: Re: Topic Thuật giải Sun Feb 27, 2011 10:47 amღ...............(¯™º•º†•»-»(¯`† Lớp 09CT112 Forum †´¯)«-«•†º•™¯)...............ღ
daominhcanh Tài Sản của : daominhcanh Tiêu đề: Re: Topic Thuật giải Mon Feb 28, 2011 4:03 pmღ...............(¯™º•º†•»-»(¯`† Lớp 09CT112 Forum †´¯)«-«•†º•™¯)...............ღ
ngocoi Tài Sản của : ngocoi Tiêu đề: Re: Topic Thuật giải Mon Feb 28, 2011 8:29 pmღ...............(¯™º•º†•»-»(¯`† Lớp 09CT112 Forum †´¯)«-«•†º•™¯)...............ღ
haily2312 Tài Sản của : haily2312 Tiêu đề: Re: Topic Thuật giải Mon Feb 28, 2011 8:40 pmღ...............(¯™º•º†•»-»(¯`† Lớp 09CT112 Forum †´¯)«-«•†º•™¯)...............ღ
nhoc_dg