Shell Sort

Summary: In this tutorial, we will learn what Shell Sort Algorithm is, how it works and how to sort an array using the Shell Sort Algorithm in C, C++, and Java.

Introduction to Shell Sort Algorithm

Shell Sort is an optimization of insertion sort that allows the exchange of items that are far apart.

Wikipedia

Shell Sort Algorithm introduces a gap in the sorting process which quickly reduces the amount of disorder in the array compared to the insertion sort algorithm.

In Insertion sort, the value of the gap is one. That’s why in insertion sort we compare an array element with its adjacent element of 1 index far way.

But in shell sort instead of comparing the values one index away, we compare values with the index difference of gap=length/2 and decrease the gap value successively.

Beginning with a large gap value leaves less work for smaller gap values to finish the sorting process.

When the gap reduces to 1, the shell sort behaves as insertion sort.

Here is the illustration of how shell sorts works:

Shell sort with gap of 3
shell sort with gap of 4

Shell Sort Algorithm

  1. Initialize gap=(size_of_array/2).
  2. Loop from j=gap to i<size_of array.
  3. while (arr[j-gap] > arr[j] && j>=gap) swap (arr[j-gap], arr[j]).
  4. End Loop.
  5. Update gap=gap/2 and repeat for gap>=1 from step-1.

Here is the implementation of the shell sort algorithm in C, C++, and Java:

C

#include <stdio.h>
#include <stdlib.h>
int main()
{
    int arr[] = {5, -35, 8, 56, 54, 11 ,-1};
    int sizeArr = sizeof(arr)/sizeof(arr[0]);
 
    for(int gap=(sizeArr/2); gap>=1; gap=gap/2){
        for(int j=gap; j<sizeArr; j++){
            int currentElement = arr[j];
            while(arr[j-gap] > currentElement && j>=gap ){
                arr[j]=arr[j-gap];
                j=j-gap;
            }
            arr[j] = currentElement;
        }
    }
 
    for(int i=0; i<sizeArr; i++){
        printf("%d ",arr[i]);
    }
 
    return 0;
}

C++

#include <iostream>
using namespace std;
 
int main()
{
    int arr[] = {5, -35, 8, 56, 54, 11 ,-1};
    int sizeArr = sizeof(arr)/sizeof(arr[0]);
 
    for(int gap=(sizeArr/2); gap>=1; gap=i/2){
        for(int j=gap; j<sizeArr; j++){
            int currentElement = arr[j];
            while(arr[j-gap] > currentElement && j>=gap ){
                arr[j]=arr[j-gap];
                j=j-gap;
            }
            arr[j] = currentElement;
        }
    }
 
    for(int i=0; i<sizeArr; i++){
        cout << arr[i]<< " ";
    }
    return 0;
}

Java

public class ShellSort{
    public static void main(String args[]){
        int arr[] = {5, -35, 8, 56, 54, 11 ,-1};
        int sizeArr = arr.length;
 
        for(int gap=(sizeArr/2); gap>=1; gap=i/2){
            for(int j=gap; j<sizeArr; j++){
                int currentElement = arr[j];
                while(j>=gap && arr[j-gap] > currentElement ){
                    arr[j]=arr[j-gap];
                    j=j-gap;
                }
                arr[j] = currentElement;
            }
        }
 
        for(int i=0; i<sizeArr; i++){
            System.out.print(arr[i]+" ");
        }
    }
}

Output

-35 -1 5 8 11 54 56

Shell Sort Overview

  • In-place algorithm: No extra array is used
  • O(n²) worst-case time complexity: The time complexity depends on the gap value.
  • Unstable algorithm: Duplicates numbers are not interchanged.

In this tutorial, we learned what is shell sort algorithm, how it works and how to sort an array in C, C++, and Java using shell sort algorithm.

You May Also Like:

This Post Has One Comment

  1. mongchaihla June 29, 2023 Reply

    Your shell sort program in c++ has a bug.
    This is :for(int gap=(sizeArr/2); gap>=1; gap= ” i ” /2)
    there is i wrong;
    there has be gap;
    also the full code to be :
    public static void main(String[] args) {
    int arr []={54,545,-56,451,56};
    for(int gap=(arr.length/2); gap>=1; gap=gap/2){
    for(int j=gap; j=gap && arr[j-gap] > currentElement ){
    arr[j]=arr[j-gap];
    j=j-gap;
    }
    arr[j] = currentElement;
    }
    }

    for(int i=0; i<arr.length; i++){
    System.out.print(arr[i]+" ");
    }
    }

Leave a Reply