Description

Shell Sort is an in-place comparison-based sorting algorithm. It is a generalization of insertion sort, allowing the exchange of items that are far apart. The method starts by sorting elements that are far apart, reducing the gap between elements as it progresses, and eventually performs a final insertion sort.

The gap sequence typically starts with half the size of the array and is repeatedly halved until it becomes 1. This technique helps reduce the time complexity compared to the standard insertion sort, especially for medium-sized arrays.

Working of Shell Sort Algorithm

1. Initial Gap Selection:

The algorithm starts with an initial gap, typically half the length of the array (n/2).

2. Gapped Insertion Sort:

For each gap, the algorithm performs a modified insertion sort where elements that are far apart (determined by the gap) are compared and swapped if necessary.
For instance, with a gap of 5, the element at position 0 is compared to the element at position 5, the element at position 1 is compared to the element at position 6, and so on.

3. Gap Reduction:

The gap is then reduced by half in each iteration until the gap becomes 1, which is equivalent to a regular insertion sort.

4. Final Pass:

Once the gap is 1, the algorithm performs the final pass similar to insertion sort, which ensures that the array is fully sorted.

5. Termination:

The process stops when the gap is reduced to 0, meaning the entire array has been sorted.

Key Steps of the Algorithm

1. For each gap from n/2 to 1:

• Perform gapped insertion sort for each subarray (elements at gap intervals).
• Reduce the gap by half and repeat.

2. Continue until the entire array is sorted.

Test Cases

Test Case 1: Basic test case with random elements

Input:

5
12 34 54 2 3

Expected Output:

Array before sorting:
12 34 54 2 3 
Array after sorting:
2 3 12 34 54

Test Case 2: Already sorted array

Input:

6
1 2 3 4 5 6

Expected Output:

Array before sorting:
1 2 3 4 5 6
Array after sorting:
1 2 3 4 5 6

Test Case 3: Reverse sorted array

Input:

6
6 5 4 3 2 1

Expected Output:

Array before sorting:
6 5 4 3 2 1
Array after sorting:
1 2 3 4 5 6

Test Case 4: Array with duplicate elements

Input:

7
4 3 3 1 4 5 3

Expected Output:

Array before sorting:
4 3 3 1 4 5 3
Array after sorting:
1 3 3 3 4 4 5

Fixes #293