The topic of sorting algorithms is a crucial one for software engineers, especially if you are preparing for a coding interview. During tech interviews, you will face many challenging problems that will put your data structure and algorithms knowledge to test. Sorting algorithms are the key to solving many such problems.
In this article, we’ll go over the shell sort algorithm. We’ll cover:
What Is Shell Sort?
How Does Shell Sort Work?
Shell Sort Algorithm
Shell Sort Pseudocode
Shell Sort Code
Shell Sort Complexities
Advantages of Shell Sort
Disadvantages of Shell Sort
FAQs on Shell Sort
What Is Shell Sort?
Shell sort algorithm is a generalization of insertion sort, which uses the fact that insertion sort works efficiently on an input that is already almost sorted. It improves insertion sort by comparing and exchanging elements that are far apart.
In short, shell sort works by sorting elements at a specific interval using insertion sort. The interval between the elements is gradually decreased based on the increment sequence used. Shell sort’s performance also depends on the type of sequence used. (We’ll talk about these sequences shortly!)
The last step of shell sort is the same as insertion sort, but the elements are already almost sorted by then.
Real-World Applications of Shell Sort
Following are some of the applications of the shell sort algorithm:
Shell sort is used in the Linux kernel because it does not use a call stack.
uClibc library uses Shell sort.
Shell sort is used in the bzip2 compressor to avoid problems that could come when sorting algorithms exceed a language’s recursion depth.
How Does Shell Sort Work?
Let’s assume that the array Arr[] = {12, 17, 4, 9, 3, 6, 13, 1} is to be sorted.
We’ll use the sequence (N/2, N/4, ...1) as intervals in our algorithm.
Here, “interval” refers to the distance of index between two elements of an array that will be placed in the same sublist. By N/2, we mean floor(N/2). In our outer loop, we will iterate over the elements of the sequence we have chosen in decreasing order (here, our sequence is N/2, N/4, … 1) In the first iteration, the interval is N/2 = 4. So, in our inner loop, we sort all the sublists of every 4th element.
Now, in the second iteration, the interval is N/4 = 2 — we sort all sublists of every 2nd element:
Sublist 1: {3,4,12,13} Sublist 2: {6,1,17,9}
After sorting all sublists, we have:
Finally, in the third iteration, the interval is N/8 = 1. So, we perform insertion sort.
Sublist 1: {3, 1, 4, 6, 12, 9, 13, 17}
The result after sorting:
There are many increment sequences that can be used for shell sort, and as mentioned before, the time complexity of the process can vary based on the sequence chosen. Following are some of the increment sequences used in shell sort:
Step 1: Initialize h (interval) with N/2 and divide it by 2 in every iteration until it becomes 1. Step 2: Divide the array into smaller sub-lists of equal interval h. Step 3: Sort all sub-lists using insertion sort. Repeat Steps 2 and 3 until the array is sorted.
Shell Sort Pseudocode
Here's the pseudocode for shell sort. You can use as a reference this to code in any programming language you prefer.
h: interval
N: Size of array
for h from N/2 to 1, do
Put all the elements which are at the distance of h in a sublist
And sort all sublists using insertion sort.
return Arr
Shell Sort Code
We’ve used C++ to demonstrate how shell sort works. Use this as a reference to code in C, Java, Python, or any programming language of your choice.
#include
using namespace std;
void Shellsort(int Arr[], int N)
{
// Changing interval as (N/2, N/4 ... 1) sequence
for(int h = N / 2; h >= 1; h /= 2)
{
//sorting each sub-list using insertion sort
for(int i = h; i < N; i++)
{
int temp = Arr[i];
int j;
for(j = i; j >= h && Arr[j - h] > temp; j -= h)
Arr[j] = Arr[j - h];
Arr[j] = temp;
}
h /= 2;
}
}
int main()
{
const int N = 8;
int Arr[N] = {12, 17, 4, 9, 3, 6, 13, 1};
cout << "Unsorted array: ";
for (int i = 0; i < N ; i++)
cout << Arr[i] << " ";
cout << endl;
Shellsort(Arr, N);
cout << "Sorted Array: ";
for (int i = 0; i < N; i++)
cout << Arr[i] << " ";
cout << endl;
return 0;
}
Output:
Unsorted array: 12 17 4 9 3 6 13 1
Sorted Array: 1 3 4 6 9 12 13 17
Shell Sort Complexities
While the performance of shell sort depends on the sequence selected, let’s look at how our implementation does in terms of time and space complexity.
Time Complexity
The worst- and average-case time complexity of shell sort depends on the interval sequence — we choose the (N/2, N/4, ... 1) sequence. The time complexity of our implementation is O(N*N). This can be improved by choosing different sequences for reducing h (interval).
Let’s break down how we got O(N*N):
Consider an array where all the even-positioned elements are greater than the median. The odd and even elements are not compared until we reach the last increment of 1. The number of compare/exchanges needed for the last iteration is O(N*N). Therefore:
Worst-case time complexity: O(N*N)
Average-case time complexity: O(N*logN)
When the array is already sorted, the total number of comparisons for each interval is equal to the size of the array:
Best-case time complexity: O(N*logN)
Space Complexity
The auxiliary space complexity of shell sort is O(1).
Advantages of Shell Sort
Implementation is easy.
No stack call is required.
Shell sort is efficient when given data is already almost sorted.
Shell sort is an in-place sorting algorithm.
Disadvantages of Shell Sort
Shell sort is inefficient when the data is highly unsorted.
Shell sort is not efficient for large arrays.
Shell Sort vs. Quicksort
On average, quicksort performs better than shell sort; but shell sort is more efficient than quicksort when the given data is already/almost sorted.
Shell sort does not require stack calls, whereas quicksort does.
FAQs on Shell Sort
Question 1: What are the factors on which the time complexity of shell sort depends?
Answer:
Shell sort is an adaptive algorithm. Its time complexity depends on how sorted the given data is.
Shell sort’s performance also depends on the interval sequence we choose, such as Knuth’s increment sequence or Sedgewick's increment sequence.
Question 2: Is shell sort stable?
Answer: Although insertion sort is stable, shell sort is not. Moving the elements using intervals makes the shell sort unstable.
For example, consider an array Arr[] = {4, 2, 2, 5} Consider 0-based indexing.
Here, N/2 = 2.
So, we sort sublist {4, 2} and {2, 5}.
While sorting the first sublist {4, 2}, 4 and 2 will be swapped, and 2 (which was at index 2 initially) will move to index 0, and 2 (which was index 1 initially) will remain at its position. Therefore, shell sort is not stable.
Are You Ready to Nail Your Next Coding Interview?
Sorting algorithms interview questions feature in almost every coding interview for software developers. If you’re looking for guidance and help to nail these questions and more, sign up for our free webinar.
As pioneers in the field of technical interview prep, we have trained thousands of software engineers to crack the toughest coding interviews and land their dream jobs at Google, Facebook, Apple, Netflix, Amazon, and other Tier-1 tech companies.
.png)
