Shell Sort in Java

Here you will get program for shell sort in Java.

Insertion sort is no doubt an efficient and fast sorting technique to sort a given set of values, but sometimes the insertion sort may be implemented in a comparatively complex manner if some “light” elements are used at the ends. For removing such problems, the shell sort was introduced by Donald Shell in 1959. It attempts to sort the data moving large elements towards one end and the smaller ones towards the other. In this method, instead of sorting the array all at once, it is divided into smaller segments. The shell sort is also called diminishing increment sort.

A general understanding of the algorithm:

Let us consider an example of a linear array (0-4 is the array indexes) – Here we will sort it in ascending order:

0	1	2	3	4	5	6	7	8
4	1	9	7	3	0	2	10	11

We consider the gap at which the arrays are to be considered. The gap should mandatorily be less than the total number of array indexes (Here 9). Gap = floor (N/2), here floor lets us select the smaller value of the outcome is a floating value.

For instance, here gap should be 4. The set gap is then decremented at each step as the sorting is performed, to better understand the concept of this gap, let us consider an example of the above array:

Gap=4 ; This means, if we consider the first element to be at index 0 then the next element should be at index 0+4 and thereafter at 4+4=8. If we consider an element at index 1, then the next element would be at gap 1+4 =5 and the next one at 5+4 =9; since the 9^th index do not exist for this example, we would consider the elements at index 0 and 1 only.

Working in brief:

We consider the elements at gap 4 that is at index: 0, 4 and 8.

0	1	2	3	4	5	6	7	8
4	1	9	7	3	0	2	10	11

Here, these are 4, 3 and 11.

The element at index 3 here denotes the end which basically denotes the index covered yet.

We then start comparing the elements to the right hand side of end, if the right hand side element is smaller than end, we swap the two elements, else we move to the next position of the array index and perform the same thing. For example, here:

Is 4>3? Yes, swap the elements 4 and 3.

Next, we would take the other set of elements at gap 4 apart and would continue this process of swapping the elements at gap 4 apart until we find that the end has reached the last index position or we have covered all the elements at the concerned gap. This would mean that one pass has been completed.

For the next pass we would take gap as:

Gap = floor (gap/2); so, in this instance gap would be reduced to 2. We would continue this process until the possible indexes are covered; we finally will receive a sorted list of values.

Program for Shell Sort in Java

import java.util.*;
public class ShellSortEx 
{
    public static final int SIZE = 5;
    public static int[] array = new int[SIZE];
    
    /**
    *Shell Sort Algorithm.
    **/
    public static void sort() 
    {
        int inc = array.length / 2;
        while (inc > 0) 
        {
            for (int i = inc; i < array.length; i++) 
            {
                int temp = array[i];
                int j = i;
             
                while (j >= inc && array[j - inc] > temp) 
                {
                    array[j] = array[j - inc];
                    j = j - inc;
                }
                array[j] = temp;
            }
            if (inc == 2)
                inc = 1;
            else
                inc *= (5.0 / 11);
 
        }
    }
 
    public static void main(String args[]) 
    {
        System.out.println("Enter 5 Elements");
 
        Scanner key = new Scanner(System.in);
        for (int i = 0; i < SIZE; i++)
            array[i] = key.nextInt();
 
        System.out.println("\nOriginal array: ");
        for (int i = 0; i < array.length; i++)
            System.out.print(array[i] + " ");
 
        System.out.println("\nSorted array: ");
        sort();
        for (int i = 0; i < array.length; i++)
            System.out.print(array[i] + " ");
    }
}

import java.util.*;

public class ShellSortEx

{

public static final int SIZE = 5;

public static int[] array = new int[SIZE];

/**

*Shell Sort Algorithm.

**/

public static void sort()

{

int inc = array.length / 2;

while (inc > 0)

{

for (int i = inc; i < array.length; i++)

{

int temp = array[i];

int j = i;

while (j >= inc && array[j - inc] > temp)

{

array[j] = array[j - inc];

j = j - inc;

}

array[j] = temp;

}

if (inc == 2)

inc = 1;

else

inc *= (5.0 / 11);

}

public static void main(String args[])

{

System.out.println("Enter 5 Elements");

Scanner key = new Scanner(System.in);

for (int i = 0; i < SIZE; i++)

array[i] = key.nextInt();

System.out.println("\nOriginal array: ");

for (int i = 0; i < array.length; i++)

System.out.print(array[i] + " ");

System.out.println("\nSorted array: ");

sort();

for (int i = 0; i < array.length; i++)

System.out.print(array[i] + " ");

}

Output

Enter 5 Elements
22 5 8 12 9

Original array:
22 5 8 12 9
Sorted array:
5 8 9 12 22

Comment below if you have queries related to above java shell sort program.

Shell Sort in Java

Program for Shell Sort in Java

Related Posts

Leave a Comment Cancel Reply