**Shell Sort Technique In C++: A Complete Overview.**

Shell sort is often termed as an improvement over insertion sort. In insertion sort, we take increments by 1 to compare elements and put them in their proper position.

In shell sort, the list is sorted by breaking it down into a number of smaller sublists. It’s not necessary that the lists need to be with contiguous elements. Instead, shell sort technique uses increment i, which is also called “gap” and uses it to create a list of elements that are “i” elements apart.

**=> See Here To Explore The Full C++ Tutorials list.**

What You Will Learn:

### General Algorithm

**The general algorithm for shell sort is given below.**

shell_sort (A, N)

where A – list to be sorted; N – gap_size

set gap_size = N, flag = 1

while gap_size > 1 or flag = 1, repeat

begin

set flag = 0

set gap_size = (gap_size + 1)/2

end

for i = 0 to i< (N-gap_size) repeat

begin

if A[i + gap_size] > A[i]

swap A[i + gap_size], A[i]

set flag = 0

end

end

Thus in the above algorithm, we first set N which is the gap for sorting the array A using shell sort. In the next step, we divide the array into sub-arrays by using the gap. Then in the next step, we sort each of the sub-arrays so that at the end of the loop we will get a sorted array.

Next, let us consider a detailed example to better understand the shell sort using a pictorial representation.

### Illustration

**Let us illustrate the Shell sort with an Example.**

Consider the following array of 10 elements.

If we provide a gap of 3, then we will have the following sub-lists with each element that is 3 elements apart. We then sort these three sublists.

The sorted sub-lists and the resultant list that we obtain after combining the three sorted sublists are shown below.

The above array that we have obtained after merging the sorted subarrays is nearly sorted. Now we can perform insertion sort on this list and sort the entire array. This final step is shown below for your reference.

As seen above, after performing shell sort and merging the sorted sublists, we only required three moves to completely sort the list. Thus we can see that we can significantly reduce the number of steps required to sort the array.

The choice of increment to create sub-lists is a unique feature of shell sort.

### C++ Example

**Let us see the implementation of shell sort in C++ below.**

#include <iostream> using namespace std; // shellsort implementation int shellSort(int arr[], int N) { for (int gap = N/2; gap > 0; gap /= 2) { for (int i = gap; i < N; i += 1) { //sort sub lists created by applying gap int temp = arr[i]; int j; for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) arr[j] = arr[j - gap]; arr[j] = temp; } } return 0; } int main() { int arr[] = {45,23,53,43,18,24,8,95,101}, i; //Calculate size of array int N = sizeof(arr)/sizeof(arr[0]); cout << "Array to be sorted: \n"; for (int i=0; i<N; i++) cout << arr[i] << " "; shellSort(arr, N); cout << "\nArray after shell sort: \n"; for (int i=0; i<N; i++) cout << arr[i] << " "; return 0; }

**Output:**

Array to be sorted:

45 23 53 43 18 24 8 95 101

Array after shell sort:

8 18 23 24 43 45 53 95 101

We have used the same list that we used in the illustration and we can see that we begin initially by creating two sub-lists and then narrowing the gap further. Once sub lists are created as per the gap specified, we sort each of the sub lists. After all the sub lists are sorted, we get the almost sorted list. Now this list can be sorted using the basic insertion sort which will take very few moves.

Next, let us implement shell sort using Java language.

### Java Example

// Java class for ShellSort class ShellSort { //function to sort the array using shell sort int sort(int arr[]) { int N = arr.length; // Start with a big gap, then narrow the gap for (int gap = N/2; gap > 0; gap /= 2) { //sort sub lists created by applying gap for (int i = gap; i < N; i += 1) { int temp = arr[i]; int j; for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) arr[j] = arr[j - gap]; arr[j] = temp; } } return 0; } } class Main{ public static void main(String args[]) { int arr[] = {45,23,53,43,18,24,8,95,101}; int N = arr.length; System.out.println("Array to be sorted: "); for (int i=0; i<N; ++i) System.out.print(arr[i] + " "); System.out.println(); ShellSort ob = new ShellSort(); ob.sort(arr); System.out.println(""Array after shell sort: "); for (int i=0; i<N; ++i) System.out.print(arr[i] + " "); System.out.println(); } }

**Output:**

Array to be sorted:

45 23 53 43 18 24 8 95 101

Array after shell sort:

8 18 23 24 43 45 53 95 101

We have implemented the same logic for shell sort in both C++ and Java programs. Thus as explained above in the Java program, we first divide the array into subarrays and then sort them to obtain a complete sorted array.

### Conclusion

Shell sort is the highly efficient algorithm that comes to an improvement over the insertion sort.

While insertion sort works by incrementing its elements by 1, shell sort uses the parameter “gap” to divide the array into sub-arrays whose elements are “gap” apart. Then we can sort the individual list using insertion sort to obtain the complete sorted array.

Shell sort performs faster than insertion sort and takes fewer moves to sort the array when compared to insertion sort. Our upcoming tutorial will explore all about the heap sort technique for sorting data structures.