1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
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);
}
|
