arrays.java

数据挖掘中

/*----------------------------------------------------------------------
  File    : Arrays.java
  Contents: Sorting an array of objects with quicksort
  Author  : Christian Borgelt
  History : 02.04.2002 file created
            06.07.2004 adapted to standard java interpretation of 'to'
----------------------------------------------------------------------*/
package util;

/*----------------------------------------------------------------------
In contrast to java.util.Arrays, which provides functions for sorting
arrays with a compareTo function that takes one argument, the function
in this class uses a compareTo function with two arguments. The second
argument can be used to modify the behavior of the comparison function.
The sorting algorithm is a modified quicksort, which switches to
insertion sort once the array sections to be sorted are small enough.
----------------------------------------------------------------------*/

public class Arrays {

  public interface CompareTo2 {
    public int compareTo (Object obj, Object data); }
  /* The element comparison function "compareTo" of this class needs */
  /* two arguments, the second of which can be used to specify how */
  /* the comparison is to be carried out. */

  /*------------------------------------------------------------------*/

  /* --- constants --- */
  private static final int TH_INSERT = 8;
  /* section size threshold for switch to insertion sort */

  /*------------------------------------------------------------------*/

  private static void qsort (CompareTo2[] array, int from, int to,
                             Object data)
  {                             /* --- recursive part of quicksort */
    int        m, n;            /* number of elements in sections */
    int        l, r;            /* indices of exchange positions */
    CompareTo2 x, t;            /* pivot element and exchange buffer */

    do {                        /* sections sort loop */
      l = from; r = to;         /* start at left and right boundary */
      if (array[l].compareTo(array[r], data) > 0) {
        t        = array[l];    /* bring the first and the last */
        array[l] = array[r];    /* element of the array */
        array[r] = t;           /* into the proper order */
      }                         /* (needed for choosing the pivot) */
      x = array[(l+r) >> 1];    /* get the middle element as pivot */
      if      (x.compareTo(array[l], data) < 0)
        x = array[l];           /* first element is a better pivot */
      else if (x.compareTo(array[r], data) > 0)
        x = array[r];           /* last  element is a better pivot */
      while (true) {            /* split and exchange loop */
	while (array[++l].compareTo(x, data) < 0)
          ;                     /* skip elements smaller than pivot */
	while (array[--r].compareTo(x, data) > 0)
          ;                     /* skip elements greater than pivot */
        if (l >= r) {           /* if less than two elements left, */
          if (l <= r) { l++; r--; } break; }     /* abort the loop */
        t        = array[l];    /* otherwise exchange the elements */
        array[l] = array[r];    /* at the left and right index */
        array[r] = t;           /* (which are in the wrong order) */
      }
      m = to -l   +1;           /* compute the number of elements */
      n = r -from +1;           /* right and left of the split */
      if (n > m) {              /* if right section is smaller, */
        if (m >= TH_INSERT)     /* but larger than the threshold, */
          qsort(array, l, to, data);      /* sort it recursively, */
        to = r; }               /* then switch to the left  section */
      else {                    /* if the left section is smaller, */
        if (n >= TH_INSERT)     /* but larger than the threshold, */
          qsort(array, from, r, data);    /* sort it recursively, */
        from = l; n = m;        /* then switch to the right section */
      }
    } while (n >= TH_INSERT);   /* while greater than threshold */
  }  /* qsort() */

  /*------------------------------------------------------------------*/

  public static void sort (CompareTo2[] array, int from, int to,
                           Object data)
  {                             /* --- sort an array of objects */
    int        n;               /* number of elements to sort */
    int        k;               /* size of first section */
    int        l, r;            /* array indices */
    CompareTo2 t;               /* exchange buffer */

    n = to -from;               /* compute the number of elements */
    if (n <= 1) return;         /* do not sort less than two elements */
    if (n < TH_INSERT)          /* if fewer elements than threshold */
      k = n;                    /* for insertion sort, not the */
    else {                      /* number of elements, otherwise call */
      qsort(array, from, to-1, data);       /* the recursive function */
      k = TH_INSERT -1;         /* and get the number of elements */
    }                           /* in the first array section */
    for (l = r = from; --k > 0;)/* find the smallest element */
      if (array[++r].compareTo(array[l], data) < 0)
        l = r;                  /* within the first k elements */
    t        = array[r = from]; /* swap the smallest element */
    array[r] = array[l];        /* to the front of the array */
    array[l] = t;               /* as a sentinel for insertion */
    while (--n > 0) {           /* insertion sort loop */
      t = array[++r];           /* note the element to insert */
      for (l = r; array[--l].compareTo(t, data) > 0; )
        array[l+1] = array[l];  /* shift elements that are greater */
      array[l+1] = t;           /* than the one to insert and store */
    }                           /* the element to insert in the */
  }  /* sort() */               /* place thus found */

  /*------------------------------------------------------------------*/

  public static void sort (CompareTo2[] array, Object data)
  { sort(array, 0, array.length, data); }

}  /* class Arrays */