Mercurial > repos > timpalpant > java_genomics_toolkit

comparison src/edu/unc/utils/SortUtils.java @ 2:e16016635b2a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Uploaded
author timpalpant
date Mon, 13 Feb 2012 22:12:06 -0500
parents
children
comparison
equal deleted inserted replaced
1:a54db233ee3d 2:e16016635b2a
1 package edu.unc.utils;
2
3 /**
4 * Custom sorting utilities
5 * see: http://stackoverflow.com/questions/951848/java-array-sort-quick-way-to-get-a-sorted-list-of-indices-of-an-array
6 * @author timpalpant
7 *
8 */
9 public class SortUtils {
10 public static int[] indexSort(float[] main) {
11 int[] index = new int[main.length];
12 for (int i = 0; i < index.length; i++) {
13 index[i] = i;
14 }
15
16 quicksort(main, index, 0, index.length-1);
17
18 return index;
19 }
20
21 // quicksort a[left] to a[right]
22 public static void quicksort(float[] a, int[] index, int left, int right) {
23 if (right <= left)
24 return;
25 int i = partition(a, index, left, right);
26 quicksort(a, index, left, i - 1);
27 quicksort(a, index, i + 1, right);
28 }
29
30 // partition a[left] to a[right], assumes left < right
31 private static int partition(float[] a, int[] index, int left, int right) {
32 int i = left - 1;
33 int j = right;
34 while (true) {
35 while (a[index[++i]] < a[index[right]])
36 // find item on left to swap
37 ; // a[right] acts as sentinel
38 while (a[index[right]] < a[index[--j]])
39 // find item on right to swap
40 if (j == left)
41 break; // don't go out-of-bounds
42 if (i >= j)
43 break; // check if pointers cross
44 exch(a, index, i, j); // swap two elements into place
45 }
46 exch(a, index, i, right); // swap with partition element
47 return i;
48 }
49
50 // exchange a[i] and a[j]
51 private static void exch(float[] a, int[] index, int i, int j) {
52 // Don't swap the data
53 // float swap = a[i];
54 // a[i] = a[j];
55 // a[j] = swap;
56 int b = index[i];
57 index[i] = index[j];
58 index[j] = b;
59 }
60 }