# Shell Sort in Data Structure

Mentor: Shailendra Chauhan
Duration : 00:03:00

## 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.