2 065762A 19 7 13 1 2 2.1 common.h include #include <stdio.h> #include <time.h> #define MAXN 1000000 int A[MAXN], n; double start,end; void inputdata(void) int i; // printf(" "); scanf("%d",&n); // printf(" "); for(i=1;i<=n;i++) scanf("%d",&a[i]); return; 1
void printdata(void) printf("%07d %10.4f\n", n, end - start); return; void swap(int x,int y) //A[x] A[y] int temp; temp=a[x]; A[x]=A[y]; A[y]=temp; #include <sys/time.h> #include <sys/resource.h> double getrusage_sec() struct rusage t; struct timeval tv; getrusage(rusage_self, &t); tv = t.ru_utime; // return tv.tv_sec + (double)tv.tv_usec*1e-6; return (tv.tv_sec + tv.tv_usec)/1000.0000; 2.2 #include <stdio.h> #include "common.h" //common.h void selectionsort(int,int ); int main(void) inputdata(); start=getrusage_sec();// start selectionsort(1,n); end=getrusage_sec();// end 2
printdata(); void selectionsort(int p,int q) int i,j,cmin; for(j=p;j<=q;j++) cmin=j; for(i=j+1;i<=q;i++) if(a[cmin]>a[i])cmin=i; swap(j,cmin); 2.3 #include <stdio.h> #include "common.h" void insertionsort(int,int); int main(void) inputdata(); start=getrusage_sec(); insertionsort(1,n); end=getrusage_sec(); printdata(); void insertionsort(int p,int q) int i,j,c; for(j=p+1;j<=q;j++) c=a[j]; i=j; while(i>p&&a[i-1]>c) A[i]=A[i-1];i=i-1; A[i]=c; 3
2.4 #include <stdio.h> #include "common.h" void heapsort(int,int); void makeheap(int,int); void heapify(int,int); void printdata_reverse(void); int main(void) inputdata(); start=getrusage_sec(); heapsort(1,n); end=getrusage_sec(); //printdata_reverse(); printdata(); void heapsort(int s,int t) int i; makeheap(s,t); for(i=t;i>=s+1;i--) swap(s,i); heapify(s,i-1); //A[s]...A[t] void makeheap(int s,int t) int i; 4
for(i=t;i>=s;i--) heapify(i,t); //A[p] Shift-down void heapify(int p,int q) int r; r=2*p; if(r <= q) if(r<q && A[r]>A[r+1]) r=r+1; if(a[p] > A[r]) swap(p,r); heapify(r,q); void printdata_reverse(void) int i; printf(" \n"); for(i=n;i>=1;i--) printf("%d ",A[i]); printf("\n"); 2.5 #include "common.h" void mergesort(int,int); void merge(int,int,int); int B[MAXN]; int main(void) inputdata(); start=getrusage_sec(); mergesort(1,n); end=getrusage_sec(); printdata(); 5
void mergesort(int p,int r) int q; if(p < r) q = (p+r)/2; mergesort(p,q);// mergesort mergesort(q+1,r); merge(p,q,r); A[p]...A[q] A[q+1]...A[r] void merge(int p,int q,int r) int i,j,k; i=p,j=q+1; // A A[i] A[j] B[k] for(k=p;k<=r;k++) if((j>r) ((i<=q)&&(a[i]<=a[j]))) B[k]=A[i]; i=i+1; else B[k]=A[j]; j=j+1; for(k=p;k<=r;k++) A[k]=B[k]; 2.6 #include <stdio.h> #include "common.h" int find_median3(int,int); int partition(int,int,int); void quicksort(int,int); 6
void insertionsort(int,int); int main(void) inputdata(); A[0]=-999999999;//A[0] start=getrusage_sec(); quicksort(1,n); end=getrusage_sec(); printdata(); int find_median3(int left,int right) int center,p; center=(left+right)/2; //A[left]<=A[center]<=A[right] if(a[left]>a[center])swap(left,center); if(a[left]>a[right])swap(left,right); if(a[center]>a[right])swap(center,right); p=a[center];//a[center] swap(center,right); return(p); int partition(int left,int right,int q) int i,j; i=left-1; j=right; do do i=i+1; while(a[i]<q); do j=j-1; while(a[j]>q); if(i<j)swap(i,j); while(i<j); swap(i,right); return(i); 7
void quicksort(int left,int right) int cutoff,pivot,i; cutoff=10; if((right-left)<cutoff) insertionsort(left,right); else pivot=find_median3(left,right); i=partition(left,right,pivot); quicksort(left,i-1);// (A[left]...A[i-1]) quicksort(i+1,right);// (A[i+1]...A[right]) void insertionsort(int p,int q) int i,j,c; for(j=p+1;j<=q;j++) c=a[j]; i=j; while(i>p&&a[i-1]>c) A[i]=A[i-1];i=i-1; A[i]=c; 3 c getrusage() getrusage() struct timeval 1000 int main(void) inputdata(); start=getrusage_sec(); <- insertionsort(1,n); end=getrusage_sec(); <- printdata(); end start 8
clock() time() gettimeofday() getrusage() 4 10 100 100,1000,2000,2500,5000,7500,10000,20000, 30000,40000,50000,60000,70000,80000,90000,100000,150000,200000,300000,400000,500000 500000 400000 4.1 random.c c rand rand 1 1000 random.c 10 500000 4.1.1 100 rand000100.txt prompt>./random > rand/rand000100.txt 100 prompt> cat rand/rand000100.txt 100 341 439 170 829 992 34 106 497 851 610 167 963 784 256 91 171 384 337 210 284 453 397 762 238 636 664 283 183 545 12 974 420 191 291 65 283 21 353 945 660 501 103 137 750 250 500 773 981 815 272 675 330 273 554 655 151 953 190 985 643 54 839 735 40 709 73 107 837 621 721 679 235 930 639 240 959 76 377 745 984 266 873 925 134 465 919 887 74 292 221 144 250 267 639 181 510 141 105 948 162 4.1.2 #include <stdlib.h> #include <stdio.h> #include <time.h> int main(void) int a,i,j; scanf("%d",&a); 9
printf("%d\n",a); srand((unsigned) time(null)); //1 1000 a for (i=0; i<a; i++) printf("%d\n",rand()%1000+1); 4.2 timing.sh prompt>./quick < randxxxxxx.txt randxxxxxx.txt rand ls./quick data xxx.dat 4.2.1 10 500000 quick.dat prompt>./timing.sh quick prompt> cat data/quick.dat 10 0.0000 100 0.0000 500 0.0000 1000 0.0000 2000 0.0000 2500 0.0000 5000 0.0000 7500 0.0000 10000 0.0000 20000 4.0010 30000 8.0010 40000 8.0000 50000 8.0010 60000 12.0010 70000 12.0010 80000 12.0000 90000 16.0010 10
100000 20.0010 150000 28.0020 200000 36.0020 300000 52.0040 400000 76.0050 500000 92.0060 4.2.2 #!/bin/sh # if [ $# -ne 1 ] ; then echo "prompt> $0 arg1" exit 1 fi rand ls list list= /bin/ls -1./rand data $1.dat touch./data/$1.dat //rand data/$1.dat for filename in $list do./$1 < rand/$filename >>./data/$1.dat done 11
5 6 n 2 nlogn n 2 nlogn O(n 2 ) O(nlogn) 2 1 [1] [2] Mover.C : http://kzk9.net/column/time.html [3] GnuplotTips http://t16web.lanl.gov/kawano/gnuplot/index.html 12