Вычислить время, отведенное на каждую сортировку - C (СИ)
Формулировка задачи:
Есть куча сортировок массива
Нужно вычислить сколько работает каждая
Важны именно милисекунды!
Препод сказал что есть какой-то способ
Я в растеряности, нужна помощь
#include <stdio.h> #include <stdlib.h> #include <time.h> #define N 50 typedef enum{false,true} bool; void print(int n,int *a) { int i; for(i=0;i<10;i++) printf("%3d ",a[i]); printf("\n\n"); } void BubbleSort (int n, int *a) { int i,j,temp; for(i=0;i<n;i++) { for(j=n-1;j>i;j--) if(a[j]>a[j-1]) { temp=a[j]; a[j]=a[j-1]; a[j-1]=temp; } } } void StraightSelection(int n, int *a) { int i,j,k,temp; for(i=0;i<n-1;i++) { k=i; temp=a[i]; for(j=i+1;j<n;j++) if(a[j]<temp) { temp=a[j]; k=j; } a[k]=a[i]; a[i]=temp; } } int increment(int n,int *seq) { int p1,p2,p3,s; p1=p2=p3=1; s=-1; do { if (++s%2) seq[s]=8*p1-6*p2+1; else { seq[s]=9*p1-9*p2+1; p2*=2; p3*=2; } p1*=2; } while (3*seq[s]<N); return (s>0) ? (--s):(0); } void ShellSort(int n,int *a) { long inc,i,j,seq[40]; int s,temp; s=increment(n,seq); while(s>=0) { inc=seq[s--]; for(i=inc;i<n;i++) { temp=a[i]; for(j=i-inc;((j>=0)&&(a[j]<temp));j-=inc) a[j+inc]=a[j]; a[j+inc]=temp; } } } void StraightmergeSort(int n,int *a) { int i,j,k,L,t; int h,m,p,q,r; bool up; up=true; p=1; do { h=1; m=n; if(up) {i=0;j=n-1;k=n;L=2*n-1;} else {k=0;L=n-1;i=n;j=2*n-1;} do { if(m>=p){q=p;} else {q=m;} m-=q; if(m>=p){r=p;} else{r=m;} m-=r; while((q!=0) && (r!=0)) { if(a[i]<a[j]) {a[k]=a[i];k+=h;i++;q--;}else {a[k]=a[j];k+=h;j--;r--;} } while(r>0) {a[k]=a[j];k+=h;j--;r--;} while(q>0) {a[k]=a[i];k+=h;i--;q--;} h=-h;t=k;k=L;L=t; }while(m!=0); up=!up; p=2*p; }while(p<n); if(!up) for(i=0;i<n;i++) a[i]=a[i+n]; } void QuickSort(int n,int *a) { int i,j,temp,p; i=0;j=n; p=a[n>>1]; do { while(a[i]<p)i++; while(a[j]>p)j--; if(i<=j) { temp=a[i]; a[i]=a[j]; a[j]=temp; i++; j--; } }while(i<=j); if(j>0) QuickSort(j,a); if(n>i) QuickSort(n-i,a+i); } void downheap(int n,int k,int a[]) { int new_elem; int child; new_elem=a[k]; while(k<=n/2) { child=2*k; if(child<n && a[child]<a[child+1]) child++; if(new_elem>=a[child]) break; a[k]=a[child]; k=child; } a[k]=new_elem; } void HeapSort(int size,int a[]) { int i; int temp; for(i=size/2-1;i>=0;i--) downheap(size-1,i,a); for(i=size-1;i>0;i--) { temp=a[i];a[i]=a[0];a[0]=temp; downheap(i-1,0,a); } } int main() { int A1[N],A2[N],A3[N],A4[N],A5[N],A6[N]; int i; srand(time(0)); for(i=0;i<N;i++) A1[i]=A2[i]=A3[i]=A4[i]=A5[i]=A6[i]=rand()%100; BubbleSort(N,A1); StraightSelection(N,A2); StraightmergeSort(N,A3); ShellSort(N,A4); QuickSort(N,A5); HeapSort(N,A6); print(N,A1); print(N,A2); print(N,A3); print(N,A4); print(N,A5); print(N,A6); return 0; }
Решение задачи: «Вычислить время, отведенное на каждую сортировку»
textual
Листинг программы
end = clock();