Given two arrays of equal length and varying types, the standard technique for sorting them in parallel is to create a new temporary object for each row, store the objects in a temporary array, sort the array using a custom comparator, and the extract the original values back into their respective arrays. This is wasteful in both time and memory.
This class generates bytecode customized to the particular set of arrays you need to sort, in such a way that both arrays are sorted in-place, simultaneously.
Two sorting algorithms are provided. Quicksort is best when you only need to sort by a single column, as it requires very few comparisons and swaps. Mergesort is best used when sorting multiple columns, as it is a "stable" sort--that is, it does not affect the relative order of equal objects from previous sorts.
The mergesort algorithm here is an "in-place" variant, which while slower, does not require a temporary array.
| Modifier and Type | Class and Description |
|---|---|
| pack-priv static class | |
| pack-priv static class | |
| pack-priv static interface | |
| pack-priv static class | |
| pack-priv static class | |
| public static class | |
| pack-priv static class | |
| pack-priv static class | |
| pack-priv static class | |
| pack-priv static class |
| Modifier and Type | Field and Description |
|---|---|
| protected Object[] | |
| private ParallelSorter. |
| Access | Constructor and Description |
|---|---|
| protected |
| Modifier and Type | Method and Description |
|---|---|
| private void | |
| protected int | |
| public static ParallelSorter | |
| private int | |
| public void | |
| public void | mergeSort(int
array (column) to sort by index, int starting array index (row), inclusive lo, int ending array index (row), exclusive hi)Sort the arrays using an in-place merge sort. |
| public void | mergeSort(int
array (column) to sort by index, Comparator<T> Comparator to use if the specified column is non-primitive cmp)Sort the arrays using an in-place merge sort. |
| public void | mergeSort(int
array (column) to sort by index, int starting array index (row), inclusive lo, int ending array index (row), exclusive hi, Comparator<T> Comparator to use if the specified column is non-primitive cmp)Sort the arrays using an in-place merge sort. |
| public abstract ParallelSorter | |
| public void | |
| public void | quickSort(int
array (column) to sort by index, int starting array index (row), inclusive lo, int ending array index (row), exclusive hi)Sort the arrays using the quicksort algorithm. |
| public void | quickSort(int
array (column) to sort by index, Comparator<T> Comparator to use if the specified column is non-primitive cmp)Sort the arrays using the quicksort algorithm. |
| public void | quickSort(int
array (column) to sort by index, int starting array index (row), inclusive lo, int ending array index (row), exclusive hi, Comparator<T> Comparator to use if the specified column is non-primitive cmp)Sort the arrays using the quicksort algorithm. |
| a | back to summary |
|---|---|
| protected Object[] a | |
| comparer | back to summary |
|---|---|
| private ParallelSorter. | |
| ParallelSorter | back to summary |
|---|---|
| protected ParallelSorter() | |
| chooseComparer | back to summary |
|---|---|
| private void chooseComparer(int index, Comparator<T> cmp) | |
| compare | back to summary |
|---|---|
| protected int compare(int i, int j) Implements abstract org.
| |
| create | back to summary |
|---|---|
| public static ParallelSorter create(Object[] arrays) Create a new ParallelSorter object for a set of arrays. You may sort the arrays multiple times via the same ParallelSorter object.
| |
| len | back to summary |
|---|---|
| private int len() | |
| mergeSort | back to summary |
|---|---|
public void mergeSort(int index)
| |
| mergeSort | back to summary |
|---|---|
| public void mergeSort(int index, int lo, int hi) Sort the arrays using an in-place merge sort.
| |
| mergeSort | back to summary |
|---|---|
| public void mergeSort(int index, Comparator<T> cmp) Sort the arrays using an in-place merge sort.
| |
| mergeSort | back to summary |
|---|---|
| public void mergeSort(int index, int lo, int hi, Comparator<T> cmp) Sort the arrays using an in-place merge sort.
| |
| newInstance | back to summary |
|---|---|
| public abstract ParallelSorter newInstance(Object[] arrays) | |
| quickSort | back to summary |
|---|---|
| public void quickSort(int index) Sort the arrays using the quicksort algorithm.
| |
| quickSort | back to summary |
|---|---|
| public void quickSort(int index, int lo, int hi) Sort the arrays using the quicksort algorithm.
| |
| quickSort | back to summary |
|---|---|
| public void quickSort(int index, Comparator<T> cmp) Sort the arrays using the quicksort algorithm.
| |
| quickSort | back to summary |
|---|---|
| public void quickSort(int index, int lo, int hi, Comparator<T> cmp) Sort the arrays using the quicksort algorithm.
| |
| Modifier and Type | Field and Description |
|---|---|
| private final byte[] |
| Access | Constructor and Description |
|---|---|
| public |
| Modifier and Type | Method and Description |
|---|---|
| public int |
| a | back to summary |
|---|---|
| private final byte[] a | |
| ByteComparer | back to summary |
|---|---|
| public ByteComparer(byte[] a) | |
| compare | back to summary |
|---|---|
| public int compare(int i, int j) Implements org.
| |
| Modifier and Type | Field and Description |
|---|---|
| private final Object[] | |
| private final Comparator |
| Access | Constructor and Description |
|---|---|
| public |
| Modifier and Type | Method and Description |
|---|---|
| public int |
| a | back to summary |
|---|---|
| private final Object[] a | |
| cmp | back to summary |
|---|---|
| private final Comparator<T> cmp | |
| ComparatorComparer | back to summary |
|---|---|
| public ComparatorComparer(Object[] a, Comparator<T> cmp) | |
| compare | back to summary |
|---|---|
| public int compare(int i, int j) Implements org.
| |
| Modifier and Type | Method and Description |
|---|---|
| public int |
| compare | back to summary |
|---|---|
| public int compare(int i, int j) | |
| Modifier and Type | Field and Description |
|---|---|
| private final double[] |
| Access | Constructor and Description |
|---|---|
| public |
| Modifier and Type | Method and Description |
|---|---|
| public int |
| a | back to summary |
|---|---|
| private final double[] a | |
| DoubleComparer | back to summary |
|---|---|
| public DoubleComparer(double[] a) | |
| compare | back to summary |
|---|---|
| public int compare(int i, int j) Implements org.
| |
| Modifier and Type | Field and Description |
|---|---|
| private final float[] |
| Access | Constructor and Description |
|---|---|
| public |
| Modifier and Type | Method and Description |
|---|---|
| public int |
| a | back to summary |
|---|---|
| private final float[] a | |
| FloatComparer | back to summary |
|---|---|
| public FloatComparer(float[] a) | |
| compare | back to summary |
|---|---|
| public int compare(int i, int j) Implements org.
| |
| Modifier and Type | Field and Description |
|---|---|
| private Object[] | |
| private static final AbstractClassGenerator. |
| Access | Constructor and Description |
|---|---|
| public |
| Modifier and Type | Method and Description |
|---|---|
| public ParallelSorter | |
| protected Object | firstInstance(Class<T> type)
Implements abstract org.
|
| public void | |
| protected ClassLoader | |
| protected Object | nextInstance(Object instance)
Implements abstract org.
|
| public void |
| arrays | back to summary |
|---|---|
| private Object[] arrays | |
| SOURCE | back to summary |
|---|---|
| private static final AbstractClassGenerator. | |
| Generator | back to summary |
|---|---|
| public Generator() | |
| create | back to summary |
|---|---|
| public ParallelSorter create() | |
| firstInstance | back to summary |
|---|---|
| protected Object firstInstance(Class<T> type) Implements abstract org.
| |
| generateClass | back to summary |
|---|---|
| public void generateClass(ClassVisitor v) throws Exception Implements org.
| |
| getDefaultClassLoader | back to summary |
|---|---|
| protected ClassLoader getDefaultClassLoader() Implements abstract org.
| |
| nextInstance | back to summary |
|---|---|
| protected Object nextInstance(Object instance) Implements abstract org.
| |
| setArrays | back to summary |
|---|---|
| public void setArrays(Object[] arrays) | |
| Modifier and Type | Field and Description |
|---|---|
| private final int[] |
| Access | Constructor and Description |
|---|---|
| public |
| Modifier and Type | Method and Description |
|---|---|
| public int |
| a | back to summary |
|---|---|
| private final int[] a | |
| IntComparer | back to summary |
|---|---|
| public IntComparer(int[] a) | |
| compare | back to summary |
|---|---|
| public int compare(int i, int j) Implements org.
| |
| Modifier and Type | Field and Description |
|---|---|
| private final long[] |
| Access | Constructor and Description |
|---|---|
| public |
| Modifier and Type | Method and Description |
|---|---|
| public int |
| a | back to summary |
|---|---|
| private final long[] a | |
| LongComparer | back to summary |
|---|---|
| public LongComparer(long[] a) | |
| compare | back to summary |
|---|---|
| public int compare(int i, int j) Implements org.
| |
| Access | Constructor and Description |
|---|---|
| public |
| Modifier and Type | Method and Description |
|---|---|
| public int |
| a | back to summary |
|---|---|
| private final Object[] a | |
| ObjectComparer | back to summary |
|---|---|
| public ObjectComparer(Object[] a) | |
| compare | back to summary |
|---|---|
| public int compare(int i, int j) Implements org.
| |
| Modifier and Type | Field and Description |
|---|---|
| private final short[] |
| Access | Constructor and Description |
|---|---|
| public |
| Modifier and Type | Method and Description |
|---|---|
| public int |
| a | back to summary |
|---|---|
| private final short[] a | |
| ShortComparer | back to summary |
|---|---|
| public ShortComparer(short[] a) | |
| compare | back to summary |
|---|---|
| public int compare(int i, int j) Implements org.
| |