Shell Sort

Here, We will discuss about Shell Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications.

What is Shell Sort?

Shell Sort also called diminishing increment sort. This sorting algorithm is a generalization of insertion sort.

Shell sort is efficient for medium size lists. For bigger lists, the algorithm is not the best choice. It is the fastest of all O(n2) sorting algorithms.

Shell sort is also known as n-gap insertion sort.

The algorithm based on the idea that sort the elements far apart from each other and successively reduces the interval between the elements to be sorted.

SHELL SORT

Shell Sort Implementation

Program code in C

//Shell sort in C programming #include<stdio.h> //shell sort void shellsort(int arr[], int n) { for(int interval=n/2; interval>0; interval/=2) { for(int i=interval; i<n; i+=1) { int temp = arr[i]; int j; for(j=i; j>=interval && arr[j-interval] > temp; j-=interval) { arr[j] = arr[j-interval]; } arr[j] = temp; } } } //print an array void printarray(int arr[], int n) { for(int i=0; i<n; i++) { printf("%d ",arr[i]); } printf("\n"); } //Driver Code int main() { int data[] = {8, 4, 35, 12, 1}; int size = sizeof(data) / sizeof(data[0]); shellsort(data, size); printf("Sorted array: "); printarray(data, size); }
Code language: C++ (cpp)

Output:

Sorted array : 1 4 8 12 35
Code language: PHP (php)

Time and Space Complexity of Shell Sort

Time Complexity
Worst CaseO(n log2n)
Best CaseO(n)
Average Casedepend on gap sequence
Space Complexity
Worst CaseO(n)

Applications of Shell Sort

Shell Sort is used when:

  1. calling a stack is overhead. uClibc library uses this sort.
  2. recursion exceeds a limit. bzip2 compressor uses it.

Heap Sort

Here, We will discuss about Heap Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications. What …
Read More

Bubble Sort

Here, We will learn about bubble sort in C, their algorithm, implementation in C, time & space complexity and their applications. What is Bubble Sort? Bubble Sort …
Read More

Counting Sort

Here, We will discuss about Counting Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications. What is Counting …
Read More

Selection Sort

Here, We will discuss about selection sort in C, their algorithm, implementation code in C, time and space complexity and their advantages. What is Selection Sort? Selection …
Read More

Quick Sort

Here, We will discuss about Quick sort in C, their algorithm, implementation in C, time & space complexity and their applications. What is Quick Sort? Quick …
Read More

Bucket Sort

Here, We will discuss about Bucket Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications. …
Read More

Want to Contribute:-

If you like “To The Innovation” and want to contribute, you can mail your articles to 📧 contribute@totheinnovation.com. See your articles on the main page and help other coders.😎

Leave a Comment

Your email address will not be published.