Updated April 12, 2023
Introduction to Shell sort in Python
Shell sort is defined as the variation of insertion sort which is an algorithm for sorting the elements in a method such as it sorts the elements far apart from each element and then successively goes on deducing the interval rate which is between each element which is given for sorting. In general, we can shell sort is an algorithm in Python or any other programming language which is used to first sort the element which is separated far from each element and then it reduces each successive elements at a certain or particular rate of the interval between every element and hence this is said to be a generalized version of insertion sort.
Syntax:
Shell sort is an algorithm and instead, it uses a formula for calculating the intervals between the elements which is known as “Knut’s Formula”. In this, we will see the algorithm and the formula used in sorting the given elements. The algorithm is as follows:
Step 1: Firstly we need to initialize any variable which is later used in the formula for calculating the interval. We are using “k”.
Step 2: Then the given list is divided into the sublists in which each list is separated by the interval calculated (k).
Step 3: Then we sort the obtained sub-lists using the insertion sort method.
Step 4: Then continue the above 3 steps until the given list is obtained in sorted order.
Now as mentioned above, to calculate interval we are using Knuth’s formula and the formula is as follows:
k = k * 3 +1
here, k the value in which the interval is obtained and its initial value starts from 1 and n as the nth increment.
How shell sort works in Python with examples?
The shell sort is an algorithm and its workings are simple in all programming language and let us see the working on a given array of numbers with “n” numbers with given original sequence of shell’s algorithm ( other such sequences are Knuth’s sequence, Sedgewick’s sequence, Hibbard’s sequence) as intervals such as ( n/2, n/4, n/8,…. 1) and then the given array which contains “n” number of elements which are at the given interval for the first loop with interval rate staring at n/2, n/4 at the second loop and so on where these elements are compared and swapped if the given elements are not in order, which means that 0th element in the given array is compared to the number at n/2th element which this element is stored in one variable named “temp” and 0th element will be stored in n/2th element and the element stored in the temp variable will be stored in 0th position. This is how the numbers are swapped and are arranged in order and this process continues for the remaining elements until the elements are sorted completely. Below is the algorithm is given, where the examples work based on the below-given algorithm.
Shellsortalgo( arr, size)
for interval t < -1 size/2n till 1
for each interval t in arr
sort all the elements at the given interval "t"
end ShellsortalgoExamples
Let us consider the example for shell sorting in Python:
Example #1
Code:
def shellSortalgo(arr):
n = len(arr)
intv = n/2
while intv > 0:
for i in range(intv,n):
temp = arr[i]
j = i
while j >= intv and arr[j-intv] >temp:
arr[j] = arr[j-intv]
j -= intv
arr[j] = temp
intv /= 2
print("Demonstration of shell sort algorithm in Python is as follows:")
print("\n")
arr = [ 49, 15, 98, 7, 23]
n = len(arr) # len() method gives the total elements present in the
# specified array.
print ( "The given array before sorting is as follows:" )
for i in range(n):
print(arr[i]),
shellSortalgo(arr)
print("\n")
print ( "The Array after sorting is as follows:" )
for i in range(n):
print(arr[i]),Output:
In the above program, we can see first we have declared a function in which we are including the logic of how shell sort will work with the given array of numbers and the function name is “shellsortalgo()” where we are passing an array as an argument to this function. In this function firstly we will declare a variable in which we will store the length of the given array such as “n” size of the array, then we will declare the interval variable in which we will declare the interval for which we start with interval 1 till the length of the array obtained as “n” we will check all the elements and then from the given interval we will start swapping the elements by reducing the intervals until it becomes 1. In the above program, we have already specified the array as “arr” with 5 elements. Where here the interval will start using the shell original sequence n/2, n/4,… as the n value here is 5 then the interval is n/2 which is 5/2 = 2, therefore, it compares 0th and 2nd element and swap these numbers using temp variable and if the 0th element is greater than 2nd element then the numbers will be swapped and these steps are continued till all the elements are sorted and the output is as shown in the above screenshot.
Example #2
Now we will see another example where the user itself can enter the array of numbers to sort the elements using the shell sort algorithm.
Code:
def interval(size):
l = size.bit_length()
for k in range(l - 1, 0, -1):
yield 2**k - 1
def shellsortalgo(lst):
def insertion_sort_with_gap(intv):
for i in range(intv, len(lst)):
temp = lst[i]
j = i - intv
while (j >= 0 and temp < lst[j]):
lst[j + intv] = lst[j]
j = j - intv
lst[j + intv] = temp
for g in interval(len(lst)):
insertion_sort_with_gap(g)
print( "Demonstration of shell sort with user input" )
print("\n")
lst = input('Enter the list of numbers as array: ').split()
lst = [int(x) for x in lst]
shellsortalgo(lst)
print('Array after sorting the given list: ', end='')
print(lst)Output:
In the above program, it is similar to the above example it works the same as the above example but here the only difference is the array is specified by the user which means here we have provided users to enter the array elements and it takes the same logic where it sorts the elements using the shell sort algorithm and the output is as shown in the above program.
Conclusion
In this article, we conclude that the shell sort algorithm in Python is the same as in another programming language. The shell sort is an algorithm which is based on insertion sort which is used for sorting the given elements in an array in the ascending order which also uses Knuth’s formula to calculate the interval rate which will help to sort by reducing these intervals and sort the elements.
Recommended Articles
We hope that this EDUCBA information on “Shell sort in Python” was beneficial to you. You can view EDUCBA’s recommended articles for more information.
