Shell sort is an in-place comparison-based sorting algorithm. It generalizes insertion sort by allowing the exchange of items that are far apart. The algorithm starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. The efficiency of Shell sort depends on the gap sequence used, with time complexity varying from O(n^2) to O(n log n) based on the sequence.
Consider an array with the following elements:
[12, 34, 54, 2, 3]
To sort this array using Shell sort, follow these steps:
Let's apply these steps to the example array:
Below is the pseudo code for the Shell sort algorithm:
function shellSort(array)
n = length(array)
gap = n // 2
while gap > 0 do
for i = gap to n - 1 do
temp = array[i]
j = i
while j >= gap and array[j - gap] > temp do
array[j] = array[j - gap]
j = j - gap
end while
array[j] = temp
end for
gap = gap // 2
end while
end function
Explanation:
def shell_sort(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 -= 1
arr[j] = temp
gap //= 2
return arr
# Example usage:
array = [12, 34, 54, 2, 3]
print("Original array:", array)
sorted_array = shell_sort(array)
print("Sorted array:", sorted_array) # Output: [2, 3, 12, 34, 54]
This Python program defines a function to perform Shell sort on an array. The function initializes the gap, performs a gapped insertion sort for each gap, and reduces the gap until the array is fully sorted.