| Insertion Class |
The Insertion class provides static methods for sorting an array using insertion sort.
This implementation makes ~ 1/2 N^2 compares and OrderHelper.Exchanges in the worst case, so it is not suitable for sorting large arbitrary arrays. More precisely, the number of OrderHelper.Exchanges is exactly equal to the number of inversions. So, for example, it sorts a partially-sorted array in linear time.
The sorting algorithm is stable and uses O(1) extra memory.
See InsertionPedantic.java for a version that eliminates the compiler warning.
Inheritance HierarchyNamespace: Algs4Net
Assembly: Algs4Net (in Algs4Net.dll) Version: 1.0.0.0 (1.0.0.0)
Syntaxpublic class Insertion
The Insertion type exposes the following members.
Methods| Name | Description | |
|---|---|---|
  | IndexSort |
Returns a permutation that gives the elements in the array in ascending order,
while not changing the original array a[] |
| MainTest |
Reads in a sequence of strings from standard input; insertion sorts them;
and prints them to standard output in ascending order. |
| Sort(IComparable) |
Rearranges the array in ascending order, using the natural order. |
| Sort(Object, Comparer) |
Rearranges the array in ascending order, using a comparator. |
| Sort(IComparable, Int32, Int32) |
Rearranges the subarray a[lo..hi] in ascending order, using the natural order. |
| SortT(T, Int32, Int32, ComparerT) |
Rearranges the subarray a[lo..hi] in ascending order, using a generic comparator. |
RemarksThis class is a C# port from the original Java class Insertion implementation by Robert Sedgewick and Kevin Wayne.
See Also