Shell Sort Algorithm in C | Shell Sort Program in C

What is Shell Sort?

Shell sort is a sorting algorithm called shell sort after the name of its inventor Donald Schell. Shellsort, also known as Shell sort or Shell’s method, is an in-place comparison sort. Shell sort algorithm is an improved version of the insertion sort algorithm but it can also be applied to bubble sort.

The method starts by sorting elements far apart from each other and progressively reducing the gap between them. Starting with far apart elements can move some out-of-place elements into position faster than a simple nearest neighbor exchange. This algorithm works very well for medium-sized arrays and even for an array with elements of higher magnitude, having elements up to a few thousand.

Problem Description

Write a C program to sort a given array of integer numbers using Shell Sort algorithm.

Shell Sort Algorithm:

1. We will store the random set of numbers in an array.
2. We will traverse this array and insert each element of this array, to its correct position where it should actually be, by shifting the other elements on the left if required.
3. The first element in the array is considered as sorted, even if it is an unsorted array. The array is sub-divided into smaller sub-part, each part must have equal intervals.
4. Sort the sub-lists using insertion sort algorithm.
5. This goes until the last element in list gets sorted and is placed in correct position in the output array.
6. Now, we have the array in sorted order.

Working of Shell Sort Algorithm:

Suppose we are given an array:

Given arr:

Index	0	1	2	3	4	5	6	7	8	9	10	11
Element	12	3	4	2	56	7	9	87	0	-2	12	-1

Shell sort use to do sort on an interval basic where at the first iteration of the array we sort the array that is at (size of array / 2) interval that is 12/2 = 6.

Step 1:
At first, the interval value is 6.
So, we take the first element and then increase the value of the interval till we reach the end of the array. We do the same iteratively till the subarrays are only of length

Subsists, that are formed at interval = 6 are,

{12,9}, {3,87}, {4,0}, {2,-2}, {56,12}, {7,-1}

Sort the list using insertion sort then the result will be:

Subscribe Now: C Algorithms Newsletter | Important Subjects Newsletters

Index	0	1	2	3	4	5	6	7	8	9	10	11
Element	9	3	0	-2	12	-1	12	87	4	2	56	7

Step 2:
Now we divide the value of the interval by 2. This will give us the value = 3.
Now we will take intervals of 3.

Subsequences are formed by taking the interval value = 3.

{9, -2, 12, 2} , {3, 12, 87, 56}, {0, -1, 4, 7}

We compare values in each subsequence and swap them (if necessary) in the original array. After this step, the new array should look like this −>

{-2, 2, 9 , 12}, {3, 12, 56, 87}, {-1, 0, 4, 7}

Index	0	1	2	3	4	5	6	7	8	9	10	11
Element	-2	3	-1	2	12	0	9	56	4	12	87	7

Step 3:
Now we sort the whole array using insertion sort using the interval = 1.

As we know that in insertion sort we find the minimum element from the unsorted list and place it at the rightmost index of the sorted list we do this by taking the interval value = 1.
After the process, we get the array as

Index	0	1	2	3	4	5	6	7	8	9	10	11
Element	-2	-1	0	2	3	4	7	9	12	12	56	87

Problem Solution

There are several ways to write an shell sort program in C language. Let’s discuss all the ways in detail.

Shell Sort Program using Pointers
Shell Sort Program using Simple Approach

Method 1: Shell Sort Program using Pointers

In this approach we simply traverse the array and by using a loop, we insert each element to its correct place and finally print the sorted array using shell sort.

Program/Source Code

Here is the source code of the C program to sort integers using Shell Sort algorithm. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/* 
```

 * C Program to sort an array in ascending order using Shell Sort

```
 */
```
```
 
```
```
#include <stdio.h>
```
```
void swap(int *a, int *b)
```
```
{
```
```
    *a=*a + *b;
```
```
    *b=*a - *b;
```
```
    *a=*a - *b;
```
```
    return ;
```
```
}
```
```
 
