Shell Sort

Shell Sort is an improved version of Insertion Sort that works efficiently on large arrays.

It compares elements far apart first, then reduces the gap between elements to be compared.

This allows elements to move closer to their final position faster than regular insertion sort.

It is named after its inventor Donald Shell, who introduced it in 1959.

How Shell Sort Works?

Shell Sort works by:

• Starting with a larger gap and sorting elements that are that far apart.
• Gradually reducing the gap.
• Ending with a gap = 1, which is a standard insertion sort pass.

No matter whether n is even or odd, Shell Sort still works because:

• Integer division (gap = gap / 2) takes care of reducing the gap.
• It stops when gap = 0.

Finding the Gap Sequence for n (initially n = number of given element)

If array is [45, 23, 53, 12, 9, 78, 67, 34, 1] where n = 9

So the gap sequence will be: 4 → 2 → 1 and so on.

Example: Shell Sort

Sorting the array [45, 23, 53, 12, 9, 78, 67, 34, 1] using Selection Sort

Step-by-Step Process

Step 1: Calculate initial gap

Using the common gap sequence:

gap = n / 2 = 9 / 2 = 4 (integer division)

Step 3: Sort elements that are gap = 4 apart

We compare and possibly swap elements at indices:

• (0, 4): 45 and 9 → since 9 < 45, swap

Array: [9, 23, 53, 12, 45, 78, 67, 34, 1]

• (1, 5): 23 and 78 → 23 < 78, no swap
• (2, 6): 53 and 67 → 53 < 67, no swap
• (3, 7): 12 and 34 → 12 < 34, no swap
• (4, 8): 45 and 1 → 1 < 45, swap

Array: [9, 23, 53, 12, 1, 78, 67, 34, 45]

Step 4: Reduce gap

gap = gap / 2 = 4 / 2 = 2

Compare elements 2 apart

• (0, 2): 9 vs 53 → 9 < 53 → no swap
• (1, 3): 23 vs 12 → 23 > 12 → swap

Array: [9, 12, 53, 23, 1, 78, 67, 34, 45]

• (2, 4): 53 vs 1 → 53 > 1 → swap

Array: [9, 12, 1, 23, 53, 78, 67, 34, 45]

• (3, 5): 23 vs 78 → 23 < 78 → no swap
• (4, 6): 53 vs 67 → 53 < 67 → no swap
• (5, 7): 78 vs 34 → 78 > 34 → swap

Array: [9, 12, 1, 23, 53, 34, 67, 78, 45]

• (6, 8): 67 vs 45 → 67 > 45 → swap

Array: [9, 12, 1, 23, 53, 34, 45, 78, 67]

Step 5: Reduce gap

gap = 2/2 = 1 (final pass)

Compare elements 1 apart (regular adjacent comparison)

• (0, 1): 9 vs 12 → 9 < 12 → no swap
• (1, 2): 12 vs 1 → 12 > 1 → swap

Array: [9, 1, 12, 23, 53, 34, 45, 78, 67]

• (2, 3): 12 vs 23 → 12 < 23 → no swap
• (3, 4): 23 vs 53 → 23 < 53 → no swap
• (4, 5): 53 vs 34 → 53 > 34 → swap

Array: [9, 1, 12, 23, 34, 53, 45, 78, 67]

• (5, 6): 53 vs 45 → 53 > 45 → swap

Array: [9, 1, 12, 23, 34, 45, 53, 78, 67]

• (6, 7): 53 vs 78 → 53 < 78 → no swap
• (7, 8): 78 vs 67 → 78 > 67 → swap

Array: [9, 1, 12, 23, 34, 45, 53, 67, 78]

After first pass of gap = 1, array is [9, 1, 12, 23, 34, 45, 53, 67, 78]

Because the array is not sorted yet, repeat gap = 1 passes until sorted.

• Compare (0,1): 9 vs 1 → swap

Array: [1, 9, 12, 23, 34, 45, 53, 67, 78]

• Rest pairs already sorted, no swaps needed.

Final sorted array: [1, 9, 12, 23, 34, 45, 53, 67, 78]

