mev-4.0.01/source/org/tigr/microarray/mev/cluster/gui/impl/util/IntSorter.java

Code
Comments
Other
Rev Date Author Line
2 26 Feb 07 jari 1 /*
2 26 Feb 07 jari 2 Copyright @ 1999-2003, The Institute for Genomic Research (TIGR).
2 26 Feb 07 jari 3 All rights reserved.
2 26 Feb 07 jari 4 */
2 26 Feb 07 jari 5 /*
2 26 Feb 07 jari 6  * $RCSfile: IntSorter.java,v $
2 26 Feb 07 jari 7  * $Revision: 1.3 $
2 26 Feb 07 jari 8  * $Date: 2005/03/10 20:36:56 $
2 26 Feb 07 jari 9  * $Author: braistedj $
2 26 Feb 07 jari 10  * $State: Exp $
2 26 Feb 07 jari 11  */
2 26 Feb 07 jari 12 package org.tigr.microarray.mev.cluster.gui.impl.util;
2 26 Feb 07 jari 13
2 26 Feb 07 jari 14 public class IntSorter {
2 26 Feb 07 jari 15     
2 26 Feb 07 jari 16     /**
2 26 Feb 07 jari 17      * Sorts an array with specified comparator.
2 26 Feb 07 jari 18      *
2 26 Feb 07 jari 19      * @param a the array of integers to be sorted.
2 26 Feb 07 jari 20      * @param c the <code>IntComparator</code> interface implementation.
2 26 Feb 07 jari 21      * @see IntComparator
2 26 Feb 07 jari 22      */
2 26 Feb 07 jari 23     public static void sort(int[] a, IntComparator c) {
2 26 Feb 07 jari 24   int[] aux = cloneArray(a);
2 26 Feb 07 jari 25   mergeSort(aux, a, 0, a.length, c);
2 26 Feb 07 jari 26     }
2 26 Feb 07 jari 27     
2 26 Feb 07 jari 28     private static int[] cloneArray(int[] a) {
2 26 Feb 07 jari 29   int[] clone = new int[a.length];
2 26 Feb 07 jari 30   for (int i = a.length; --i >= 0;) {
2 26 Feb 07 jari 31       clone[i] = a[i];
2 26 Feb 07 jari 32   }
2 26 Feb 07 jari 33   return clone;
2 26 Feb 07 jari 34     }
2 26 Feb 07 jari 35     
2 26 Feb 07 jari 36     private static void swap(int[] x, int a, int b) {
2 26 Feb 07 jari 37   int t = x[a];
2 26 Feb 07 jari 38   x[a] = x[b];
2 26 Feb 07 jari 39   x[b] = t;
2 26 Feb 07 jari 40     }
2 26 Feb 07 jari 41     
2 26 Feb 07 jari 42     private static void mergeSort(int[] src, int[] dest, int low, int high, IntComparator c) {
2 26 Feb 07 jari 43   int length = high - low;
2 26 Feb 07 jari 44   
2 26 Feb 07 jari 45   // Insertion sort on smallest arrays
2 26 Feb 07 jari 46   if (length < 7) {
2 26 Feb 07 jari 47       for (int i=low; i<high; i++)
2 26 Feb 07 jari 48     for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
2 26 Feb 07 jari 49         swap(dest, j, j-1);
2 26 Feb 07 jari 50       return;
2 26 Feb 07 jari 51   }
2 26 Feb 07 jari 52   
2 26 Feb 07 jari 53   // Recursively sort halves of dest into src
2 26 Feb 07 jari 54   int mid = (low + high)/2;
2 26 Feb 07 jari 55   mergeSort(dest, src, low, mid, c);
2 26 Feb 07 jari 56   mergeSort(dest, src, mid, high, c);
2 26 Feb 07 jari 57   
2 26 Feb 07 jari 58   // If list is already sorted, just copy from src to dest.  This is an
2 26 Feb 07 jari 59   // optimization that results in faster sorts for nearly ordered lists.
2 26 Feb 07 jari 60   if (c.compare(src[mid-1], src[mid]) <= 0) {
2 26 Feb 07 jari 61       System.arraycopy(src, low, dest, low, length);
2 26 Feb 07 jari 62       return;
2 26 Feb 07 jari 63   }
2 26 Feb 07 jari 64   
2 26 Feb 07 jari 65   // Merge sorted halves (now in src) into dest
2 26 Feb 07 jari 66   for (int i = low, p = low, q = mid; i < high; i++) {
2 26 Feb 07 jari 67       if (q>=high || p<mid && c.compare(src[p], src[q]) <= 0)
2 26 Feb 07 jari 68     dest[i] = src[p++];
2 26 Feb 07 jari 69       else
2 26 Feb 07 jari 70     dest[i] = src[q++];
2 26 Feb 07 jari 71   }
2 26 Feb 07 jari 72     }
2 26 Feb 07 jari 73 }

Generated on Thu Jul 20 09:29:33 2023 (UTC) by svndigest 0.11.2pre (dev build 1672)