[Sorting] Shell Sort

In the final post, we looked into the selection sorting algorithm.

https://code-studies.tistory.com/124

[Sorting] Insertion Sort

 

In this post, we will check out shell sort. 

 

---

Shell Sort

 

Shell sort is a sorting algorithm that treats the input as a collection of interleaved lists, and sorts each list individually with a variant of the insertion sort algorithm.

 

Shell sort uses gap values to determine the number of interleaved lists.

A gap value is a positive integer representing the distance between elements in an interleaved list.

For each interleaved list, if an element is at index [i], the next element is at index [i + gap value].

 

Shell sort begins by choosing a gap value K and sorting K interleaved lists in place.

Shell sort finishes by performing a standard insertion sort on the entire array.

Because the interleaved parts have already been sorted, smaller elements will be close to the array's beginning and larger elements towards the end.

Insertion sort can then quickly sort the nearly-sorted array.

 

Any positive integer gap value can be chosen.

In the case that the array size is not evenly divisible by the gap value, some interleaved lists will have fewer items than others.

 

https://www.youtube.com/watch?v=qzXAVXddcPU&ab_channel=RunTimeClips

 

This video on YouTube visually demonstrates Shell Sort effectively.

 

 

As you can assume at this point, shell sorting ends up with the gap value K being 1. 

Shell sort tends to work better when we choose descending K value. 

 

A common option is to choose powers of 2 minus 1. (= 2 ^ t - 1)

Ex. If N = 100, K = 63, 31, 15, 7, 3, and 1

This gap selection technique results in shell sort's time complexity being no worse than O(N^3/2).

 

 

---

Python Implementation

 

def insertion_sort_interleaved(arr: list[int], startIndex: int, gap: int) -> None:
    for i in range(startIndex + gap, len(arr), gap):
        j = i
        
        while (j - gap >= startIndex) and arr[j] < arr[j-gap]:
            arr[j-gap], arr[j] = arr[j], arr[j-gap]
            j -= gap

def shell_sort(arr: list[int], gapValues: list[int]) -> None:
    for gap in gapValues:
        for startIndex in range(0, len(arr)):
            insertion_sort_interleaved(arr, startIndex, gap)

 

Implementation of shell sort into code is variation of insertion sort with different gap values. 

Compare the similarities of the code of shell sort and insertion sort to get a better understanding.