Updated April 10, 2023
Definition of Shell sort C++
Shell sort in C++ is defined as a sorting algorithm that allows users to sort arrays and puts the list in the prescribed order i.e. either in ascending or descending order and in another dimension. These prescribed orders can also be numerical or lexicographical orders. An efficient sorting algorithm is equally important as it paves the way for having an optimized efficiency of other related algorithms which use the sorting algorithms within its use cases and need sorted data as their needs! The shell sort is one type of sorting algorithm mainly a variation of insertion sort. The objective of insertion sort is to move elements only one position ahead! In this article, we will look at the variation and the working of shell sort in C++.
How shell sort works in C++?
When we talked about shell sort in the introduction, we learned that the algorithm is a generalized version of insertion sort. Now let us take a glance at the insertion sort first as the learning of the algorithm will pave the way for getting into the nitty-gritties of shell sort. In an insertion sort, the array is virtually split into a sorted part and the other is an unsorted path. Now, the values from the unsorted part is picked and correspondingly inserted in the correct position of the array. The unsorted part starts from the first element and at that time the sorted part is the nil and the unsorted is the original array. Now as the iteration progresses, each element of the array in the unsorted part is looked into one by one and then compared with respect to the predecessor. If the predecessor is smaller (or larger as per the requirement) it is then compared to the elements in the sorted array and then the correct position is determined and finally inserted there. In this way with each successive iteration, the sorted part gets bigger in size and the unsorted part reduces with finally the unsorted part being nil.
Now, for shell sort, we know that it is a generalized version of insertion sort, there are some sequences that are followed generally. In this article, we will focus on Shell’s original sequence keeping in mind the length of the article, but we would take this chance to look at all the sequences at a superficial level. The numbers mentioned for each sequence are the intervals in our algorithm. It will be clearer when we understand the working of shell sort step by step.
• Shell’s original sequence: N/2, N/4, …, 1
• Increments:
- Knuth’s: 1, 4, 13, …, (3k – 1) / 2
- Hibbard’s: 1, 3, 7, 15, 31, 63, 127, 255, 511…
- Papernov & Stasevich: 1, 3, 5, 9, 17, 33, 65…
- Sedgewick’s: 1, 8, 23, 77, 281, 1073, 4193, 16577…4j+1+ 3·2j+ 1
• Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81….
We should be aware that the sequences mentioned above are not exhaustive and are the optimal ones. Now, let us assume that there is an array given which needs sorting. Below are the steps followed in Shell’s original sequence (for sorting in ascending order).
1. The interval is taken as N/2, N/4, …, 1, where N is the array size.
2. In the first iteration, the elements present in the interval of N/2 are compared and swapped. For example, if the array size is 8, the 0th element is compared to 8/2 = 4th element. If the 4th element is smaller, we swap the places and if not, we don’t perform any action. This process goes on till we reach the end of the array.
3. In the next iteration, we will take the elements in the intervals of 8/4 = 2. At some point, one would visualize (in this example) that we compared 0 and 2nd, and then again 2nd and 4th, and that is the point of the shell sort.
4. Finally, the iterative process is completed till we reach the interval to be compared as 1.
5. The final array we get is the sorted one!
Examples
Let us discuss examples of Shell sort C++.
Example #1
Shell sort with explanation:
Syntax:
#include <iostream>
using namespace std;
void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
void shellSort(int arrayToSort[], int n) {
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i += 1) {
int swap = arrayToSort[i];
int j;
for (j = i; j >= gap && arrayToSort[j - gap] > swap; j -= gap) {
arrayToSort[j] = arrayToSort[j - gap];
}
if (arrayToSort[j] != swap){
if(gap%10 == 1){
cout<< " In the "<< gap << "st interval swap, we are swapping ";
cout<< arrayToSort[j] <<" and "<< swap;
cout<< endl;
arrayToSort[j] = swap;
}
else if(gap%10 == 2){
cout<< " In the "<< gap << "nd interval swap, we are swapping ";
cout<< arrayToSort[j] <<" and "<< swap;
cout<< endl;
arrayToSort[j] = swap;
}
else if(gap%10 == 3){
cout<< " In the "<< gap << "rd interval swap, we are swapping ";
cout<< arrayToSort[j] <<" and "<< swap;
cout<< endl;
arrayToSort[j] = swap;
}
else{
cout<< " In the "<< gap << "th interval swap, we are swapping ";
cout<< arrayToSort[j] <<" and "<< swap;
cout<< endl;
arrayToSort[j] = swap;
}
}
else{
if(gap%10 == 1){
cout<< " In the "<< gap << "st interval swap, we are not swapping ";
cout<< arrayToSort[j - gap] << " and " << arrayToSort[j];
cout<< endl;
}
else if(gap%10 == 2){
cout<< " In the "<< gap << "nd interval swap, we are not swapping ";
cout<< arrayToSort[j - gap] << " and " << arrayToSort[j];
cout<< endl;
}
else if(gap%10 == 3){
cout<< " In the "<< gap << "rd interval swap, we are not swapping ";
cout<< arrayToSort[j - gap] << " and " << arrayToSort[j];
cout<< endl;
}
else{
cout<< " In the "<< gap << "th interval swap, we are not swapping ";
cout<< arrayToSort[j - gap] << " and " << arrayToSort[j];
cout<< endl;
}
}
}
if(gap%10 == 1){
cout << "Array after the swaps at " << gap << "st interval";
}
else if(gap%10 == 2){
cout << "Array after the swaps at " << gap << "nd interval";
}
else if(gap%10 == 3){
cout << "Array after the swaps at " << gap << "rd interval";
}
else{
cout << "Array after the swaps at " << gap << "th interval";
}
cout << endl;
printArray(arrayToSort,n);
}
}
int main() {
int data[] = {91, 9, 27, 1, 11, 5, 6, 12};
int size = sizeof(data) / sizeof(data[0]);
cout << "Unsorted array: \n";
printArray(data, size);
shellSort(data, size);
cout << "Sorted array: \n";
printArray(data, size);
}Output:
Conclusion
In conclusion, in this article we have learned about working of shell sort, and following it is a small piece of code that tries to replicate the concept of the same. Here we looked at a step-by-step functionality as well. By now we do understand the difference between shell sort and insertion sort and the basis of generalization of shell sort! Rest keep experimenting!
Recommended Articles
This is a guide to Shell sort C++. Here we discuss definition, syntax, and parameters, How shell sort works in C++, examples with code implementation. You may also have a look at the following articles to learn more –
