Shell Sort Algorithm in Java

1. Introduction

Shell Sort, also known as the diminishing increment sort, is an in-place comparison sort. It is a generalization of insertion sort that allows the exchange of elements that are far apart. The idea is to arrange the list of elements so that, starting anywhere, taking every hth element produces a sorted list. Such a list is said to be h-sorted.

2. Implementation Steps

1. Choose a gap h (typically half of the array size).

2. Perform an insertion sort for elements with an interval of h.

3. Reduce the value of h and repeat the process until h becomes 1. This will sort the entire list.

3. Implementation in Java

public class ShellSort {
    public void sort(int arr[]) {
        int n = arr.length;
        // Start with a gap of n/2, and reduce the gap until it becomes 1
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // Do a gapped insertion sort for this gap size
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j;
                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                    arr[j] = arr[j - gap];
                arr[j] = temp;
            }
        }
    }
    public static void main(String[] args) {
        int arr[] = { 23, 29, 15, 19, 31, 7, 9, 5, 2 };
        int n = arr.length;
        ShellSort ob = new ShellSort();
        ob.sort(arr);
        System.out.println("Sorted array:");
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}

Output:

Sorted array:
2 5 7 9 15 19 23 29 31

Explanation:

1. Initially, choose a gap of size h. For simplicity, this is usually taken as half the size of the list being sorted.

2. Next, perform an insertion sort on elements spaced h positions apart. This will create h different sub-arrays that are individually sorted.

3. The gap h is then reduced, and the process repeats. This continues until the entire list is sorted when h becomes 1.

4. With each reduction in gap size, the elements are closer to their final positions, thus reducing the total number of swaps and comparisons needed.