yumyum116

Posted on Jan 3

Implementing Shell Sort: From Theory to Practical Code

#shellsort #python

This article is part of a series focused on translating algorithmic theory into practical code implementations.

I am glad if this blog helps beginners, or those transitioning their careers into software engineering, take a step forward.

In this article, I implement Shell sort, one of the more efficient sorting algorithms, using multiple approaches.

What is shell sort?

Shell sort is an improvement over insertion sort, which is one of the fundamental sorting algorithms. Insertion sort compares and inserts adjacent elements in a given array.

By contrast, Shell sort repeatedly performs insertion-like operations on elements that are separated by a fixed gap, gradually reducing the gap size. Eventually, when the gap becomes 1, the algorithm behaves exactly like insertion sort.

This raised an important question: is Shell sort ultimately becomes insertion sort, where does the improvement come from?

Before diving into the main discussion, let me briefly introduce some background.

There are two common measures used to evaluate algorithm performance: time complexity and space complexity. In this article, I will not explain these concepts in detail; instead, I will refer to them using $Big-O$ notation, which expresses their behavior mathematically.

For an input size of $n$ , the time complexity of insertion sort ranges from $O(n^2)$ to $O(n)$ .

In contrast, Shell sort improves to about $O(n^{1.3})$ to $O(nlogn)$ , depending on the gap sequence used.

If you are interested in how the time complexity are derived, I recommend reading Introduction to Algorithms. In practice, the difference in performance becomes noticeable when the input size exceeds around 1,000 elements.

Let us consider the following concrete problem:

You are given the integer scores of 10,000 engineers, arranged in random order.

Write a program that pairs engineers whose scores are close to each other.

One possible approach is:

Sort the engineers by score
Pair adjacent elements in the sorted list

If insertion sort is used for step 1, the number of operations can reach up to one billion in the worst case, since its worst-case time complexity is $O(n^2)$ .

By contrast, when Shell sort is applied, the average time complexity improves to approximately $O(n^{1.3})$ to $O(nlogn)$ , depending on the gap sequences.

As you may notice, Shell sort is designed to address the inefficiency of insertion sort, particularly when dealing with large input sizes.

Shell sort Approach

Before I explain the shell sort method, let me first describe how insertion sort works.

Insertion sort approach

For each index $i$ from $1$ to $n - 1$ , insert element $A_i$ into the sorted position of the array.
Store the value of $A_i$ in a temporary variable $x$ .
While $A_j > x$ , shift $A_j$ one position to the right.
Insert $x$ into $A_{j+1}$ .

Insertion sort can be viewed as a special case of Shell sort where the gap size is $1$ .

Therefore, a generalized version of insertion sort naturally leads to the Shell sort algorithm.

In more detail, the approach can be extended as follows:

Shell Sort Approach

Choose an initial gap value $g$ .
For each index $i$ from $g$ to $n - 1$ , insert element $A_i$ into its correct position among elements spaced $g$ apart.
Store the value of $A_i$ in a temporary variable $x$ .
While $A_j > x$ , shift $A_j$ to $A_{j+g}$ .
Insert $x$ into $A_{j+g}$ .
Iterate steps 2-5 while gradually reducing the gap until it becomes $1$ .

In the next section, I will implement this approach in practical code.

Implementation of shell sort

Pattern 1: Gap Sequence Provided as Input

def    insertion_sort(array, n, gap):
    for i in range(gap, n):
        # Store the value of A[i] in a temporary variable x
        x = array[i]

        j = i - gap

        while j >= 0 and array[j] > x:
            # Shift A[j] to A[j+gap]
            array[j + gap] = array[j]
            j -= gap

        # Insert x into A[j+gap]
        array[j + gap] = x

def    shell_sort(array, n, gap_sequence):
    for gap in gap_sequence:
        insertion_sort(array, n, gap)

, where $n$ denotes the number of elements in the array.

Pattern 2: Gap Sequence Generated Within the Algorithm

def    insertion_sort(array, n, gap):
    for i in range(gap, n):
        # Store the value of A[i] in a temporary variable x
        x = array[i]

        j = i - gap

        while j >= 0 and array[j] > x:
            # Shift A[j] to A[j+gap]
            array[j + gap] = array[j]
            j -= gap

        # Insert x into A[j+gap]
        array[j + gap] = x

def    shell_sort(array, n):
    # Create an array to store the gap values.
    gap_sequence = []

    # Initialize the first gap as n // 2
    gap = n // 2

    while gap > 0:
        gap_sequence.append(gap)
        # Gradually reduce the gap until it reaches 1.
        gap //= 2
    if not gap_sequence:
        gap_sequence.append(1)

    for gap in gap_sequence:
        insertion_sort(array, n, gap)

This is concludes the article.

As a final note, the optimal gap sequence for Shell sort remains an open problem.
If you are interested in this topic, you may find it rewarding to explore how different gap sequences perform across various datasets.

If you notice any mistakes, including typos, I would be happy to revise them.
Please feel free to share your feedback through the contact form.

See you in the next article 👋

DEV Community