← Back to Data Structures and Algorithms in Python

1. Introduction

Shell Sort is an optimization over insertion sort. It's an in-place comparison sort that improves its performance by comparing elements separated by a gap of several positions. This allows elements with the correct order to move faster to their designated position, reducing the total number of operations compared to the traditional insertion sort.

2. Implementation Steps

1. Choose a gap sequence. A common choice is to start with the array length divided by 2 and keep halving the gap until it becomes 1.

2. Sort the elements separated by the chosen gap.

3. Reduce the gap and repeat the process until the gap becomes 1. At this point, the array is sorted using a standard insertion sort.

3. Implementation in Python

def shell_sort(arr):
    """Function to perform Shell Sort on an array"""
    n = len(arr)
    gap = n // 2
    # Gap reduces by half each iteration
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            # Sort the sub-array for this gap
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2
arr = [12, 34, 54, 2, 3]
shell_sort(arr)
print(arr)

Output:

[2, 3, 12, 34, 54]

Explanation:

1. The shell_sort function starts with an initial gap which is half the length of the array.

2. For each gap, the function sorts the sub-arrays formed by the elements separated by the gap. This is done using a modified insertion sort.

3. After sorting the sub-arrays for a given gap, the gap is halved and the process is repeated.

4. The process continues until the gap becomes 1. At this point, the array is nearly sorted, and a final pass of insertion sort finishes the sorting process.

The performance of Shell Sort is heavily dependent on the gap sequence chosen. Different sequences can yield different performances, but in general, Shell Sort is more efficient than simple insertion sort.