Here is an example to help you understand the working of Shell sort on array of elements name A = {17, 3, 9, 1, 8}

Algorithm for Shell Sort

Step-by-Step Algorithm

Input: An array arr of size n
Output: Sorted array in ascending order
Initialize gap = n / 2 (integer division)
While gap > 0 do the following
	For i from gap to n - 1:
    	Store temp = arr[i]
    	Initialize j = i
    	While j >= gap and arr[j - gap] > temp
        	Move arr[j - gap] to arr[j]
        	Update j = j - gap
    	Insert temp at position arr[j]
	Update gap = gap / 2 (integer division)
End While
Return sorted array

Advantages of Shell Sort

Efficient for medium-sized arrays: Shell Sort performs much better than simple algorithms like Bubble, Selection, or Insertion sort for moderately sized arrays.

In-place sorting: It requires only a small, constant amount of extra memory space (no large additional arrays).

Improves on insertion sort: By allowing exchanges of far apart elements, it reduces large-scale disorder quickly, making the final insertion sort phase faster.

Simple to implement: Easier to code compared to more complex sorts like Quick Sort or Merge Sort.

Adaptive: Works well when the array is already partially sorted.

Disadvantages of Shell Sort

Not stable: Equal elements may change their relative order after sorting.

Performance depends on gap sequence: The efficiency is highly influenced by the choice of gap values; no definitive best sequence exists.

Worst-case complexity is not guaranteed: Worst-case time complexity can degrade to O(n²) with some gap sequences.

Not suitable for very large datasets: For very large data, more efficient algorithms like Quick Sort, Merge Sort, or Heap Sort are preferred.

When to Use Shell Sort?

When you need a simple, easy-to-implement sorting algorithm that performs better than basic sorts (like Bubble or Insertion Sort) on medium-sized arrays.

When you have limited memory, since Shell Sort sorts in-place and uses very little extra space.

When your data is partially sorted or nearly sorted, as Shell Sort can take advantage of this to run faster.

When you want a fairly efficient algorithm without the complexity of Quick Sort or Merge Sort.

In scenarios where stability is not a concern (because Shell Sort is not stable).

When you want to improve insertion sort’s efficiency on larger arrays by reducing the total number of shifts required.

Shell Sort in C Programming

#include <stdio.h>

// Function to perform Shell Sort
void shellSort(int arr[], int n) {
    // Start with a big gap, then reduce the gap
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // Perform a gapped insertion sort for this gap size
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;
            // Shift earlier gap-sorted elements up until the correct location for arr[i] is found
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            // Put temp (the original arr[i]) in its correct location
            arr[j] = temp;
        }
    }
}

// Function to print the array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {45, 23, 53, 12, 9, 78, 67, 34, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array:\n");
    printArray(arr, n);

    shellSort(arr, n);

    printf("Sorted array:\n");
    printArray(arr, n);

    return 0;
}

• The shellSort function starts with a big gap and reduces it each iteration.
• It performs insertion sort on elements that are gap apart.
• Eventually, gap becomes 1, and the array is fully sorted.

Output:

Original array:
45 23 53 12 9 78 67 34 1 
Sorted array:
1 9 12 23 34 45 53 67 78 

Complexity of Shell Sort

Here’s the Time and Space Complexity of Shell Sort.

Space Complexity: O(1) (constant space)

Shell Sort is an in-place sorting algorithm and requires only a small amount of extra space for variables.

Numerical Question for selection Sort

1. Sort the following array using Shell Sort and show each pass. {32, 17, 45, 23, 5, 12, 8}
2. Sort the array using Shell Sort and explain how the gap is reduced in each step. {64, 25, 12, 22, 11}
3. Apply Shell Sort to this array and display the result after each gap reduction. {90, 70, 50, 30, 10, 20, 40, 60, 80}
4. Manually trace Shell Sort on this input and provide the sorted array. {5, 3, 1, 4, 2}
5. Using Shell Sort, sort the array and count the total number of comparisons. {10, 20, 5, 15, 25}
6. Given the array below, show how Shell Sort rearranges it using a gap sequence of n/2, n/4, ..., 1. {100, 34, 56, 23, 67, 45, 89}