Question

The shellsort algorithm is described in detail in the Topic 4 lecture slides, as well as Wikipedia (https://en.wikipedia.org/wiki/Shellsort).

Write a function in C which implements the shell sort algorithm. The recommended approach is to create an array of sub arrays using dynamic memory allocation, sort those sub-arrays, and replace them in the array. This is achievable through the use of double pointers. The following may be helpful: https://www.geeksforgeeks.org/dynamically-allocate-2d-array-c/

Inputs:

• array -> a pointer to the integer array to be sorted
• size -> the size of the array to be sorted
• h_gaps -> a pointer to an integer array of h gaps, in descending order.
• subsort -> a function pointer to the sub-sorting algorithm to be used by shellsort.

Outputs:

• Explicit -> the number of swaps performed. You may assume the subsort function returns this information.
• Implicit -> The array pointed to by array should be sorted when you are finished.

NOTES:

• Remember to start at the first h_gap which is at most half the length of the array.
• Assume that 1 is the last element in the array of h gaps.
• Remember that singleton lists are already sorted!
• If at any point a memory allocation operation fails, immediately have shellsort return a value of -1.

Test Case 1:

• unsorted -> {44, 79, 8, 53, 93, 21, 70, 79, 82, 49, 25, 2, 62, 26, 29, 54, 89, 57, 74, 39}
• sorted -> {2, 8, 21, 25, 26, 29, 39, 44, 49, 53, 54, 57, 62, 70, 74, 79, 79, 82, 89, 93}
• output -> 39

Test Case 2:

• unsorted -> {135, 529, 81, 54, 46, 605, 47, 793, 278, 323, 306, 430, 973, 286, 712, 962, 461, 81, 57, 325, 711, 995, 833, 222, 284, 293, 153, 224, 126, 643, 425, 400, 420, 309, 831, 6, 496, 347, 185, 583}
• sorted -> {6, 46, 47, 54, 57, 81, 81, 126, 135, 153, 185, 222, 224, 278, 284, 286, 293, 306, 309, 323, 325, 347, 400, 420, 425, 430, 461, 496, 529, 583, 605, 643, 711, 712, 793, 831, 833, 962, 973, 995}
• output -> 103

Answer 1

#include <stdio.h>
void shell_sort(int a[], int n);
int main()
{
int a[15], n, i;

printf ("enter no. of elements to be inserted:");
scanf("%d", &n); //1. Enter value of n

for (i=0;i<n;i++)
{
printf ("\nenter the element:");
//2. Enter n elements

scanf ("%d", &a[i]);
}
shell_sort(a, n);
printf("\nthe sorted list is:");
for(i=0;i<n;i++)
printf("%d\t", a[i]);

return 0;
}
void shell_sort(int a[], int n)
{
int i,j, k, temp,count;

for (i=n/2;i>0;i=i/2)
{
for (j=i;j<n;j++)
{
for (k=j-i;k>=0;k--)
{
if(a[k+i]<a[k])
{
count++;
temp =a[k+i];
a[k+i]=a[k];
a[k]=temp;
}
}
}

}
printf ("Output is%d\n",count);

}