Logo Search packages:      
Sourcecode: rpart version File versions  Download package

mysort.c

/* SCCS @(#)mysort.c    1.6 12/13/99 */
/*
** quick sort routine : sort a vector of floats, and carry along an int
**
**  x:     vector to sort on
**  start: first element of x to sort
**  stop:  last element of x to sort
**  cvec:  a vector to carry along
*/
#include "rpart.h"
#include "rpartproto.h"

void mysort(int start, int stop, FLOAT *x, int *cvec)
 {
 int i, j, k;
 FLOAT temp, median;
 int tempd;

  while (start < stop) {
    /*
    ** first-- if the list is short, do an ordinary insertion sort
    */
    if ((stop-start)<11) {
      for (i=start+1; i<=stop; i++) {
          temp = x[i];
          tempd= cvec[i];
          j=i-1;

          while (j>=start && (x[j]>temp)) {
            x[j+1] = x[j];
            cvec[j+1] = cvec[j];
            j--;
            }
          x[j+1] = temp;
          cvec[j+1]  = tempd;
          }
      return;
      }

    /*
    ** list is longer -- split it into two
    **  I use the median of 3 values as the split point
    */
    i=start;
    j=stop;
    k = (start + stop)/2;

    median = x[k];
    if (x[i] >= x[k]) {      /* one of j or k is smallest */
      if (x[j] > x[k]) {   /* k is smallest */
          if (x[i] > x[j])  median = x[j];
          else median= x[i];
          }
      }
    else {
      if (x[j] < x[k]) {
          if (x[i] > x[j]) median = x[i];
          else median = x[j];
          }
      }

    /* 
    **  Now actually do the partitioning 
    **   Because we must have at least one element >= median, "i"
    **   will never run over the end of the array.  Similar logic
    **   applies to j.
    ** A note on the use of "<" rather than "<=".  If a list has lots
    **   of identical elements, e.g. 80/100 are "3.5", then we will
    **   often go to the swap step with x[i]=x[j]=median.  But we will
    **   get the pointers i and j to meet approximately in the middle of
    **   the list, and that is THE important condition for speed in a
    **   quicksort.
    **   
    */
    while (i<j) {
      /*
      ** top pointer down till it points at something too large
      */
      while (x[i] < median) i++;

      /*
      ** bottom pointer up until it points at something too small
      */
      while(x[j] > median) j--;

      if (i<j) {
          if (x[i] > x[j]) {  /* swap */
            temp = x[i];
            x[i] = x[j];
            x[j] = temp;
            tempd= cvec[i];   cvec[i] =cvec[j];  cvec[j] =tempd;
            }
          i++; j--;
          }
      }

    /*
    ** The while() step helps if there are lots of ties.  It will break
    **  the list into 3 parts: < median, ==median, >=median, of which only
    **  the top and bottom ones need further attention.
    ** The ">=" is needed because i may be  == to j
    */
    while (x[i] >= median && i>start) i--;
    while (x[j] <= median && j<stop ) j++;

    /*
    ** list has been split, now do a recursive call
    **   always recur on the shorter list, as this keeps the total
    **       depth of nested calls to less than log_base2(n).
    */
    if ((i-start) < (stop-j)) { /* top list is shorter */
      if ((i-start)>0) mysort(start,i, x, cvec);
      start =j; 
      }

    else {    /* bottom list is shorter */
      if ((stop -j)>0) mysort(j,stop, x, cvec);
      stop=i; 
      }
     }
  }

Generated by  Doxygen 1.6.0   Back to index