SortUtils
jhplot.math

Class SortUtils



  • public class SortUtilsextends Object
    Utility class providing some useful static sort methods. The sort routines all return index permutations p such that data[p[0]],..,data[p[data.length-1]] is in sorted order. The data array itself is not modified. To actually rearrange the array elements, the inverse of p can be used to permute the array, such that data[0],..,data[data.length-1] is in sorted order. Use getIterator(p, data) to iterate in sorted order. A code example may show you what to do next:
     String[] colors = { "red", "green", "blue" }; int[] p = SortUtils.sort(colors, new StringComparator()); // --> (colors[p[0]], colors[p[1]], colors[p[2]]) == ("blue","green","red") Iterator iter = SortUtils.getIterator(p, colors) // --> (iter.next(), iter.next(), iter.next()) == ("blue","green","red") SortUtils.permute(SortUtils.inverse(p), colors, true); // --> (colors[0], colors[1], colors[2]) == ("blue","green","red") 
    Stable sorts (preserving order of equal elements) are supported. Sorting is done using quick-sort mith median of 3 (and insertion-sort for small ranges).
    • Constructor Summary

      Constructors 
      Constructor and Description
      SortUtils() 
    • Method Summary

      Methods 
      Modifier and TypeMethod and Description
      static IteratorgetIterator(int[] p, List data)
      Answer iterator, which iterates over specified data list according to the specified permutation, that is data.get(p[0]),..,data.get(p[data.length-1])
      static IteratorgetIterator(int[] p, Object[] data)
      Answer iterator, which iterates over specified data array according to the specified permutation, that is data[p[0]],..,data[p[data.length-1]]
      static int[]identity(int n)
      Create identity permutation, that is {0, 1, ..., n}
      static int[]inverse(int[] p)
      Compute inverse permutation
      static voidmain(String[] args)
      Test method
      static Object[]permute(int[] p, Object[] data, boolean clone)
      Rearrange the specified data according to the specified permutation.
      static int[]reverse(int n)
      Create reverse permutation, that is {n-1, ....
      static voidsort(int[] indices, Object[] data, Comparator comparator)
      Do an unstable sort.
      static voidsort(int[] indices, Object[] data, Comparator comparator, boolean stable)
      Do a sort on indices.
      static int[]sort(Object[] data, Comparator comparator)
      Do an unstable sort.
      static int[]sort(Object[] data, Comparator comparator, boolean stable)
      Do a sort on indices.
    • Constructor Detail

      • SortUtils

        public SortUtils()
    • Method Detail

      • identity

        public static int[] identity(int n)
        Create identity permutation, that is {0, 1, ..., n}
      • reverse

        public static int[] reverse(int n)
        Create reverse permutation, that is {n-1, .... 1, 0}
      • inverse

        public static int[] inverse(int[] p)
        Compute inverse permutation
      • permute

        public static Object[] permute(int[] p,               Object[] data,               boolean clone)
        Rearrange the specified data according to the specified permutation. That is, the array is rearranged, such that data_after[p[i]] == data_before[i].
        Parameters:
        data - data to be permuted
        p - the permutation
        clone - if true, rearrange a clone instead of the original data;
        Returns:
        the permuted array (which is the original reference if clone == false)
      • getIterator

        public static Iterator getIterator(int[] p,                   Object[] data)
        Answer iterator, which iterates over specified data array according to the specified permutation, that is data[p[0]],..,data[p[data.length-1]]
      • getIterator

        public static Iterator getIterator(int[] p,                   List data)
        Answer iterator, which iterates over specified data list according to the specified permutation, that is data.get(p[0]),..,data.get(p[data.length-1])
      • sort

        public static void sort(int[] indices,        Object[] data,        Comparator comparator,        boolean stable)
        Do a sort on indices.
        Parameters:
        data - data to be sorted
        comparator - comparator to use
        stable - do a stable sort iff true
        indices - into data (any permutation of 0,..data.length-1).
      • sort

        public static int[] sort(Object[] data,         Comparator comparator,         boolean stable)
        Do a sort on indices.
        Parameters:
        data - data to be sorted
        comparator - comparator to use
        stable - do a stable sort iff true
        Returns:
        permutation p such that data[p[0]],..,data[p[data.length-1]] is in sorted order
      • sort

        public static int[] sort(Object[] data,         Comparator comparator)
        Do an unstable sort.
        Parameters:
        data - data to be sorted
        comparator - comparator to use
        Returns:
        permutation p such that data[p[0]],..,data[p[data.length-1]] is in sorted order
      • sort

        public static void sort(int[] indices,        Object[] data,        Comparator comparator)
        Do an unstable sort.
        Parameters:
        data - data to be sorted
        indices - into data (permutation of 0,..data.length-1).
      • main

        public static void main(String[] args)
        Test method

SCaVis 1.8 © jWork.org