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 Summary

    Constructors
    Constructor
    Description
    Shellsort()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    sort(int[] elements)
    Sorts the elements in-place silently.
    void
    sort(int[] elements, boolean trace)
    Sorts the elements in-place, optionally emitting step-by-step traces to visualize the algorithmic progression.

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • Shellsort

      public Shellsort()

  • Method Details

    • sort

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

    • sort

      public void sort(int[] elements, boolean trace)
      Description copied from interface: SortingAlgorithm
      Sorts the elements in-place, optionally emitting step-by-step traces to visualize the algorithmic progression.
      Specified by:
      sort in interface SortingAlgorithm
      Parameters:
      elements - The array of integers to be sorted.
      trace - If true, logs the internal state during execution.