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.
Table of Contents:
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.
=> Visit Here To Learn C++ From Scratch.