A common.h include #include <stdio.h> #include <time.h> #define MAXN int A[MAXN], n; double start,end; void inputdata(

Size: px

Start display at page:

Download "A common.h include #include <stdio.h> #include <time.h> #define MAXN int A[MAXN], n; double start,end; void inputdata("

ありさこうだ
4 years ago
Views:

1 A common.h include #include <stdio.h> #include <time.h> #define MAXN 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

2 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)/ ; 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

3 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

4 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

5 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

6 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

7 void insertionsort(int,int); int main(void) inputdata(); A[0]= ;//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

8 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

9 clock() time() gettimeofday() getrusage() ,1000,2000,2500,5000,7500,10000,20000, 30000,40000,50000,60000,70000,80000,90000,100000,150000,200000,300000,400000, random.c c rand rand random.c rand txt prompt>./random > rand/rand txt 100 prompt> cat rand/rand txt #include <stdlib.h> #include <stdio.h> #include <time.h> int main(void) int a,i,j; scanf("%d",&a); 9

10 printf("%d\n",a); srand((unsigned) time(null)); // 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 quick.dat prompt>./timing.sh quick prompt> cat data/quick.dat

11 #!/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

12 5 6 n 2 nlogn n 2 nlogn O(n 2 ) O(nlogn) 2 1 [1] [2] Mover.C : [3] GnuplotTips 12

‚æ2›ñ C„¾„ê‡Ìš|

‚æ2›ñ C„¾„ê‡Ìš| I 8 10 10 I ( 6 ) 10 10 1 / 23 1 C ( ) getchar(), gets(), scanf() ( ) putchar(), puts(), printf() 1 getchar(), putchar() 1 I ( 6 ) 10 10 2 / 23 1 (getchar 1 1) 1 #include 2 void main(void){ 3 int