Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024
Difficulty: Medium

Shell Sort Program in C

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

Sorting algorithms play a fundamental role in computer science, and Shell sort, named after its creator Donald Shell, is one of the powerful yet lesser-known members of this family. The unique "gap" strategy in Shell sort makes it distinct and more efficient in certain scenarios compared to its counterparts. 

shello sort program in C

Let's dive deep into this fascinating algorithm.

Understanding Shell Sort

Shell sort is an in-place comparison sort. It's a generalization of insertion sort that allows the exchange of elements that are far apart. The algorithm sorts elements at specific intervals and gradually reduces the interval to perform a final sort.

How Shell Sort Works

Imagine sorting an array as arranging a deck of cards. Instead of moving one card at a time, you divide the deck into smaller piles (gaps). You sort those smaller piles first, and then merge them together, making the task simpler and quicker.

In Shell sort, the original array is divided into smaller subarrays based on the gap. Elements at a specific gap are sorted first. This gap is then reduced, and the process is repeated until the gap becomes 1, leading to a completely sorted array.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Shell Sort Algorithm 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

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 - 


Check out the following problems - 

 

Refer to our guided paths on Coding Ninjas Studio 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.

Do upvote our blog to help other ninjas grow

Happy Reading!!‍
 

Topics covered
1.
Introduction
2.
Understanding Shell Sort
2.1.
How Shell Sort Works
3.
Shell Sort Algorithm in C
3.1.
Time and Space Complexity
4.
Frequently Asked Questions
4.1.
What is Shell Sort in C?
4.2.
How does Shell Sort work?
4.3.
What is the time complexity of Shell Sort?
5.
Conclusion