1 files changed, 104 insertions, 0 deletions
diff --git a/bcc/misc/test/sort.t b/bcc/misc/test/sort.t
new file mode 100644
index 0000000..34bcb9e
--- /dev/null
+++ b/bcc/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);
+}