Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
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++
#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;
}
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);
}
}
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)
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
}
}
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;
}
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;
}
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
}
}
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.
