Shell Sort Program in C

Algorithm of Shell sort

Shell Sort is an extension of Insertion Sort that sorts elements separated by a gap, reducing the gap until it becomes 1. This method improves efficiency by moving out-of-place elements closer to their correct position early on.

1. Initialize Gap: Start with a gap size, typically half the length of the list (gap = n/2).
2. Gap Reduction: Repeat until the gap reduces to 1 by halving it after each pass.
3. Sort with Gap: For each gap:
   • Perform an insertion sort for elements separated by the gap.
   • Iterate through the list, comparing elements that are gap positions apart.
   • Swap if necessary to ensure elements are ordered according to the current gap.
4. Continue Until Sorted: Reduce the gap and repeat until no swaps are needed, resulting in a fully sorted array.

Working on Shell Sort Program in C

Consider sorting this array: [8, 5, 3, 6, 9, 2]

Step 1: Initial Array

• Array: [8, 5, 3, 6, 9, 2]
• n: Length of the array = 6

Step 2: First Gap (n/2 = 3)

• Gap = 3
• We will sort elements separated by a gap of 3.

1. Compare 8 and 6 (gap of 3): Swap them.
   Result: [6, 5, 3, 8, 9, 2]
2. Compare 3 and 2 (gap of 3): Swap them.
   Result: [6, 5, 2, 8, 9, 3]

Step 3: Reduce Gap (3/2 = 1.5, rounded to 1)

• Gap = 1
• Now, perform a regular insertion sort with a gap of 1.

1. Compare 6 and 5: Swap them.
   Result: [5, 6, 2, 8, 9, 3]
2. Compare 6 and 2: Swap them.
   Result: [5, 2, 6, 8, 9, 3]
3. Continue insertion sort until all elements are in order:
   Result: [2, 3, 5, 6, 8, 9]

Final Sorted Array:

• Sorted Array: [2, 3, 5, 6, 8, 9]

Implementation of Short Shell in C

Here's the basic structure of a Shell sort implementation in C:

#include <stdio.h>
 
void shellSort(int array[], int n) {
  for (int gap = n/2; gap > 0; gap /= 2) {
    for (int i = gap; i < n; i += 1) {
      int temp = array[i];
      int j;           
      for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
        array[j] = array[j - gap];
      }
      array[j] = temp;
    } 
  } 
}

In this code snippet, the outer loop controls the gap size, which starts from n/2 and reduces by half each time. The second loop iterates over the elements in the subarrays. The third loop compares the elements and swaps them if they're in the wrong order.

Time and Space Complexity

Shell sort has a worst-case and average time complexity of O(n^2), where n is the number of elements. However, with an optimal choice of gaps, it can perform considerably better. Its best-case complexity is O(n*log(n)).

As for space complexity, since it's an in-place sorting algorithm, its space complexity is O(1).

Also read, Bit stuffing program in c

Applications of Shell Sort

1. Medium-Sized Data Sets: Efficient for sorting medium-sized arrays where a full O(n²) sort would be slow, but a full O(n log n) sort might be unnecessary.
2. Embedded Systems: Due to its low overhead and simple code structure, Shell Sort is used in memory-constrained embedded systems.
3. Partially Sorted Data: Performs well on data that’s already partially sorted, requiring fewer passes and swaps compared to other algorithms.
4. Array-Based Lists: Commonly used for sorting lists that are implemented as arrays, as it works in-place without needing extra memory for another array.
5. Real-Time Applications: Useful in applications needing relatively quick, approximate sorts without the strict requirements of an exact O(n log n) sort

Frequently Asked Questions

What is Shell Sort in C?

Shell sort is an algorithm that sorts elements in specific intervals, gradually reducing the interval until the array is completely sorted.

How does Shell Sort work?

Shell sort works by sorting elements at specific 'gap' intervals, reducing the gap until the array is sorted.

What is the time complexity of Shell Sort?

The worst-case and average time complexity of Shell Sort is O(n^2), but with the optimal gap, it can perform at O(n*log(n)).

Conclusion

Shell sort stands as an interesting algorithm that generalizes insertion sort to improve efficiency. While it might not be the first choice for large datasets due to its average and worst-case time complexity, its unique approach makes it an important concept for every budding programmer. It's yet another proof that in computer science, there's always more than one way to sort a list.

Check out these useful blogs on - 

• Compilation process of a C program
• Conditional Operator in C
• Introduction to C
• Getch in C
• Call by value & call by reference in C
• Ternary Operator in C
• Bubble Sort Program in C
• odd or even program in c

Check out the following problems - 

• Sum Of Two Arrays.
• Merge K Sorted Arrays.
• Intersection Of Two Arrays.

Refer to our guided paths on Code360 to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available, interview puzzles, take a look at the interview experiences, and interview bundle for placement preparations.