Updated March 13, 2023
Introduction to Shell Sort in Data Structure
Data structure provides different kinds of sorting techniques; the shell sort is one of the sorting techniques. The shell sort is basically based on the insertion sort algorithm, and it is a very highly efficient sorting technique in the data structure. In insertion sort, we move the element only one position at a time. Sometimes we move elements far ahead; at that time, we require multiple moves. In shell sort, first, sort the element from each other and reduce the interval between the sorted elements. The sell sort performs the sort with a specific interval. So the interval between elements decreases, and the shell sort performance depends on what type of input we give to sort shell.
Syntax:
shell_sort (Array_name, size_of_array)
for interval j < size_of_array / 2 n to 1
for each interval “j” in Array_name
sorted element from the shell sort at interval “j”
end shell_sort
Explanation:
- In the above syntax, we first define the user-defined function with two parameters: array name and size of the array inside the function. After that, we need to compare the interval with the size of the array and print the value for each interval as shown in the above syntax.
How to Perform Shell Sort in Data Structure?
Now let’s see how shell sort works in a data structure as follows.
Shell sort is similar to insertion sort, which conquers the downsides of insertion sort by looking at components isolated by a hole of a few positions. All in all, Shell sort plays out the accompanying advances.
Stage 1: Arrange the components in the table structure and sort the columns by utilizing insertion sort.
Stage 2: Repeat Stage 1 each time with a more modest number of longer columns so that toward the end, there is just a single column of information to be sorted.
Example:
Now consider a simple example for a better understanding of shell sort, which means how it works.
Now take array {45, 35, 52, 19, 24, 29, 37, 54}. Now divide the given array into the interval here we make 4 intervals of 4 positions that means virtual sub list of array as below. {45, 24}, {35, 29}, {52, 37}, {19, 54}
Now compare each value from the sub list and interchange if required in the original array.
The structure of the array list is shown in the below figure as follows.
The final array after interchanged the value as shown in the below figure as follows.
Now we take the interval of 1 position, and it creates the two sub-lists that are {24, 52, 45, 52} and {29, 19, 35, 54} as shown in the below figure as follows and follow the same process of interchange.
Now we get a new array, as shown in the below figure as follows.
Finally, we got a new array with new values; now, a shell sort applies the insertion sort techniques to then sort the array.
Step 1: Compare the first two elements from the array and interchanged if required. See here the first element is less than the second element that is 24 is less than 29, so there is no need to swap the values and final array list as shown in the below figure as follows.
Step 2: Repeat the same process and compare the second and third elements from the array list. In this step, the second element is less than the third element that is 29, is less than 37. So there is no need to perform the swap operation.
The final array list is shown in the below figure as follows.
Step 3: Now compare the third and fourth elements from the array list. See here fourth element is less than the third element, that 19 is less than 34, so we need to perform the swap operation then final array as shown in the figure below.
Step 4: Now, see here the third element is less than the second element, so we need to perform the swap operation, and final array list as shown in the below figure as follows.
Step 5: Notice where the second element is less than the first element that is 19 is less than 24. So we need to perform the swap operation and final array list as shown in the below figure as follows.
Step 6: Now compare the fourth and fifth elements; see here 37 is less than 45, so there is no need to perform the swap operation and final array list as shown in the below figure as follows.
Step 7: Now compare 45 and 35; see here 35 is less than 45. So we need to perform the swap operation and final array list as shown in the below figure as follows.
Step 8: Notice here 35 is less than 37, so we need to perform the swap operation and final array list as shown in the below figure as follows.
Step 9: Now see the remaining elements that mean value are sorted, that means there is no need to perform any swap operation and final array list as shown in the figure below.
Algorithm for shell sort as follows:
Step 1: Initialize the size of the array.
Step 2: After that, we need to divide the array list into the sub list of the same interval.
Step 3: Sort array list by using insertion sort.
Step 4: Repeat all steps until the list is sorted.
Example of Shell Sort in Data Structure
Given below is the example of shell sort by using python programming languages as follows:
Code:
def shell_Sort(arr_list):
diff = len(arr_list) // 2
while diff > 0:
i = 0
j = diff
while j < len(arr_list):
if arr_list[i] > arr_list[j]:
arr_list[i], arr_list[j] = arr_list[j], arr_list[i]
i += 1
j += 1
while i - diff != -1:
if arr_list[i - diff] > arr_list[i]:
arr_list[i - diff], arr_list[i] = arr_list[i], arr_list[i - diff]
i -= 1
diff //= 2
arr_list1 = [45, 35, 52, 19, 24, 29, 37, 54]
print("User input Array List is:", arr_list1)
shell_Sort(arr_list1)
print("sorted Array List is:", arr_list1)
We can implement it by using different programming languages.
Explanation:
- In the above example, we try to implement shell sort.
- The final output of the above statement we illustrate by using the following snapshot.
Output:
Conclusion
From the above article, we have seen the basic syntax of Shell sort, and we have also seen examples of Shell sort. We have seen how and when we use the Shell sort in the data structure from this article.
Recommended Articles
This is a guide to Shell Sort in Data Structure. Here we discuss the introduction, how to perform shell sort in data structure? and examples. You may also have a look at the following articles to learn more –
