Shell Sort Implementation in Python

Shell sort is a sorting algorithm that improves upon the insertion sort algorithm by breaking the original list into smaller sublists and sorting them using insertion sort. The sublists are created by choosing a gap value, which determines how many elements apart each element to be compared will be. The gap value is gradually decreased until the sublist is just the original list, at which point the algorithm becomes equivalent to insertion sort.

How Shell Sort Algorithm Works?

The shell sort algorithm can be summarized in the following steps:

1. Choose a gap value.
2. Starting from the first element, compare every element with the element gap places away. If the gap is 3, compare element 0 with element 3, element 1 with element 4, etc.
3. If the element gap places away is smaller than the current element, swap the two elements.
4. Continue comparing elements with the element gap places away until the end of the list is reached.
5. Repeat the above steps with a smaller gap value until the gap value is 1.

The idea is that by first sorting elements far apart from each other, smaller elements can bubble up to the top faster, reducing the total number of swaps needed.

Shell Sort Algorithm Implementation in Python

Here’s an implementation of the shell sort algorithm in Python:

def shell_sort(arr):
    # Start with a gap value of half the length of the list
    gap = len(arr) // 2
    
    # Keep reducing the gap value until it's 1
    while gap > 0:
        # Do a gapped insertion sort for this gap size.
        for i in range(gap, len(arr)):
            temp = arr[i]
            j = i
            
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
                
            arr[j] = temp
        
        gap //= 2
    
    return arr

The above code starts with a gap value of half the length of the input list, then gradually reduces the gap value to 1 by dividing it by 2 at the end of each iteration. At each iteration, the algorithm performs an insertion sort with the current gap value by comparing elements that are gap places apart. If an element gap places away is smaller than the current element, they are swapped. The algorithm repeats this process for each element in the list until it is sorted.

Time and Space Complexity

The time complexity of the shell sort algorithm depends on the gap sequence used. The best known sequence is the Pratt sequence, which has a time complexity of O(nlogn^2). The space complexity of the shell sort algorithm is O(1), as it sorts the list in place.

Example Run

Let’s run the above implementation of the shell sort algorithm on an input array of integers:

arr = [64, 34, 25, 12, 22, 11, 90]

sorted_arr = shell_sort(arr)

print("Sorted Array:", sorted_arr)

The output of the above code should be:

Sorted Array: [11, 12, 22, 25, 34, 64, 90]

The above code sorts the input array using the shell sort algorithm and prints the sorted array. As expected, the sorted array is in ascending order.

Conclusion

Shell sort is a sorting algorithm that improves upon the insertion sort algorithm by breaking the original list into smaller sublists and sorting them using insertion sort with decreasing gap values. The shell sort algorithm has a time complexity of O(nlogn^2) when using the Pratt sequence, and a space complexity of O(1). It can be a good choice for sorting lists of moderate size or for sorting data that is nearly sorted to begin with.