Package smile.sort

Interface ShellSort

public interface ShellSort
Shell sort is a generalization of insertion sort. For n < 50, roughly, Shell sort is competitive with the more complicated Quicksort on many machines. For n > 50, Quicksort is generally faster.

Shell sort is based on two observations:

  • insertion sort is efficient if the input is "almost sorted", and
  • insertion sort is typically inefficient because it moves values just one position at a time.
Shell sort improves insertion sort by comparing elements separated by a gap of several positions. This lets an element take "bigger steps" toward its expected position. Multiple passes over the data are taken with smaller and smaller gap sizes. The last step of Shell sort is a plain insertion sort, but by then, the array of data is guaranteed to be almost sorted.

The original implementation performs O(n2) comparisons and exchanges in the worst case. A minor change given in V. Pratt's book improved the bound to O(n log2 n). This is worse than the optimal comparison sorts, which are O(n log n).

  • Method Summary

    Static Methods
    Modifier and Type
    Method
    Description
    static void
    sort(double[] x)
    Sorts the specified array into ascending numerical order.
    static void
    sort(float[] x)
    Sorts the specified array into ascending numerical order.
    static void
    sort(int[] x)
    Sorts the specified array into ascending numerical order.
    static <T extends Comparable<? super T>>
    void
    sort(T[] x)
    Sorts the specified array into ascending order.

  • Method Details

    • sort

      static void sort(int[] x)
      Sorts the specified array into ascending numerical order.
      Parameters:
      x - the array.

    • sort

      static void sort(float[] x)
      Sorts the specified array into ascending numerical order.
      Parameters:
      x - the array.

    • sort

      static void sort(double[] x)
      Sorts the specified array into ascending numerical order.
      Parameters:
      x - the array.

    • sort

      static <T extends Comparable<? super T>> void sort(T[] x)
      Sorts the specified array into ascending order.
      Type Parameters:
      T - the data type of array elements.
      Parameters:
      x - the array.