edu.stanford.math.plex

Class PlexSort

java.lang.Object

edu.stanford.math.plex.PlexSort

public class PlexSort
extends java.lang.Object

The PlexSort class provides a sorting routine that I'd prefer was part of the standard libraries.

Version:

$Id$

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	PlexSort.Comp Instances of the Comp inner class are used as comparison closures for the sorting routine comp_sort.
static class	PlexSort.CompL
static class	PlexSort.CompObj

Constructor Summary

Constructors

Constructor and Description
PlexSort()

Method Summary

Methods

Modifier and Type	Method and Description
static void	comp_sort(int[] x, int start, int len, PlexSort.Comp comp) Sort a subarray of an int[] using a comparison function.
static void	comp_sort(long[] x, int start, int len, PlexSort.CompL comp) Same as comp_sort(int[], int, int, Comp), but for arrays of long.
static void	comp_sort(java.lang.Object[] x, int start, int len, PlexSort.CompObj comp) Same as comp_sort(int[], int, int, Comp), but for arrays of Object.
static void	reverse_sort(int[] indices, double[] vals)
static void	reverse_sort(int[] indices, int[] vals)
static void	sort(int[] indices, double[] vals)
static void	sort(int[] indices, double[] vals, boolean reverse)
static void	sort(int[] indices, int[] vals)
static void	sort(int[] indices, int[] vals, boolean reverse)
static void	sort(int[] indices, int start, int end, double[] vals, boolean reverse)
static void	sort(int[] indices, int start, int end, int[] vals, boolean reverse) Take an array of indices and sort them by the values in an array.

Methods inherited from class java.lang.Object

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

Constructor Detail

PlexSort

public PlexSort()

Method Detail

comp_sort

public static void comp_sort(int[] x,
             int start,
             int len,
             PlexSort.Comp comp)

Sort a subarray of an int[] using a comparison function. The sort is not stable, but it uses no extra storage, and seems to be faster in practice then even insertion sort, although it doesn't have that algorithm's guarantee of optimal worst-case behavior.

This code is copied with trivial alterations from "Engineering a Sort Function", by Bentley and McIlroy. I have no idea why there isn't something like this already available in the class java.util.Arrays -- apparently the sort routines in that class are based on the same paper, but support for a comparison function has been removed.

Parameters:

x - int[] to sort.

start - Beginning of subarray to sort.

len - Length of the subarray of x to sort.

comp - PlexSort.Comp instance to use in sorting.

comp_sort

public static void comp_sort(long[] x,
             int start,
             int len,
             PlexSort.CompL comp)

Same as comp_sort(int[], int, int, Comp), but for arrays of long.

comp_sort

public static void comp_sort(java.lang.Object[] x,
             int start,
             int len,
             PlexSort.CompObj comp)

Same as comp_sort(int[], int, int, Comp), but for arrays of Object.

sort

public static void sort(int[] indices,
        int start,
        int end,
        int[] vals,
        boolean reverse)

Take an array of indices and sort them by the values in an array.

Parameters:

indices - An int[] of indices to be sorted.

start - The first entry in indices to be sort.

end - The first entry in indices to not be sorted.

vals - An array of integer values against which to sort indices.

reverse - A boolean which, if true, causes the indices to be sorted into decreasing order.

sort

public static void sort(int[] indices,
        int start,
        int end,
        double[] vals,
        boolean reverse)

sort

public static void sort(int[] indices,
        int[] vals,
        boolean reverse)

sort

public static void sort(int[] indices,
        int[] vals)

reverse_sort

public static void reverse_sort(int[] indices,
                int[] vals)

sort

public static void sort(int[] indices,
        double[] vals,
        boolean reverse)

sort

public static void sort(int[] indices,
        double[] vals)

reverse_sort

public static void reverse_sort(int[] indices,
                double[] vals)