All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class com.sgi.sysadm.util.Sort

java.lang.Object
   |
   +----com.sgi.sysadm.util.Sort

public final class Sort

extends Object

Most methods operate on a range of elements. A range is described by the index of its first element and an index that is one past its last element. So, for example, [n, n+1) is a range that contains one element, [n, n) is a range that contains zero elements, and [n, n-1) is not a valid range.

Unless otherwise specified, the test for equality uses the == operator by default. Any different notion of equality may be represented as a BinaryPredicate. You can use the predefined class Equals, which implements BinaryPredicate, if you want to use the Object.equals() method.

See Also:

BinaryPredicate

Sort()

inplace_merge(Object[], int, int, int, BinaryPredicate)

Transforms two consecutive sorted ranges into a single sorted range.

insertion_sort(Object[], int, int, BinaryPredicate)

Sort a range of elements by a user-supplied comparison function.

lower_bound(Object[], int, int, Object, BinaryPredicate)

Performs a binary search on an already-sorted range: finds the first position where an element can be inserted without violating the ordering.

reverse(Object[], int, int)

Reverses a sequence of elements.

rotate(Object[], int, int, int)

Rotate a range in place: array[middle] is put in array[first], array[middle+1] is put in array[first+1], etc.

stable_sort(Object[], int, int, BinaryPredicate)

Sort a range of elements by a user-supplied comparison function.

upper_bound(Object[], int, int, Object, BinaryPredicate)

Performs a binary search on an already-sorted range: finds the last position where an element can be inserted without violating the ordering.

 public Sort()

 public static void stable_sort(Object array[],
                                int first,
                                int last,
                                BinaryPredicate comp)

Sort a range of elements by a user-supplied comparison function. The sort is stable---that is, the relative order of equal elements is unchanged. Worst case performance is N (log N)^2.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

comp - Comparison function.

 public static void insertion_sort(Object array[],
                                   int first,
                                   int last,
                                   BinaryPredicate comp)

Sort a range of elements by a user-supplied comparison function. Uses the insertion sort algorithm. This is a quadratic algorithm, but it is useful for sorting small numbers of elements.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

comp - Comparison function.

 public static void inplace_merge(Object array[],
                                  int first,
                                  int middle,
                                  int last,
                                  BinaryPredicate comp)

Transforms two consecutive sorted ranges into a single sorted range. The initial ranges are [first, middle) and [middle, last), and the resulting range is [first, last). Elements in the first input range will precede equal elements in the second. Sorting is by a user-supplied comparison function.

Parameters:

array - Array containing the ranges.

first - Beginning of the first range.

middle - One past the end of the first range, and beginning of the second.

last - One past the end of the second range.

comp - Comparison function.

 public static int lower_bound(Object array[],
                               int first,
                               int last,
                               Object x,
                               BinaryPredicate comp)

Performs a binary search on an already-sorted range: finds the first position where an element can be inserted without violating the ordering. Sorting is by a user-supplied comparison function.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

x - Element to be searched for.

comp - Comparison function.

Returns:

The largest index i such that, for every j in the range [first, i), comp.apply(array[j], x) is true.

 public static int upper_bound(Object array[],
                               int first,
                               int last,
                               Object x,
                               BinaryPredicate comp)

Performs a binary search on an already-sorted range: finds the last position where an element can be inserted without violating the ordering. Sorting is by a user-supplied comparison function.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

x - Element to be searched for.

comp - Comparison function.

Returns:

The largest index i such that, for every j in the range [first, i), comp.apply(x, array[j]) is false.

 public static void reverse(Object array[],
                            int first,
                            int last)

Reverses a sequence of elements.

Parameters:

array - Array containing the sequence

first - Beginning of the range

last - One past the end of the range

Throws: ArrayIndexOutOfBoundsException

If the range is invalid.

 public static void rotate(Object array[],
                           int first,
                           int middle,
                           int last)

Rotate a range in place: array[middle] is put in array[first], array[middle+1] is put in array[first+1], etc. Generally, the element in position i is put into position (i + (last-middle)) % (last-first).

Parameters:

array - Array containing the range

first - Beginning of the range

middle - Index of the element that will be put in array[first]

last - One past the end of the range

All Packages  Class Hierarchy  This Package  Previous  Next  Index