Implementing Shell Sort Algorithm in Java¶

1. What is Shell Sort?¶

Shell Sort is an improved version of Insertion Sort. While regular Insertion Sort is efficient when the array is nearly sorted, it requires excessive shifting operations if the array is reverse-ordered. Shell Sort addresses this by grouped insertion, first making the array partially sorted and then using Insertion Sort for the final full sort, thereby reducing the number of shifts and improving efficiency.

2. Core Idea¶

The key of Shell Sort is the introduction of a “step size (Gap)”. The array is divided into several subsequences, and each subsequence is sorted using Insertion Sort. The step size is then gradually reduced, and the process repeats until the step size becomes 1 (equivalent to regular Insertion Sort).

• Grouping: With a step size of gap, the array is divided into gap independent subsequences. Elements in each subsequence have indices following i, i+gap, i+2gap... (e.g., for gap=2, subsequences are [0,2,4], [1,3]).
• Insertion Sort: Each subsequence is sorted individually using Insertion Sort.
• Reduce Step Size: Start with gap = length/2, then halve it (gap = gap/2) each time until gap=0.

3. Algorithm Steps¶

1. Initialize Step Size: gap = length of array / 2.
2. Grouped Insertion Sort: Perform Insertion Sort on each subsequence (traverse elements and insert each into its correct position within the subsequence).
3. Reduce Step Size: gap = gap / 2, repeat Step 2 until gap=0.

4. Java Code Implementation¶

public class ShellSort {
    // Main method for Shell Sort
    public static void shellSort(int[] arr) {
        int n = arr.length;
        // Start with gap = n/2, reduce by half each iteration
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // Perform insertion sort on each subsequence
            for (int i = gap; i < n; i++) {
                int temp = arr[i]; // Temporarily store current element
                int j;
                // Shift elements forward until correct position is found
                for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap) {
                    arr[j + gap] = arr[j]; // Shift elements right
                }
                arr[j + gap] = temp; // Insert the temporary element
            }
        }
    }

    // Test method
    public static void main(String[] args) {
        int[] arr = {12, 34, 54, 2, 3};
        System.out.println("Array before sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        shellSort(arr);

        System.out.println("\nArray after sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

5. Code Explanation¶

• Outer Loop: Controls the step size gap, starting at n/2 and halving each iteration until gap=0.
• Inner Loop: Processes each subsequence:
• temp = arr[i]: Saves the current element to avoid overwriting during shifting.
• for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap): Compares elements backward in the subsequence and shifts larger elements right.
• arr[j + gap] = temp: Inserts the temporary element into its correct position.

6. Example Demonstration¶

Using the array [12, 34, 54, 2, 3]:
1. Initial Gap: gap = 5/2 = 2. Subsequences: [12,54,3] and [34,2]. After sorting, the array becomes [3,2,12,34,54].
2. Reduced Gap: gap = 2/2 = 1. Equivalent to regular Insertion Sort, resulting in the fully sorted array [2,3,12,34,54].

7. Summary¶

Shell Sort improves efficiency over regular Insertion Sort by reducing shifts through grouping and gradually ordering the array. Focus on understanding the role of step size and grouped insertion logic. For further optimization, explore advanced step sequences like 3k+1.

Output:

Array before sorting:
12 34 54 2 3 
Array after sorting:
2 3 12 34 54