Shell Sort Algorithm and Code in Javascript

The Shell Sort algorithm is basically extended from or variation of insertion algorithm. In the Insertion algorithm, we used to compare and swap two adjacent values from given input values. But in the Shell Sort algorithm, we select and swap distance values or values that are not adjacent or have more gap than one.

This algorithm is basically inherited properties from Insertion algorithm as its last step is insertion algorithm. Shell Sorting algorithm works on gap or distance or interval in between input values.

The formula used to find the gap is (gap= n/2), where n is a total number of values that are divided by 2 to get the value of gap. We continue applying this formula until we get gap value 1 that is the last step of this algorithm totally based on Insertion algorithm.

Flow Chart of Shell Sort in Javascript

STEP#01

Find out the total number of input values that is n. To find gap use formula that is (gap=n/2) but make sure the value of gap must be less than the total number of values (gap<n).

Step#02

Next step is to compare input values according to the gap value. Start comparison from the left side. If the value on the left side is greater than the value on the right in then swap values. If the value on the left side is lesser than the value on the right side then don’t swap values.

Step#03

After the first pass again divide the current gap value with 2 to get a new gap value and repeat the same process with new gap value until you get gap value 1.

Step#04

When you get gap value 1 then apply simple Insertion algorithm to get final sorted values.

Pseudo code of Shell Sort Algorithm in Javascript

Method sortshell(){

            Array  = List of input in an array;

Variable gap = array.length/2;

While(gap>0){        

            For(Integer i = gap; i is less than array.lenght; increment i )

                        {

                                    Create a temporary variable as container;

                                    While(value of i - gap > value of temporary variable ){

                                                Swap values;

                                    }

                                    }

                        gap = gap/2;

}

}

Method sortshell(){

Array = List of input in an array;

Variable gap = array.length/2;

While(gap>0){

For(Integer i = gap; i is less than array.lenght; increment i )

{

Create a temporary variable as container;

While(value of i - gap > value of temporary variable ){

Swap values;

}

gap = gap/2;

}

How does Shell Algorithm work?

Let’s suppose we have input values of 41, 2, 33, 11and 24 in an array. We have to sort these values using Shell Sorting Algorithm.

First, find N (Total number of values) = 5

Find gap using formula (N/2) = 5/2 = 2

Shell Sort Algorithm in Javascript — According to our gap value that is 2, starting from left 41, 33 and 24 will be compared with each other and will be swap according to rule.

Now, 24 is compared with 41, and 41 greater than 24. So, these values will be swiped until 24 gets at index 0, 33 at index 2 and 41 at index 4.

Now 2 and 11 will be compared and they will not swap with each other as 2 is smaller than 11.

After this gap will be reduced to 1 by applying formula again on gap value so the next step is applying the Insertion Algorithm from which you will get final sorted values.

SO the output is = 2, 11, 24, 33, 41

Shell Sort Code in Javascript

Let’s see a small part of the Shell Sort Code for better understanding.

function sorting() {
		var array = [41, 2, 33, 11, 24];  
    		var gap = arrayy.length / 2;
    		while (gap > 0) {
        		for (int x = gap; x < array.length; x++) {
            		var y = x;
            		var container = array[x];
    
while (y >= gap && array[y-gap] > container) {
                			array[y] = array[y-gap];
                			y = y - gap;
            		}
    
            array[y] = container;
        		}
    		gap = gap/2;
        
    }
	window.alert(array);
}

function sorting() {

var array = [41, 2, 33, 11, 24];

var gap = arrayy.length / 2;

while (gap > 0) {

for (int x = gap; x < array.length; x++) {

var y = x;

var container = array[x];

while (y >= gap && array[y-gap] > container) {

array[y] = array[y-gap];

y = y - gap;

}

array[y] = container;

}

gap = gap/2;

}

window.alert(array);

}

Output

Sorted Output: 2, 11, 24, 33, 41