1. Introduction
Shell sort, also known as the diminishing increment sort, is a generalization of the insertion sort algorithm that allows the exchange of elements that are far apart. The idea is to arrange the list of elements so that, starting from any given position, taking every hth element produces a sorted list. These lists are sorted individually, and the process is repeated for different values of h.
2. Implementation Steps
1. Choose an increment h to start with, where h is typically chosen as less than the total number of elements.
2. Sort the sublists created by considering elements at every hth interval.
3. Reduce the increment h and repeat step 2.
4. Continue this process until h is reduced to 1.
3. Implementation in Ruby Programming
def shell_sort(array)
n = array.length
# Start with a large gap and reduce the gap with each iteration
gap = n / 2
# Continue until the gap is 1
while gap > 0
# Do a gapped insertion sort for this gap size
for i in gap...n
temp = array[i]
j = i
# Shift elements by gap until correct position is found
while j >= gap && array[j - gap] > temp
array[j] = array[j - gap]
j -= gap
end
array[j] = temp
end
gap /= 2 # Reduce the gap size
end
end
# Client code
arr = [12, 34, 54, 2, 3]
puts "Original Array: #{arr}"
shell_sort(arr)
puts "Sorted Array: #{arr}"
Output:
Original Array: [12, 34, 54, 2, 3] Sorted Array: [2, 3, 12, 34, 54]
Explanation:
1. Shell sort is an optimized version of insertion sort that sorts elements that are far apart from each other.
2. It begins with a large gap size and reduces the gap size in each iteration.
3. For each gap size, it performs a gapped insertion sort.
4. As the gap size reduces, the array becomes more sorted until the gap size becomes 1. At this point, the array is fully sorted.
Comments
Post a Comment