org.knowceans.util
Class IndexQuickSort

java.lang.Object
  extended by org.knowceans.util.IndexQuickSort

public class IndexQuickSort
extends java.lang.Object

IndexQuickSort sorts indices of an array without changing its values. There are additional functions to reverse the order and to get the inverse of the mapping from the array to the sorted index. Types supported include primitive double and int arrays as well as objects and associated Comparators.

Author:
gregor, used quicksort algorithm at http://www.cs.princeton.edu/introcs/42sort/QuickSort.java.html

Constructor Summary
IndexQuickSort()
           
 
Method Summary
static int[] inverse(int[] index)
          inverse of the index, i.e., the ordered index of the argument
static void inverse(int[] index, int[] invindex)
          inverse of the index, i.e., the ordered index of the argument
static void main(java.lang.String[] args)
           
static void reorder(double[] x, int[] order)
          reorder the array according to the sorting.
static void reorder(int[] x, int[] order)
          reorder the array according to the sorting.
static
<T> void
reorder(java.util.List<T> x, int[] order)
          reordering for lists
static
<T> void
reorder(T[] x, int[] order)
          reorder the array according to the sorting.
static void resortdec(int[] x, int[] idx, int[] invidx, int dec)
          re-sort index of x after x[dec] has reduced in value
static void resortinc(int[] x, int[] idx, int[] invidx, int inc)
          re-sort index of x after x[inc] has increased in value
static void reverse(int[] index)
          reverse ordering
static int[] sort(double[] fixedArray)
          sort indices
static void sort(double[] fixedArray, int[] index)
          sort indices
static void sort(double[] a, int[] index, int left, int right)
           
static int[] sort(int[] fixedArray)
          sort indices
static void sort(int[] fixedArray, int[] index)
          sort indices
static void sort(int[] a, int[] index, int left, int right)
           
static
<T> int[]
sort(java.util.List<T> fixedList)
          sort indices.
static
<T> int[]
sort(T[] fixedArray, java.util.Comparator<T> cmp)
          sort indices
static
<T> void
sort(T[] fixedArray, java.util.Comparator<T> cmp, int[] index)
          sort indices
static
<T> void
sort(T[] a, java.util.Comparator<T> cmp, int[] index, int left, int right)
           
static void swap(double[] index, int i, int j)
           
static void swap(int[] index, int i, int j)
           
static
<T> void
swap(T[] index, int i, int j)
           
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

IndexQuickSort

public IndexQuickSort()
Method Detail

main

public static void main(java.lang.String[] args)

sort

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

Parameters:
fixedArray - values to be sorted
index - range of indices into fixedArray

sort

public static int[] sort(double[] fixedArray)
sort indices

Parameters:
fixedArray - values to be sorted
Returns:
index range of indices into fixedArray

inverse

public static int[] inverse(int[] index)
inverse of the index, i.e., the ordered index of the argument

Parameters:
index -

inverse

public static void inverse(int[] index,
                           int[] invindex)
inverse of the index, i.e., the ordered index of the argument

Parameters:
index -
invindex - the inverse mapping of index

reverse

public static void reverse(int[] index)
reverse ordering

Parameters:
main -
index -

sort

public static void sort(double[] a,
                        int[] index,
                        int left,
                        int right)

swap

public static void swap(int[] index,
                        int i,
                        int j)

swap

public static void swap(double[] index,
                        int i,
                        int j)

swap

public static <T> void swap(T[] index,
                            int i,
                            int j)

sort

public static void sort(int[] fixedArray,
                        int[] index)
sort indices

Parameters:
fixedArray - values to be sorted
index - range of indices into fixedArray

sort

public static int[] sort(int[] fixedArray)
sort indices

Parameters:
fixedArray - values to be sorted
Returns:
index range of indices into fixedArray

sort

public static <T> int[] sort(java.util.List<T> fixedList)
sort indices.

Type Parameters:
T - a list of Comparables. Cast problem with >, so the argument has Comparable elements by contract.
Parameters:
fixedList - values to be sorted should be Comparable
Returns:
index range of indices into fixedArray

sort

public static void sort(int[] a,
                        int[] index,
                        int left,
                        int right)

sort

public static <T> void sort(T[] fixedArray,
                            java.util.Comparator<T> cmp,
                            int[] index)
sort indices

Parameters:
fixedArray - values to be sorted
index - range of indices into fixedArray

sort

public static <T> int[] sort(T[] fixedArray,
                             java.util.Comparator<T> cmp)
sort indices

Parameters:
fixedArray - values to be sorted
Returns:
index range of indices into fixedArray

sort

public static <T> void sort(T[] a,
                            java.util.Comparator<T> cmp,
                            int[] index,
                            int left,
                            int right)

resortinc

public static void resortinc(int[] x,
                             int[] idx,
                             int[] invidx,
                             int inc)
re-sort index of x after x[inc] has increased in value

Parameters:
x -
sort2k -
invidx -
inc -

resortdec

public static void resortdec(int[] x,
                             int[] idx,
                             int[] invidx,
                             int dec)
re-sort index of x after x[dec] has reduced in value

Parameters:
x -
sort2k -
invidx -
dec -

reorder

public static void reorder(double[] x,
                           int[] order)
reorder the array according to the sorting. This uses bubblesort to reorder in-place.

Parameters:
ds -
order -

reorder

public static void reorder(int[] x,
                           int[] order)
reorder the array according to the sorting. This uses bubblesort to reorder in-place.

Parameters:
x -
order - sorting index new, element old

reorder

public static <T> void reorder(T[] x,
                               int[] order)
reorder the array according to the sorting. This uses bubblesort to reorder in-place.

Parameters:
x -
order -

reorder

public static <T> void reorder(java.util.List<T> x,
                               int[] order)
reordering for lists

Type Parameters:
T -
Parameters:
x -
order -