/*

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

*/