Shell Sort

Shell Sort is an efficient sorting algorithm that falls under the category of insertion sort. It was developed by Donald Shell in 1959, and is a type of comparison sort. Shell Sort works by comparing elements that are far apart, and then gradually reducing the gap between the elements until the array is eventually sorted. This technique allows Shell Sort to move larger elements to their correct positions more quickly than other sorting algorithms.

Shell Sort is a general-purpose sorting algorithm that is relatively simple to understand and implement. It works by comparing elements that are far apart and then gradually reducing the gap between the elements until the array is eventually sorted. This article will provide a detailed explanation of how Shell Sort works, as well as its time and space complexities. We will also provide a python code example for each of the topics covered.

How Does Shell Sort Work?

Shell Sort is a sorting algorithm that works by comparing elements that are far apart and gradually reducing the gap between the elements until the array is eventually sorted. It works by first comparing elements that are far apart, and then gradually reducing the gap between the elements until the array is eventually sorted.

First, the array is divided into subarrays. Each subarray consists of elements with a certain gap between them. The gap is usually set to be the length of the array divided by 2. The array is then sorted using insertion sort. After the insertion sort is complete, the gap is decreased by half and the process repeats. This process is repeated until the gap is 1 and the array is sorted.

Let’s look at an example to understand how Shell Sort works. Consider the following array of integers:

[5, 4, 1, 8, 7, 2, 9, 6, 3]

We will use a gap of 4 for this example. The array is then divided into subarrays with the following elements:

Subarray 1: [5, 1, 7, 9]

Subarray 2: [4, 8, 2, 6]

Subarray 3: [3]

We then sort each of the subarrays using insertion sort. The sorted subarrays are as follows:

Subarray 1: [1, 5, 7, 9]

Subarray 2: [2, 4, 6, 8]

Subarray 3: [3]

Now, we reduce the gap to 2. The array is then divided into subarrays with the following elements:

Subarray 1: [1, 5, 7]

Subarray 2: [2, 4, 6, 8]

Subarray 3: [3]

We then sort each of the subarrays using insertion sort. The sorted subarrays are as follows:

Subarray 1: [1, 5, 7]

Subarray 2: [2, 4, 6, 8]

Subarray 3: [3]

Finally, we reduce the gap to 1. The array is then divided into subarrays with the following elements:

Subarray 1: [1, 5, 7]

Subarray 2: [2, 4, 6]

Subarray 3: [3, 8]

We then sort each of the subarrays using insertion sort. The sorted subarrays are as follows:

Subarray 1: [1, 5, 7]

Subarray 2: [2, 4, 6]

Subarray 3: [3, 8]

After the subarrays are sorted, the array is combined and sorted using insertion sort. The final sorted array is:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

Time Complexity of Shell Sort

The time complexity of Shell Sort depends on the gap sequence used. The best case time complexity is O(n). This occurs when the gap sequence is defined as 2^k – 1, where k is the number of elements in the array.

The average time complexity of Shell Sort is O(n^2). This occurs when the gap sequence is defined as 2^k – 1, where k is the number of elements in the array.

The worst case time complexity of Shell Sort is O(n^2). This occurs when the gap sequence is defined as 2^k – 1, where k is the number of elements in the array.

Space Complexity of Shell Sort

The space complexity of Shell Sort is O(1). This is because the algorithm does not require any additional storage space other than the array being sorted.

Python Code Example

Now that we have a good understanding of how Shell Sort works, the time and space complexities, let’s look at a Python code example.

# Function to sort the array 
def shellSort(arr):
    # Start with a big gap, then reduce the gap 
    n = len(arr) 
    gap = n//2
  
    # Do a gapped insertion sort for this gap size. 
    # The first gap elements a[0..gap-1] are already in gapped  
    # order keep adding one more element until the entire array 
    # is gap sorted 
    while gap > 0: 
  
        for i in range(gap,n): 
  
            # add a[i] to the elements that have been gap sorted 
            # save a[i] in temp and make a hole at position i 
            temp = arr[i] 
  
            # shift earlier gap-sorted elements up until the correct 
            # location for a[i] is found 
            j = i 
            while j >= gap and arr[j-gap] > temp: 
                arr[j] = arr[j-gap] 
                j -= gap 
  
            # put temp (the original a[i]) in its correct location 
            arr[j] = temp 
        gap //= 2

# Driver Code 
arr = [ 5, 4, 1, 8, 7, 2, 9, 6, 3 ] 
  
shellSort(arr) 
  
print ("Sorted array:") 
for i in range(len(arr)): 
    print(arr[i]), 

Conclusion

In this article, we discussed Shell Sort, a type of comparison sorting algorithm. We discussed how it works, its time and space complexities, and provided a Python code example. We hope this article provided a clear understanding of Shell Sort and its various aspects.

Exercises

def shellSort(arr): 
    n = len(arr) 
    gap = n//2
  
    while gap > 0: 
        for i in range(gap,n): 
            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

def shellSort(arr, gap_sequence): 
    n = len(arr) 
  
    for gap in gap_sequence: 
        for i in range(gap,n): 
            temp = arr[i] 
            j = i 
            while j >= gap and arr[j-gap] > temp: 
                arr[j] = arr[j-gap] 
                j -= gap 
            arr[j] = temp 

def shellSortTimeComplexity(arr): 
    n = len(arr) 
    gap = n//2
  
    time_complexity = 0
  
    while gap > 0: 
        for i in range(gap,n): 
            time_complexity += 1
            temp = arr[i] 
            j = i 
            while j >= gap and arr[j-gap] > temp: 
                arr[j] = arr[j-gap] 
                j -= gap 
                time_complexity += 1
            arr[j] = temp 
        gap //= 2
  
    return time_complexity

def shellSortSpaceComplexity(arr): 
    n = len(arr) 
  
    space_complexity = 0
  
    for i in range(n): 
        space_complexity += 1
  
    return space_complexity

def shellSort(arr): 
    n = len(arr) 
    gap = n//2
  
    while gap > 0: 
        for i in range(gap,n): 
            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
  
arr = [ 5, 4, 1, 8, 7, 2, 9, 6, 3 ] 
  
shellSort(arr) 
  
print ("Sorted array:") 
for i in range(len(arr)): 
    print(arr[i]),