Shell Sort : Complexity, Implementation, Applications, Explanation

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

Explanation
Complexity
Implementations
Applications
Discussions

Shellsort (also known as Shell sort or Shell's method) is an in-place comparison based sorting algorithm.

Shell Sort improves its time complexity by taking the advantage of the fact that using Insertion Sort on a partially sorted array results in less number of moves.

It is a generalization of:

sorting by exchange (bubble sort)
sorting by insertion (insertion sort)

Explanation

The idea is to arrange the list of elements so that, starting anywhere, considering every hth element gives a sorted list. Such a list is said to be h-sorted.
Note 1-sorted array is a sorted array.
Determine a gap sequence to work on.

If the gap sequence is (5,3,1) and the array consists of 14 elements (a1, a2, ..., a14), then, there are three passes.

In the first pass, the elements are grouped as (a1, a6, a11), (a2, a7, a12), (a3, a8, a13), (a4, a9, a14), (a5, a10). Each group is sorted using Insertion Sort.
In the second pass, the 3-sorting is performed on groups (a1, a4, a7, a10, a13), (a2, a5, a8, a11, a14), (a3, a6, a9, a12).
In the third (last) pass, 1-sorting is performed on (a1, a2, ..., a14).

Pseudocode of Shell Sort using Marcin Ciura's gap sequence, with an inner insertion sort:


# Sort an array a[0...n-1].
gaps = [701, 301, 132, 57, 23, 10, 4, 1]
# Start with the largest gap and work down to a gap of 1
foreach (gap in gaps)
{
    # 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
    for (i = gap; i < n; i += 1)
    {
        # add a[i] to the elements that have been gap sorted
        # save a[i] in temp and make a hole at position i
        temp = a[i]
        # shift earlier gap-sorted elements up until the correct location for a[i] is found
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
        {
            a[j] = a[j - gap]
        }
        # put temp (the original a[i]) in its correct location
        a[j] = temp
    }
}

Complexity

Worst case time complexity: Θ(N (log N)^2) comparisons
Average case time complexity: Θ(N (log N)^2) comparisons
Best case time complexity: Θ(N log N)
Space complexity: Θ(1).

Implementations

Implementation of Shell Sort algorithm in 8 language that includes C, C++, Java, Python, Go, JavaScript, C# and Swift.

C
C++
Java
Python
Go
JavaScript
C#
Swift

C


  #include <stdio.h>
// Part of Cosmos by OpenGenus Foundation
void shell_sort(int *a, int n)
{
  int i, j, gap, temp;
  /* Assess the array in gaps starting at half the array size - Each gap is a sublist of 2 values */
  for(gap = n/2 ; gap > 0 ; gap /= 2)
  {
    /* Index at the right value of each gap */
    for(i = gap ; i < n ; i++)
    {
      /* Take a copy of the value under inspection */
      temp = a[i];
      for(j = i ; j >= gap ; j-= gap)
      {
        /* Compare the values in the sub lists and swap where necessary */
        if(temp < a[j-gap])
          a[j] = a[j-gap];
        else
          break;
      }
      a[j] = temp;
    }
  }
}
int main(void)
{
  int i;
  int a[10] = { 5 , 211 , 66 , 7 , 12 , 2, 76 , 134 , 99 , 9 };
  printf("In: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  shell_sort(a, 10);
  printf("\nOut: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  return 0;
}
C
Copy

C++


#include <iostream>
#include <vector>
#include <algorithm> 
using namespace std;
// Part of Cosmos by OpenGenus Foundation
void shellSort(vector<int> &ar)
{
  size_t j;
  for (size_t gap = ar.size() / 2; gap > 0; gap /= 2)
    {
      for (size_t i = gap; i < ar.size(); i++)
      {
          int temp = ar[i];
          for (j = i; j >= gap && temp < ar[j - gap]; j -= gap)
          {
            ar[j] = ar[j - gap];
          }
          ar[j] = temp;
      } 
    }
}
int main()
{
  vector<int> inputArray;
  cout << "Enter the elements of the array: ";
  for(int i;cin>>i;)
  {
    inputArray.push_back(i);
  }
  shellSort(inputArray);
  for(size_t i=0;i<inputArray.size();i++)
  {
    cout<<inputArray[i]<<" ";
  }
  cout<<endl;
  return 0;
}
C++
Copy

Java


  // Java implementation of ShellSort
// Part of Cosmos by OpenGenus Foundation
class ShellSort
{
    /* An utility function to print array of size n*/
    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i<n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
    /* function to sort arr using shellSort */
    int sort(int arr[])
    {
        int n = arr.length;
        // Start with a big gap, then reduce the gap
        for (int gap = n/2; gap > 0; gap /= 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
            for (int i = gap; i < n; i += 1)
            {
                // add a[i] to the elements that have been gap
                // sorted save a[i] in temp and make a hole at
                // position i
                int temp = arr[i]; 
                // shift earlier gap-sorted elements up until
                // the correct location for a[i] is found
                int j;
                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                    arr[j] = arr[j - gap];
                 // put temp (the original a[i]) in its correct
                // location
                arr[j] = temp;
            }
        }
        return 0;
    }
     // Driver method
    public static void main(String args[])
    {
        int arr[] = {12, 34, 54, 2, 3};
        System.out.println("Array before sorting");
        printArray(arr);
        ShellSort ob = new ShellSort();
        ob.sort(arr);
        System.out.println("Array after sorting");
        printArray(arr);
    }
} 
Java
Copy

Python


  # Part of Cosmos by OpenGenus Foundation
def shell_sort(alist):
    sub_list_count = len(alist) // 2
    while sub_list_count > 0:
        for start in range(sub_list_count):
            gap_insertion_sort(alist, start, sub_list_count)
        sub_list_count = sub_list_count // 2
def gap_insertion_sort(alist, start, gap):
    for i in range(start + gap, len(alist), gap):
        currentvalue = alist[i]
        position = i
        while position >= gap and alist[position - gap] > currentvalue:
            alist[position] = alist[position - gap]
            position = position - gap
        alist[position] = currentvalue
alist = [91, 91, 82, 45, 48, 35, 83, 70, 97]
print("Before: ", alist)
shell_sort(alist)
print("After: ", alist)
Python
Copy

Go


  package main
import (
    "fmt"
)
func main() {
    var n int
    fmt.Println("Please enter the lenght of the array:")
    fmt.Scan(&n)
    X := make([]int, n)
    fmt.Println("Now, enter the elements X0 X1 ... Xn-1")
     for i := 0; i < n; i++ {
        fmt.Scanln(&X[i])
    }
    fmt.Printf("Unsorted array: %v\n", X)
    fmt.Printf("Sorted array: %v\n", BubbleSort(X))  
}
func shellSort(array []int) {
  h := 1
  for h < len(array) {
    h = 3 * h + 1
  }
  for h >= 1 {
    for i := h; i < len(array); i++ {
      for j := i; j >= h && array[j] < array[j - h]; j = j - h {
        algoutils.Swap(array, j, j - h)
      }
    }
    h = h/3
  }
}
Go
Copy

JavaScript


  // Part of Cosmos by OpenGenus Foundation
function shellSort (a) {
  for (var h = a.length; h > 0; h = parseInt(h / 2)) {
    for (var i = h; i < a.length; i++) {
      var k = a[i];
      for (var j = i; j >= h && k < a[j - h]; j -= h)
        a[j] = a[j - h];
      a[j] = k;
    }
  }
  return a;
}
JavaScript
Copy

C#


  /* Part of Cosmos by OpenGenus Foundation */
//
//  shell_sort.m
//  Created by DaiPei on 2017/10/9.
//
#import <Foundation/Foundation.h>
@interface ShellSort : NSObject
- (void)sort:(NSMutableArray<NSNumber *> *)array;
@end
@implementation ShellSort
- (void)sort:(NSMutableArray<NSNumber *> *)array {
    for (int h = (int)array.count / 2; h > 0; h /= 2) {
        for (int i = h; i < array.count; i++) {
            NSNumber *k = array[i];
            int j;
            for (j = i; j >= h && [k compare:array[j - h]] == NSOrderedAscending; j -= h) {
                array[j] = array[j - h];
            }
            array[j] = k;
        }
    }
}
@end
int main(int argc, const char * argv[]) {
    @autoreleasepool {
        int n = 0;
        NSLog(@"What is the size of the array?");
        scanf("%d", &n);
        NSMutableArray *array = [NSMutableArray arrayWithCapacity:n];
        NSLog(@"Enter elements of the array one by one:");
        for (int i = 0; i < n; i++) {
            int tmp;
            scanf("%d", &tmp);
            [array addObject:@(tmp)];
        }
        ShellSort *ss = [[ShellSort alloc] init];
        [ss sort:array];
        NSLog(@"%@", array);
    }
    return 0;
}
C#
Copy

Swift


/* Part of Cosmos by OpenGenus Foundation */
//
//  shell_sort.swift
//  Created by DaiPei on 2017/10/11.
//
import Foundation
func shellSort(_ array: inout [Int]) {
    var h = array.count / 2
    while h > 0 {
        for i in h..<array.count {
            let key = array[i]
            var j = i
            while j >= h && key < array[j - h] {
                array[j] = array[j - h]
                j -= h
            }
            array[j] = key
        }
        h /= 2
    }
}
Swift
Copy

Applications

Applications of Shell Sort includes:

Shellsort performs more operations and has higher cache miss ratio than quicksort.
However, since it can be implemented using little code and does not use the call stack, some implementations of the qsort function in the C standard library targeted at embedded systems use it instead of quicksort. Shellsort is, for example, used in the uClibc library. For similar reasons, an implementation of Shellsort is present in the Linux kernel.
Shellsort can also serve as a sub-algorithm of introspective sort, to sort short subarrays and to prevent a slowdown when the recursion depth exceeds a given limit. This principle is employed, for instance, in the bzip2 compressor.

Shell Sort

Sorting Algorithms shell sort