In this section of the tutorial, we will discuss the Shell Sort in Data Structure and its concept and the algorithm of Shell sort for performing different sorting operations in detail.

Now let’s move further to the introduction of Shell Sort in Data Structure.

What is Shell Sort in Data Structure?

Shell Sort is another version of Insertion Sort, named after the person who created its algorithm, Donald L. Shell.  Shell Sort Algorithm was first published in Communication of ACM in the year 1959.

• In Shell Sort, a list of data values are diminished into multiple segments and eventually used for sorting the data.
• A list of X elements is divided into multiple N number of smaller segments, where N is known as increment.
• In each segment, there lies a minimum of integral X/N, and if X/F is not integral, some of the segments will hold extra elements.

Further, we will discuss the concepts of Shell Sort and the algorithm of Shell Sort which helps in sorting a pool of unordered data elements.

Concept used in Shell Sort

The core concept used in creating the algorithm for Shell Sort is somewhat similar to the concept of Insertion Sort. Shell Sort breaks down the list of elements into multiple smaller segments, each of which is later sorted using Insertion Sort technique and finally all together sorts the entire list in a sequenced form.

We will look into an illustrated example to understand the concepts involved in Shell Sort.

• Here, the segments are dispersed throughout the list.
• When the increment is 3, the first, fourth, seventh, and tenth elements make up segment 1.
• Similarly, the second, fifth, and eighth element make up segment 2.
• Similarly, the third, sixth, and ninth element make up segment 3.
• After each sort pass, the data in each smaller segment is sorted using the same Insertion Sort technique.
• So, for three segments, there are three different ordered lists. And for two segments, there are two different sorted lists. And when there is only one segment, the list becomes sorted.

Shell Sort Algorithm

Now that we are familiar with the concept of Shell Sort, we can now develop an algorithm before we put it into implementation.

Algorithm Shell_Sort (list, last)
1 set Increm to last / 2
2 loop (Increm not 0)
    1 set current to Increm
    2 loop (until last element sorted)
        1 move current element to hold
        2 set walker to current - Increm
        3 loop (walker >= 0 AND hold key < walker key)
            1 move walker element one Increment right
            2 set walker to walker - Increm
        4 end loop
        5 move hold to walker + Increm element
        6 Increment current
    3 end loop
    4 set Increm to Increm / 2
3 end loop
end Shell_Sort

• Here, data present in the array list are sorted in place.
• Post sorting, their keys will be in order, list[0] <= list[1] <= … <= list[last].
• list specifies an unordered array of data values.
• last specifies index value to last record in array.
• After sorting, list becomes ordered on list[i].key.
• The loop moves larger element up the list and then fall back one partition.
• After the loop breaks, the data on hold is inserted in a location while maintaining a sequence.
• This concludes the first sort pass, then the next increment continues and following the next sort passes.

Working of Shell Sort

The working of shell sort is halfway understood by the algorithm we wrote above, now we will look into an example to understand it more clearly.

• In Shell Sort, each sort pass starts with the first element in the array and goes up to the last element in the array, while comparing adjacent elements in each segment.
• When comparing the adjacent elements(keys) in a segment, we add the increment to the current index value, list [current] : list[current+increment].
• After each sort pass, the increment value is decreased until it becomes 1 and reaches the last element.
• The size of the increments defines the efficiency of the sorting technique.

• Here, after each sort pass, the elements present in each smaller segment becomes ordered.
• We reduce the increment back to one and test the adjacent elements to ensure that the previous segment is ordered at the end of each sort pass.
• In case they are found to be not in sequence, we exchange them and reduce the increment again.
• When necessary, we keep exchanging and reducing the increment until we find two elements are ordered.
• Eventually, all the elements are sorted in the list.

Time and Space Complexity of Algorithm

The complexity analysis largely depends upon the gap sequence used in the algorithm in solving a problem. However, the common complexities are given below based on the most commonly used shell sort algorithm.

Shell Sort Implementation

Now that we understand the concept of Shell Sort and also we have written the algorithm of Shell Sort, now we can implement Shell Sort in a programming language to perform the operation. Here, we will implement the Shell Sort in C and C++.

Implementation in C

Code:

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
void ShellSort(char *, int);
int main()
{
 char string[300];
 printf("Enter a string to be sorted:");
 gets(string);
 ShellSort(string, strlen(string));
 printf("Sorted String: %s", string);
 return 0;
}
void ShellSort(char *chars, int c)
{
 int i, j, incre, k;
 char x, a[5];
 a[0]=9; a[1]=5; a[2]=3; a[3]=2; a[4]=1;
 for(k=0; k < 5; k++)
 {
  incre = a[k];
  for(i=incre; i < c; ++i)
  {
   x = chars[i];
   for(j=i-incre; (x < chars[j]) && (j >= 0); j=j-incre)
    chars[j+incre] = chars[j];
   chars[j+incre] = x;
  }
 }
}

Output:

Enter a string to be sorted: CODEDEC
Sorted String: CCDDEEO

Implementation in C++

Code:

#include <iostream>
#include<cstring>
using namespace std;
void ShellSort(char *, int);
int main()
{
 char string[300];
 cout << "Enter a string to be sorted: ";
 gets(string);
 ShellSort(string, strlen(string));
 cout<<"Sorted String: "<< string;
 return 0;
}
void ShellSort(char *chars, int c)
{
 int i, j, incre, k;
 char x, a[5];
 a[0]=9; a[1]=5; a[2]=3; a[3]=2; a[4]=1;
 for(k=0; k < 5; k++)
 {
  incre = a[k];
  for(i=incre; i < c; ++i)
  {
   x = chars[i];
   for(j=i-incre; (x < chars[j]) && (j >= 0); j=j-incre)
    chars[j+incre] = chars[j];
   chars[j+incre] = x;
  }
 }
}

Output:

Enter a string to be sorted: CODEDEC                                                                                                          
Sorted String: CCDDEEO

In the next section of the tutorial, we will discuss the Selection Sort in Data Structure and its concept and the algorithm of Selection Sort for performing different sorting operations in detail. We shall discuss the algorithm and working principle in the same way as done in this article using real-world examples.