Class Shellsort

java.lang.Object
topics.sorting.shellsort.Shellsort
All Implemented Interfaces:
SortingAlgorithm
public class Shellsort extends Object implements SortingAlgorithm

Shellsort

An highly efficient optimization of Direct Insertion Sort. It overcomes the limitation of Insertion Sort (where elements only move one position at a time) by comparing and moving elements that are separated by a specific "gap". The gap is progressively reduced until it reaches 1, at which point the algorithm behaves exactly like a standard Insertion Sort, but on an array that is already nearly sorted.

Algorithm Steps

  1. Determine the initial gap size (e.g., N / 2).
  2. Perform a "gapped" insertion sort: compare elements separated by the gap.
  3. Shift elements separated by the gap to the right to make room for the key.
  4. Reduce the gap size (e.g., divide by 2) and repeat.
  5. The final pass is always performed with a gap of 1, guaranteeing a fully sorted array.

Complexity Analysis

  • Time Complexity: Highly dependent on the gap sequence. Using Shell's original sequence (N/2), the worst-case is O(N²). With Hibbard's or Knuth's sequences, it can drop to O(N^(3/2)) or O(N^(4/3)).
  • Space Complexity: O(1) - Sorts entirely in-place.
  • Stability: No - Elements leaping across large gaps will jump over equal elements, destroying relative order.
Author:
vicegd
See Also:
  • invalid reference 
    topics.sorting.SortingAlgorithm

  • Constructor Details

    • Shellsort

      public Shellsort()

  • Method Details

    • sort

      public void sort(int[] elements)
      Description copied from interface: SortingAlgorithm
      Sorts the elements in-place.
      Specified by:
      sort in interface SortingAlgorithm
      Parameters:
      elements - The array of integers to be sorted.