Shell Sort

Shell Sort

This algorithm is efficient for medium-sized arrays and is an improvement over insertion sort due to its ability to move elements over larger distances early on.

This is basically insertion sort with different gap values. For insertion sort, the gap value is always 1.

There will be several iterations using larger gap values but the last iteration will always be using a gap value = 1. At that point, it is basically the same as insertion sort.

The same logic can be applied to bubble sort as well.

We start with gap value = size / 2 and decrementing it by 2 each time.

https://github.com/explorer436/programming-playground/tree/main/java-playground/my-implementations/searching-and-sorting/src/main/java/com/my/company/sorting/algorithms

Shell sort is an in-place comparison-based sorting algorithm that generalizes insertion sort by allowing the comparison and exchange of far-apart elements. It starts by sorting pairs of elements far apart from each other, then progressively reduces the gap between elements to be compared.

Pseudo Code for Shell Sort

function shellSort(arr):
    n = length(arr)
    // Start with a large gap, then reduce the gap
    gap = n / 2

    while gap > 0:
        // Perform insertion sort for elements at current gap
        for i = gap to n-1:
            temp = arr[i]
            j = i
            // Shift elements that are gap distance apart
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j = j - gap
            arr[j] = temp
        // Reduce the gap
        gap = gap / 2

    return arr

Explanation of Pseudo Code

1. Initialize Gap: Start with a gap equal to half the array length (n / 2).
2. Gap-Based Insertion Sort: For each gap, perform an insertion sort for elements that are gap positions apart.
   • Store the current element in temp.
   • Compare temp with elements at positions j - gap, shifting larger elements up.
   • Place temp in its correct position.
3. Reduce Gap: Halve the gap and repeat until the gap becomes 0.
4. Return Sorted Array: The array is fully sorted when the gap reaches 0.

Example

Consider the array: [64, 34, 25, 12, 22, 11, 90]

Step-by-Step Walkthrough

1. Initial Gap: n = 7, so gap = 7 / 2 = 3

   • Compare and sort elements 3 positions apart:
     • Compare 64 and 12: [12, 34, 25, 64, 22, 11, 90]
     • Compare 34 and 22: [12, 22, 25, 64, 34, 11, 90]
     • Compare 25 and 11: [12, 22, 11, 64, 34, 25, 90]
     • Compare 64 and 90: No swap needed.
   • Array after gap = 3: [12, 22, 11, 64, 34, 25, 90]

2. Reduce Gap: gap = 3 / 2 = 1 (now it’s like insertion sort)

   • Perform insertion sort on the entire array:
     • 12 is in place.
     • Insert 22: No swap needed.
     • Insert 11: Shift 22, 12: [11, 12, 22, 64, 34, 25, 90]
     • Insert 64: No swap needed.
     • Insert 34: Shift 64: [11, 12, 22, 34, 64, 25, 90]
     • Insert 25: Shift 64, 34: [11, 12, 22, 25, 34, 64, 90]
     • Insert 90: No swap needed.
   • Array after gap = 1: [11, 12, 22, 25, 34, 64, 90]

3. Gap = 0: Stop, as the array is sorted.

4. Final Sorted Array [11, 12, 22, 25, 34, 64, 90]

Complexity analysis

• Time Complexity:
  • Best Case: O(n log n)
  • Average Case: Depends on gap sequence, typically O(n^1.3)
  • Worst Case: O(n^2) for some gap sequences
• Space Complexity: O(1) (in-place sorting)
• Gap Sequence: The example uses n/2, n/4, ..., but other sequences (e.g., Hibbard, Knuth) can improve performance.