Shell Sort Program in C

Introduction

In shell sort, an array is made h-sorted for a large value of h. The value of h is kept reducing until it becomes 1. If all sublists of each and every h’th element are sorted then the array is said to be h-sorted.

It overcomes the drawback of the Insertion sort. For elements that are far away, it allows movement as well as the swapping of elements. Due to this, it is efficient for medium-sized data.

The algorithm first sorts the elements that are far away and then subsequently reduces the gap between the elements. This gap is also known as intervals which can be calculated by using the given formula:

Knuth's formula: $k = h * 3 + 1$ where h is the interval having an initial value of 1.

Algorithm of Shell sort

• Start
• Initialize the value of h, i.e gap size
• Divide the given list into smaller sub-lists, each having equal intervals of h
• Sort the sub-lists using an insertion sort
• Repeat the above points until the list is sorted
• Print the sorted list
• End

Working on Shell Sort Program in C

In order to understand the working of the shell sort algorithm, let's take an example of an unsorted array. For intervals, the original sequence of shell sort should be used: $N/2, N/4,....,1$ When we iterate over the array for the first time, then the size of the array, which is n is equal to 8. Hence, the elements have an interval of 4, because ($n/2=4$). At each of these steps, the elements will be compared and swapped if not in the correct order. Therefore, when the loop is executed for the first time, the element at the 0th index will be compared to the element at the 4th index. If the element at the 0th index is greater than that of the 4th index, then the elements will be swapped, else it will remain at the same position. This will continue till the last element.

The sub-lists after interval 4 are, [31, 17], [8, 42], [33, 12], [40, 25] The next step after this is to compare elements of the sub-list and swap if required. After this step, the array would look something like this:

Now for sorting the remaining half of the array, the interval of 2 will be taken which will generate sub-lists as follows:

Now again after comparing values in each sub-list, the values will be swapped if required.

Now at the 3rd iteration, the interval will be taken of 1 for sorting the array. For this step, the shell sort uses insertion sort for sorting the array.

This is how the array is sorted.

Examples/Application for Shell Sort Program

• Replacement of insertion sort
• Used for calling the stack overhead
• Used for sorting medium to a large-size arrays of the dataset
• Used for reducing the number of operations performed

Implementation of Shell Sort Program in C

Pseudocode

Explanation:

1. Function of shell sort which takes array and value of n
2. While the gap is less than 1/3rd of array's length-> do $GAP = ( INTERVAL * 3 ) + 1$
3. Iterate through for loop and insert the value at the correct position
4. Iterate through for loop again and check whether the element is at the correct position or not
5. If not, then replace the element with the correct element

Code

Output

Complexity of Selection Sort in C

Time complexity The time complexity of shell sort is $O(n²)$ because the gap in every iteration is reduced to half. Worst Case Complexity & Best Case Complexity The worst-case complexity for shell sort is $O(n²)$ and the best-case complexity is Ω($n log(n)$) since the array is sorted in this case and a number of comparisons is equal to the number of elements in it.

Space Complexity The space complexity of the shell sort is $O(1)$ since an extra space is used for sub-lists.