```

// Function definition of sort array using shell sort

```
void shellsort(int arr[], int nums)
```
```
{
```
```
    // i -> gap/interval
```

    for (int i = nums / 2; i > 0; i = i / 2)

```
    {
```

        // Traverse j till we reach the end of the sublist.

```
        for (int j = i; j < nums; j++)
```
```
        {
```

            for(int k = j - i; k >= 0; k = k - i)

```
            {
```
```
                if (arr[k+i] >= arr[k])
```
```
                {
```
```
                    break;
```
```
                }
```
```
                else
```
```
                {
```

                    swap(&arr[k], &arr[k+i]);

```
                }
```
```
            }
```
```
        }
```
```
    }
```
```
    return ;
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int nums;
```

    printf("Enter total no. of elements :: ");

```
    scanf("%d", &nums);
```
```
    int arr[nums];
```
```
    printf("Enter the array:: \n");
```
```
    //scan the array elements.
```
```
    for (int k =  0 ; k < nums; k++)
```
```
    {
```
```
                scanf("%d", &arr[k]);
```
```
    }
```
```
 
```

    //Call the function of shell sort, bypassing the array base pointer to the first element.

```
    shellsort(arr, nums);
```
```
 
```
```
    // After the sorting the array is
```
```
    printf("Sorted array is:  \n");
```
```
    for (int k = 0; k < nums; k++)
```
```
    {
```
```
        printf("%d ", arr[k]);
```
```
    }	
```
```
    return 0;
```
```
}
```

Program Explanation

1. First ask the user to input the size of the array.
2. Then ask the user to input individual array elements.
3. Next call the shell sort function by passing the pointer to the first element in the array and the size of the array.
4. In the shell sort there is a loop that runs log(size) times as we initialize ‘i’ to size/2 and in the next iteration we just keep on dividing ‘i’ by 2 till we reach the condition where ‘i’ is smaller than 1.
5. ‘i’ variable corresponds to the interval at which the sub-lists lie.
6. Use the insertion sort algorithm in this loop to sort the sub-list.
7. When the loop stops our list gets sorted.

Time Complexity:

Worst Case Time Complexity: O(n²)
Best Case Complexity: O(nlog(n))

O(n²) is the time complexity we get in the shell sort algorithm but depending on the interval and the no of the already sorted position of elements the complexity can be decreased up to O(n* (log n))

Space Complexity: O(1)
Because it is an in-place sorting algorithm, the space required is constant i.e. O(1).

Runtime Test Cases

Here’s the run time test cases for Shell sort algorithm for 2 different input cases.

Test Case 1 – Average Case: The elements are entered in random order and then sorted in ascending order using shell sort technique.

/* Average case */
 
Enter total no. of elements:: 12
Enter the array::
12 3 4 2 56 7 9 87 0 -2 12 -1
The sorted array is:
-2 -1 0 2 3 4 7 9 12 12 56 87

Test Case 2 – Worst Case: Here, the elements are reverse sorted.

/* Worst case */
 
Enter number of elements
7
Enter 5 integers
12 9 7 5 3 1 0
Sorted list in ascending order:
0
1
3
5
7
9
12

Method 2: Shell Sort Program using Simple Approach

In this approach we sort the integers using Shell Sort technique.

Program/Source Code

Here is the source code of the C program to sort integers using Shell Sort technique. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * C Program to sort an array using Shell Sort technique

```
 */
```
```
 
```
```
#include <stdio.h>
```
```
void shellsort(int arr[], int num)
```
```
{
```
```
    int i, j, k, tmp;
```
```
    for (i = num / 2; i > 0; i = i / 2)
```
```
    {
```
```
        for (j = i; j < num; j++)
```
```
        {
```

            for(k = j - i; k >= 0; k = k - i)

```
            {
```
```
                if (arr[k+i] >= arr[k])
```
```
                    break;
```
```
                else
```
```
                {
```
```
                    tmp = arr[k];
```
```
                    arr[k] = arr[k+i];
```
```
                    arr[k+i] = tmp;
```
```
                }
```
```
            }
```
```
        }
```
```
    }
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int arr[30];
```
```
    int k,  num;
```

    printf("Enter total no. of elements : ");

```
    scanf("%d", &num);
```

    printf("\nEnter %d numbers: ", num);

```
 
```
```
    for (k =  0 ; k < num; k++)
```
```
    {
```
```
        scanf("%d", &arr[k]);
```
```
    }
```
```
    shellsort(arr, num);
```
```
    printf("\n Sorted array is: ");
```
```
    for (k = 0; k < num; k++)
```
```
        printf("%d ", arr[k]);
```
```
    return 0;
```
```
}
```

Program Explanation

1. Using a for loop, we are reading n elements from standard input into an array named arr
2. Next, we are comparing elements of the array so that we can insert them in the proper position using the shell sort method.
3. The array is sub-divided into smaller sub-part, each part must have equal intervals. Sort the sub-lists using insertion sort algorithm.
4. It goes until the last element in list gets sorted and is placed in correct position in the output array.
5. At the end, we are printing/displaying the sorted array.

Time Complexity:

Worst Case Time Complexity: O(n²)
Best Case Complexity: O(nlog(n))

Space Complexity: O(1)
Because it is an in-place sorting algorithm, the space required is constant i.e. O(1).

Program Output:

In this case the elements are entered in random order and then sorted in ascending order using shell sort technique.

Enter total no. of elements : 10
Enter numbers : 36 432 43 44 57 63  94 3 5 6
Sorted array is : 3 5 6 36 43 44 57 63 94 432

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Perform Optimal Parenthesize using Dynamic Programming

» Next - C Program to Perform Searching using Self-Organizing Lists

Related Posts:

Recommended Articles: