/*
Shell Sort.
*/
#include <stdio.h>
#define true 1 /* Constant declaration */
#define false 0
typedef int listarray[1000]; /* Variable
type declaration */
listarray list; /* Global variable declaration */
int ncomp, nswap, n, i;
void swap(int *k, int *l) /* Swap function declaration */
{
int temp;
temp = *k;
*k = *l;
*l = temp;
} /* End swap function */
void shell(int *list, int n) /* Shell subroutine declaration */
{
int m, i, j;
int done;
ncomp = 0;
nswap = 0;
m = n;
do
{
m = (m + 2) / 3;
for (i = m + 1; i <= n; i++)
{
j = i;
done = false;
while (j > m && !done) {
ncomp++;
if (list[j - m - 1] < list[j - 1]) done = true;
else
{
swap(&list[j - 1], &list[j - m - 1]); /* Call of Swap function */
nswap++;
}
j -= m;
}
}
}while(m > 1);
}
main()
{
/* Declaration Statements */
int n;
int list[100];
int FORLIM;
clrscr();
printf("C95.C -> Shell sort
program\n");
/* Assignment Statements */
printf("Enter the number of elements: ");
scanf("%hd", &n);
FORLIM = n;
printf("Enter elements (press
""enter"" between each entry)\n");
for (i = 1; i <= FORLIM; i++)
{
printf("Enter element %d: ",i);
scanf("%hd", &list[i - 1]);
}
printf("\n\nBefore Sorting\n\n");
/* Print out initial array */
for (i = 1; i <= FORLIM; i++) printf("%5d", list[i - 1]);
printf("\n\n");
/* Sort with subroutines */
shell(list, n); /* Call of shell
subroutine */
/* Print out sorted array */
printf("\nAfter Sorting\n\n");
for (i = 1; i <= FORLIM; i++) printf("%5d", list[i - 1]);
printf("\n\nNumber of comparisons=%3d\n", ncomp);
printf("Number of exchanges=%3d\n\n\n",
nswap);
return(0);
}
/* End of main Program C95 */
/*
Input :
7
59
72
41
16
27
17
11
Output :
C95.C -> Shell sort program
Enter Number of Elements : 7
Enter elements (press enter between each entry)
Element 1 : 59
Element 2 : 72
Element 3 : 41
Element 4 : 16
Element 5 : 27
Element 6 : 17
Element 7 : 11
Press Enter to continue...
Before Sorting
59 72 41 16 27 17 11
After Sorting
11 16 17 27 41 59 72
Number of comparisons= 16
Number of exchanges= 10
*/