mev-4.0.01/source/org/tigr/microarray/mev/cluster/algorithm/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 15:45:30 $
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.algorithm.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:25:27 2023 (UTC) by svndigest 0.11.2pre (dev build 1672)