Shell Sort

Shell sort is an in-place comparison-based sorting algorithm that generalizes insertion sort to allow the exchange of items that are far apart.

Introduction

It is the first algorithm to improve an insertion sort. Its idea was to avoid the large amount of data movement, first by comparing elements that were far apart and then by comparing elements that were less far apart and so on, gradually shinking toward the basic insertion sort.

The algorithm first sorts the elements that are far away and then subsequently reduces the gap between the elements. This gap is also known as intervals. The interval between the elements is reduced based on the sequence used. The performance of the shell sort depends on the type of sequence used for a given input array. Some of the optimal sequences that can be used in the shell sort algorithm are:

1. Shell's original sequence: N/2 , N/4 , …, 1
2. Knuth's increments: 1, 4, 13, …, (3k – 1) / 2
3. Hibbard's increments: 1, 3, 7, 15, 31, 63, 127, 255, 511…
and so on.

How Shell Sort Works?

Initialize the value of gap size, say gap.

Divide the list into smaller sub-part. Each must have equal intervals to gap.

Sort these sub-lists using insertion sort.

Repeat until the gap size becomes 1, then perform a final insertion sort.

The list is now sorted.

Pseudocode of Shell Sort

shellSort(array, size)
    for(gap = size/2; gap>0; gap/2){
        for(j = gap; j>size; j++){
            for(i = j-gap; i>=0; i-gap){
                if(array[i+gap] > array[i]) break
                swap(array[i+gap], array[i])
            }
        }
    }

Implementation of Shell Sort

// shellSort.cpp
#include <iostream>
#include <vector>
using namespace std;
void shellSort(vector<int> &arr)
{
int length = arr.size();
int gap = length / 2;
while (gap > 0)
{
    for (int j = gap; j < length; j++)
    {
        for (int i = j - gap; i >= 0; i -= gap)
        {
            if (arr[i + gap] > arr[i])
            {
                break;
            }
            else
            {
                swap(arr[i], arr[i + gap]);
            }
        }
    }
    gap /= 2;
}
return;
}

int main()
{
vector<int> array{23, 21, 15, 19, 31, 7, 9, 5, 2};
cout << "Unsorted Array: ";
for (int ele : array)
{
    cout << " " << ele;
}
shellSort(array);
cout << "\nSorted Array: ";
for (int ele : array)
{
    cout << " " << ele;
}
return 0;
}

#shellSort.py
def shellSort(arr):
 size = len(arr)
 gap = size//2

 while gap > 0:
     for j in range(gap, size):
         i = j - gap
         while i >= 0:
             if arr[i+gap] >= arr[i]:
                 break
             else:
                  arr[i], arr[i+gap] = arr[i+gap], arr[i]
             i -= gap
     gap //= 2             


arr = [23, 21, 15, 19, 31, 7, 9, 5, 2]
print("Unsorted Array: ",arr)
shellSort(arr)
print("Sorted Array: ", arr)

function shellSort(arr) {
 let size = arr.length
 let gap = Math.floor(size / 2)
 while (gap > 0) {
     for (let j = gap; j < size; j++) {
         for (let i = j - gap; i >= 0; i -= gap) {
             if (arr[i + gap] >= arr[i]) break
             else[arr[i + gap], arr[i]] = [arr[i], arr[i + gap]]
         }
     }
     gap = Math.floor(gap / 2)
 }
 return arr
}

let arr = [23, 21, 15, 19, 31, 7, 9, 5, 2]

console.log(`Unsorted Array: ${arr}`)
arr = shellSort(arr)
console.log(`Sorted Array: ${arr}`)

Time Complexity

Best Case:O(n logn), is the average case complexity.
Average Case:O(n logn), is the average case complexity.
Worst Case: O(n*n),is the worst-case complexity for shell sort.

Space Complexity

Constant Space:O(1)
Space Complexity:O(1)