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?

1

Initialize the value of gap size, say gap.

2

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

3

Sort these sub-lists using insertion sort.

4

Repeat this step 2 until the list is sorted.

5

Print a sorted list.

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;
}

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)