/* 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