diff options
Diffstat (limited to 'bcc-bruce/misc/test/sort.t')
-rw-r--r-- | bcc-bruce/misc/test/sort.t | 104 |
1 files changed, 104 insertions, 0 deletions
diff --git a/bcc-bruce/misc/test/sort.t b/bcc-bruce/misc/test/sort.t new file mode 100644 index 0000000..34bcb9e --- /dev/null +++ b/bcc-bruce/misc/test/sort.t @@ -0,0 +1,104 @@ +unsigned t[10000]; +unsigned s[10000]; +unsigned size,repet; +unsigned comp=0,swap=0; /* s.b. long */ + +main(argc) +{ + int i,zz; + +/* + printf("size?"); + scanf("%d",&size); + printf("repet?"); + scanf("%d",&repet); +*/ + if ( argc > 20 ) + { + printf( "usage: sort [args], where 500*argc is the array size\n" ); + exit( 1 ); + } + size = 500 * argc; + repet = 1; + for (i = 0; i < size; i++) + s[i] = size-i; + printf("\npress key to begin shell sorting\n"); + getchar(); + for (zz=0;zz<repet;zz++) + { + comp=swap=0; + for (i=0;i<size;i++) + t[i]=s[i]; + sort(); + } + printf("\nsorted\n"); + printf("\ncompares = %d, swaps = %d\n",comp,swap); + printf("\npress key to begin quick sorting\n"); + getchar(); + for (zz=0;zz<repet;zz++) + { + comp=swap=0; + for (i=0;i<size;i++) + t[i]=s[i]; + qqsort(); + } + printf("\nsorted\n"); + printf("\ncompares = %d, swaps = %d\n",comp,swap); +} + +sort() +{ + int i,j,h,temp; + + h=1; + while (9*h+4<size) + h=3*h+1; + while (h>0) + { + for (j=h; j<size; j++) + for (i=j-h; i>=0; i-=h) + { + ++comp; + if (t[i]<=t[i+h]) + break; + ++swap; + temp=t[i]; + t[i]=t[i+h]; + t[i+h]=temp; + } + h=(h-1)/3; + } +} + +qqsort() +{ + qsort(0,size-1); +} + +qsort(l,r) +int l,r; +{ + int i,j; + unsigned x,w; + + i=l;j=r; + x=t[(l+r)>>1]; + do + { + while (t[i] < x) + { + ++comp; + i++; + } + while (x < t[j]) {--j;} + if (i<=j) + { + ++swap; + w=t[i];t[i]=t[j];t[j]=w; + i++;j--; + } + } + while (i<=j); + if (l<j) qsort(l,j); + if (i<r) qsort(i,r); +} |