Shell Sort in Data Structure

What is Shell Sort in Data Structure?

Shell sort is a type of in-place comparison also known as Shell sort or Shell's approach. It can be represented as a generalization of either exchange bubble sorting or insertion sorting. The procedure starts by sorting pairs of components that are far away, then gradually closing the space between the elements to be compared. 

Optimal Sequences for Shell Sort Algorithm

Several optimum sequences that are suitable for the shell sort method include:

• Shell's original sequence: N/2 , N/4 , …, 1
• Knuth's increments: 1, 4, 13, …, (3k – 1) / 2
• Sedgewick's increments: 1, 8, 23, 77, 281, 1073, 4193, 16577...4j+1+ 3·2j+ 1
• Hibbard's increments: 1, 3, 7, 15, 31, 63, 127, 255, 511…
• Papernov & Stasevich increment: 1, 3, 5, 9, 17, 33, 65,...
• Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81...

Shell Sort Algorithm

• Step 1: Start the Shell Sort algorithm.
• Step 2: Define an initial value for the gap size, 'h'.
• Step 3: Divide the list into smaller sub-parts, with 'h' intervals between each member.
• Step 4: Use insertion sort to partially sort each sub-list.
• Step 5: Repeat Steps 2-4, decreasing the gap size 'h' with each iteration, until the list is ordered.
• Step 6: Print the sorted list.
• Step 7: Finish the algorithm.

Complexity Analysis of Shell Sort Algorithm

Time Complexity

Best Case Complexity

This occurs when no sorting is necessary, i.e., the array is pre-sorted. The best-case time complexity for Shell sort is O(n*logn).

Average Case Complexity

This arises when the array elements are jumbled and do not appropriately climb or descend. The average time complexity of Shell sort is O(n*logn).

Worst Case Complexity

This occurs when array members must be sorted in reverse order. That is, assume you need to sort the array elements in ascending order but the elements are in descending order. The worst-case temporal complexity for Shell sort is O(n2).

Space Complexity

The shell sort has a space complexity of O(1) because it uses an extra space for sub-lists.

Applications of Shell Sort

• Numeric data: Efficient sorting for arrays of variable sizes.
• Strings: Sorting strings alphabetically or using predefined criteria.
• Records or objects: Sorting records or objects by custom attributes.
• Large data sets: Better than simpler algorithms.
• Online sorting: Responsible for continuously updating sorted lists and dynamically modifying gap sequences.

Advantages of Shell Sort

• Medium-sized lists: Useful for lists of moderate size.
• In-place sorting: Operates immediately on the input list, saving memory.
• Adaptive: Adjusts the gap dynamically, taking use of partially sorted lists.
• Versatile: It is suitable for a wide range of applications, including embedded devices and scenarios with limited memory.

Disadvantages of Shell Sort

• Unstable: Shell sort may change the order of equal components.
• Gap sequence impact: Performance varies depending on the gap sequence; determining the optimum sequence is difficult.