Shell Sort is an efficient sorting algorithm that falls under the category of insertion sort. It was developed by Donald Shell in 1959, and is a type of comparison sort. Shell Sort works by comparing elements that are far apart, and then gradually reducing the gap between the elements until the array is eventually sorted. This technique allows Shell Sort to move larger elements to their correct positions more quickly than other sorting algorithms.
Shell Sort is a general-purpose sorting algorithm that is relatively simple to understand and implement. It works by comparing elements that are far apart and then gradually reducing the gap between the elements until the array is eventually sorted. This article will provide a detailed explanation of how Shell Sort works, as well as its time and space complexities. We will also provide a python code example for each of the topics covered.
How Does Shell Sort Work?
Shell Sort is a sorting algorithm that works by comparing elements that are far apart and gradually reducing the gap between the elements until the array is eventually sorted. It works by first comparing elements that are far apart, and then gradually reducing the gap between the elements until the array is eventually sorted.
First, the array is divided into subarrays. Each subarray consists of elements with a certain gap between them. The gap is usually set to be the length of the array divided by 2. The array is then sorted using insertion sort. After the insertion sort is complete, the gap is decreased by half and the process repeats. This process is repeated until the gap is 1 and the array is sorted.
Let’s look at an example to understand how Shell Sort works. Consider the following array of integers:
[5, 4, 1, 8, 7, 2, 9, 6, 3]
We will use a gap of 4 for this example. The array is then divided into subarrays with the following elements:
Subarray 1: [5, 1, 7, 9]
Subarray 2: [4, 8, 2, 6]
Subarray 3: [3]
We then sort each of the subarrays using insertion sort. The sorted subarrays are as follows:
Subarray 1: [1, 5, 7, 9]
Subarray 2: [2, 4, 6, 8]
Subarray 3: [3]
Now, we reduce the gap to 2. The array is then divided into subarrays with the following elements:
Subarray 1: [1, 5, 7]
Subarray 2: [2, 4, 6, 8]
Subarray 3: [3]
We then sort each of the subarrays using insertion sort. The sorted subarrays are as follows:
Subarray 1: [1, 5, 7]
Subarray 2: [2, 4, 6, 8]
Subarray 3: [3]
Finally, we reduce the gap to 1. The array is then divided into subarrays with the following elements:
Subarray 1: [1, 5, 7]
Subarray 2: [2, 4, 6]
Subarray 3: [3, 8]
We then sort each of the subarrays using insertion sort. The sorted subarrays are as follows:
Subarray 1: [1, 5, 7]
Subarray 2: [2, 4, 6]
Subarray 3: [3, 8]
After the subarrays are sorted, the array is combined and sorted using insertion sort. The final sorted array is:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Time Complexity of Shell Sort
The time complexity of Shell Sort depends on the gap sequence used. The best case time complexity is O(n). This occurs when the gap sequence is defined as 2^k – 1, where k is the number of elements in the array.
The average time complexity of Shell Sort is O(n^2). This occurs when the gap sequence is defined as 2^k – 1, where k is the number of elements in the array.
The worst case time complexity of Shell Sort is O(n^2). This occurs when the gap sequence is defined as 2^k – 1, where k is the number of elements in the array.
Space Complexity of Shell Sort
The space complexity of Shell Sort is O(1). This is because the algorithm does not require any additional storage space other than the array being sorted.
Python Code Example
Now that we have a good understanding of how Shell Sort works, the time and space complexities, let’s look at a Python code example.
# Function to sort the array
def shellSort(arr):
# Start with a big gap, then reduce the gap
n = len(arr)
gap = n//2
# Do a gapped insertion sort for this gap size.
# The first gap elements a[0..gap-1] are already in gapped
# order keep adding one more element until the entire array
# is gap sorted
while gap > 0:
for i in range(gap,n):
# add a[i] to the elements that have been gap sorted
# save a[i] in temp and make a hole at position i
temp = arr[i]
# shift earlier gap-sorted elements up until the correct
# location for a[i] is found
j = i
while j >= gap and arr[j-gap] > temp:
arr[j] = arr[j-gap]
j -= gap
# put temp (the original a[i]) in its correct location
arr[j] = temp
gap //= 2
# Driver Code
arr = [ 5, 4, 1, 8, 7, 2, 9, 6, 3 ]
shellSort(arr)
print ("Sorted array:")
for i in range(len(arr)):
print(arr[i]),
Conclusion
In this article, we discussed Shell Sort, a type of comparison sorting algorithm. We discussed how it works, its time and space complexities, and provided a Python code example. We hope this article provided a clear understanding of Shell Sort and its various aspects.
Exercises
Write a function that takes in an array and sorts it using Shell Sort.
def shellSort(arr):
n = len(arr)
gap = n//2
while gap > 0:
for i in range(gap,n):
temp = arr[i]
j = i
while j >= gap and arr[j-gap] > temp:
arr[j] = arr[j-gap]
j -= gap
arr[j] = temp
gap //= 2
Write a function that takes in a gap sequence and sorts an array using Shell Sort.
def shellSort(arr, gap_sequence):
n = len(arr)
for gap in gap_sequence:
for i in range(gap,n):
temp = arr[i]
j = i
while j >= gap and arr[j-gap] > temp:
arr[j] = arr[j-gap]
j -= gap
arr[j] = temp
Write a function that takes in an array and returns its time complexity using Shell Sort.
def shellSortTimeComplexity(arr):
n = len(arr)
gap = n//2
time_complexity = 0
while gap > 0:
for i in range(gap,n):
time_complexity += 1
temp = arr[i]
j = i
while j >= gap and arr[j-gap] > temp:
arr[j] = arr[j-gap]
j -= gap
time_complexity += 1
arr[j] = temp
gap //= 2
return time_complexity
Write a function that takes in an array and returns its space complexity using Shell Sort.
def shellSortSpaceComplexity(arr):
n = len(arr)
space_complexity = 0
for i in range(n):
space_complexity += 1
return space_complexity
Write a program to sort an array using Shell Sort.
def shellSort(arr):
n = len(arr)
gap = n//2
while gap > 0:
for i in range(gap,n):
temp = arr[i]
j = i
while j >= gap and arr[j-gap] > temp:
arr[j] = arr[j-gap]
j -= gap
arr[j] = temp
gap //= 2
arr = [ 5, 4, 1, 8, 7, 2, 9, 6, 3 ]
shellSort(arr)
print ("Sorted array:")
for i in range(len(arr)):
print(arr[i]),