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.