C++

Shell Sort C++

The C++ language came up with many sorting techniques to be used in the program for sorting an array of objects. One of those sorting techniques is the Shell sort which is mainly another form of insertion sort. Within insertion sort, we tend to move a single value to its next index position. The movement of a value to the consecutive next index may not give the required result if we want to place it at the end and can take more time while sorting. At the same time, the shell sort can move a value far from its original place and takes less time doing so. Thus, we have decided to demonstrate the working of the shell sort technique in C++ programming. Let’s start with C++ file creation and its opening through the instructions demonstrated below on the terminal console of the Ubuntu 20.04 system.

Example 01:

Starting from the first example in a new file, we have to utilize the required libraries first. Without the “iostream” header, a user cannot make use of any input and output stream in the code. A C++ programmer will always make use of “namespace” and libraries like “iostream,” “stdlib,” and “stdio.h,” etc. Here comes the swap() method that will be called by the “sort” function. The sort function will pass two values at different locations to the “swap()” method and use the “temp” variable to swap them with each other.

The show() function will take an array and its size to be shown in its parameters from the main() method. It will use the “for” loop to iterate the whole array up to its size “s.” Use the “cout” object to display each value using the index “I” separated from other values by a space. After all the values are displayed, the cout will be used again to add the line break.

After the unsorted array has been displayed, it’s turning for the “sort” function to work on it. The sort function will be taking an array and its size for use. Initialized three integer variables g, j, k. The variable “g” will be used in the first outer “for” loop to reduce the gap between values. It will be started from the mid of the array as per “g=n/2”. On each iteration, the gap will be again decreased by “g/2,” i.e., another half will be created. By doing so, the array will be split into various parts, and the gap size will be less. The next “j” loop will start from the current gap value, i.e., “g,” which will be the mid-point of an array at that time. And it will continue until the last index of an array. On each iteration, “j” will be incremented. The “k” for loop will start from “j-g” and continue until “k>=.” If the value at “k+g” is greater than or equal to the value at “k” of an array, it will break the loop. Otherwise, the values will be swapped by the “swap” function call. Most probably, the value at “k+g” will be a starting position, and “k” will be at the last position of an array.

Every program starts its execution from the main() driver function code while execution. Our main() function has been started with an integer array “A” initialization. This array “A” will be in a random order, i.e., unordered. The “cout” object is the C++ standard output statement used to display some text or variable value on the shell. This time, we have been using it to let users know that the array before sorting will be displayed on the screen. The “Show()” function will be called by passing it the original unsorted array “A” and the number of values you want to show before sorting. Although there are a total of 10 elements in the array, we have been sorting and displaying only 9. The “Sort” method is called by passing the array and number of elements to be sorted here. After the sorting has been done with the shell sort, the “Show” method will be utilized again to display the total of the first 9 elements sorted on the shell.

The shell.cc file got compiled and resulted in the below-shown output after the execution. The unsorted 9 elements for the array are displayed first. In the last line, the same 9 elements of an array are displayed in ascending order for sort.

Example 02:

Here comes a new example of using shell sort in our program. We have been using the same shell.cc file and initialized our code with the same header and namespace. This program starts from the main() function. The main() method has an integer array A of 5 values already initialized. The “n” variable is initialized by using the “sizeof()” function for c++. This is used to calculate total numbers in an array “A” and save that value to variable “n.” We can see that the array has only 5 elements, so you can just skip the use of calculating several elements and use “5” anywhere in the code.

There comes the message for users to be alert because the unsorted array will be displayed, i.e., via “cout.” The “Display()” function is called here to display the full unsorted array by passing it an array and the number of elements in it. The display() function will be using the “for” loop to iterate the passed array up to its last index and display the values as it is using the object “cout” and index “I.” Here comes the “sort()” method. The function call to this method is taking the array and its total number of elements as input. The outer-most “for” loop is here to decrease the gap between the values/indexes by dividing the total number of elements by 2.

The value of “g” must be greater than 0, and it will be decreased by 2 again after each iteration. This will decrease the gap in each iteration. The inner “I” loop will take the value of gap “g” as a starting point and continue until “n.” Within this loop, the value of “I” will be assigned to the “temp” temporary variable. The inner-most “j” loop is here. It starts from the point “I” until the value of g becomes equal to or greater than “g,” and also, the value at index “j-g” of the array becomes greater than the “temp” variable. The “j” will be decremented by “g” each time. This loop will continue to swap the value at the “j-g” index with the value at “j.” The value of “temp” will be assigned to index “j” of the array, i.e., swap where required. After coming back to the main() function, the display() method will be called again to display the sorted array.

On compilation and running of the shell.cc file, it turns out that the unsorted array has been sorted now.

Conclusion:

In our introduction paragraph, we have illustrated the main purpose of using the shell sort rather than insertion sort in C++. To demonstrate how it works, two simple yet diverse examples have been built, which may be changed according to the user’s preferences. The first example uses user-defined methods to swap and sort elements, but the second uses a single function to perform both. Both of these shell sort scenarios may be used for any technology-related project.

About the author

Aqsa Yasin

I am a self-motivated information technology professional with a passion for writing. I am a technical writer and love to write for all Linux flavors and Windows.