Question 83 : Implement shell sort in java?

Shell sort is in place comparison based sorting algorithm. It is generalization of insertion sort. It was invented by Donald shell.

It allows to sort elements which are far apart. In case of insertion sort, comparison happens between only adjacent elements but in shell sort, it avoid comparing adjacent elements until last steps. 

Last step of shell sort is ultimately insertion sort.
In short, it improves insertion sort by comparison and exchange elements that are far away.

Shell sort uses a sequence that can be referred as increment sequence. Shell sort makes multiple passes over array and sort number of equally sized array using insertion sort

Java program to implement shell sort:

import java.util.Arrays;

public class ShellSortMain {
    public static void main(String[] args) {
        int[] array = {
            22,
            53,
            33,
            12,
            75,
            65,
            887,
            125,
            37,
            977
        };
        System.out.println("Before Sorting : ");
        System.out.println(Arrays.toString(array));
        System.out.println("===================");
        System.out.println("After Sorting : ");
        array = shellsort(array);
        System.out.println(Arrays.toString(array));
    }

    private static int[] shellsort(int[] array) {

        // first part uses the Knuth's interval sequence
        int h = 1;
        while (h <= array.length / 3) {
            h = 3 * h + 1; // h is equal to highest sequence of h<=length/3
            // (1,4,13,40...)
        }

        // next part
        while (h > 0) { // for array of length 10, h=4

            // This step is similar to insertion sort below
            for (int i = 0; i < array.length; i++) {

                int temp = array[i];
                int j;

                for (j = i; j > h - 1 && array[j - h] >= temp; j = j - h) {
                    array[j] = array[j - h];
                }
                array[j] = temp;
            }
            h = (h - 1) / 3;
        }
        return array;
    }

}

When you run above program, you will get below output:

Before Sorting : 
[22, 53, 33, 12, 75, 65, 887, 125, 37, 977]
===================
After Sorting : 
[12, 22, 33, 37, 53, 65, 75, 125, 887, 977]

Option 2

public class ShellSort {
    
    // Method to sort array using Shell Sort
    public void sort(int[] arr) {
        int n = arr.length;
        
        // Start with a large gap, then reduce the gap
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // Perform a gapped insertion sort for this gap size
            for (int i = gap; i < n; i++) {
                // Save the current element to be positioned
                int temp = arr[i];
                
                // Shift elements of arr[0...i-gap] that are greater than temp
                // to one position ahead of their current position
                int j;
                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                
                // Place temp in its correct location
                arr[j] = temp;
            }
        }
    }

    // Method to print the array
    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

    // Main method to test the Shell Sort algorithm
    public static void main(String[] args) {
        int[] arr = {12, 34, 54, 2, 3};
        
        System.out.println("Original array:");
        printArray(arr);
        
        ShellSort shellSort = new ShellSort();
        shellSort.sort(arr);
        
        System.out.println("Sorted array:");
        printArray(arr);
    }
}

Explanation of Shell Sort Steps

1. Gap Sequence: The initial gap is set to n / 2, where n is the array length. The gap is reduced by half each time (gap /= 2) until it reaches 1.
2. Gapped Insertion Sort:
   • For each gap size, the algorithm performs an insertion sort on elements spaced by the gap.
   • Starting from the first element at index gap, it picks the element at each position i and inserts it into its correct position among elements spaced by gap to the left of it.
3. Shifting Elements:
   • Within each gapped insertion sort, if an element at position j - gap is greater than the current element temp, it is shifted to the right by gap, making space to insert temp in

Time complexity:
Best case: O(n)
Average case: Depends on gaps
Worst case : o(nlog2n)

Don't miss the next article! 

Be the first to be notified when a new article or Kubernetes experiment is published.                            

 

 Share This

• Facebook

• Twitter

• Linkedin

• Pinterest