Logo Search packages:      
Sourcecode: yorick-imutil version File versions  Download package

sedgesort.c

/*
 *  A library of sorting functions
 *
 *  Written by:  Ariel Faigon,  1987
 */
#include    <stdio.h>
#include    "sort.h"

/*------------------------------------------------------------------- 
 *            This file shouldn't be touched.
 *         For customizable parameters, see 'sort.h'
 *-----------------------------------------------------------------*/


/* 15 has been found empirically as the optimal cutoff value */
#ifndef CUTOFF
#  define CUTOFF 15
#endif

/*
 |  void  partial_quickersort (array, lower, upper)
 |  KEY_T  array[];
 |  int    lower, upper;
 |
 |  Abstract:
 |    Sort array[lower..upper] into a partial order
 |          leaving segments which are CUTOFF elements long
 |          unsorted internally.
 |
 |  Efficiency:
 |    Could be made faster for _worst_ cases by selecting
 |    a pivot using median-of-3. I don't do it because
 |    in practical cases my pivot selection is arbitrary and
 |    thus pretty random, your mileage may vary.
 |
 |  Method:
 |    Partial Quicker-sort using a sentinel (ala Robert Sedgewick)
 |
 |  BIG NOTE:
 |    Precondition: array[upper+1] holds the maximum possible key.
 |    with a cutoff value of CUTOFF.
 */

void  partial_quickersort_long (long *array, int lower, int upper)
{
    int         i, j;
    long    temp, pivot;

    if (upper - lower > CUTOFF) {
      SWAP(array[lower], array[(upper+lower)/2]);
      i = lower;  j = upper + 1;  pivot = array[lower];
      while (1) {
          /*
           * ------------------------- NOTE --------------------------
           * ignoring BIG NOTE above may lead to an infinite loop here
           * ---------------------------------------------------------
           */
          do i++; while (LT(array[i], pivot));
          do j--; while (GT(array[j], pivot));
          if (j < i) break;
          SWAP(array[i], array[j]);
      }
      SWAP(array[lower], array[j]);
      partial_quickersort_long (array, lower, j - 1);
      partial_quickersort_long (array, i, upper);
    }
}

void  partial_quickersort_float (array, lower, upper)
register float  array[];
register int    lower, upper;
{
    register int  i, j;
    register float      temp, pivot;

    if (upper - lower > CUTOFF) {
      SWAP(array[lower], array[(upper+lower)/2]);
      i = lower;  j = upper + 1;  pivot = array[lower];
      while (1) {
          do i++; while (LT(array[i], pivot));
          do j--; while (GT(array[j], pivot));
          if (j < i) break;
          SWAP(array[i], array[j]);
      }
      SWAP(array[lower], array[j]);
      partial_quickersort_float (array, lower, j - 1);
      partial_quickersort_float (array, i, upper);
    }
}

void  partial_quickersort_double (array, lower, upper)
register double array[];
register int    lower, upper;
{
    register int  i, j;
    register double     temp, pivot;

    if (upper - lower > CUTOFF) {
      SWAP(array[lower], array[(upper+lower)/2]);
      i = lower;  j = upper + 1;  pivot = array[lower];
      while (1) {
          do i++; while (LT(array[i], pivot));
          do j--; while (GT(array[j], pivot));
          if (j < i) break;
          SWAP(array[i], array[j]);
      }
      SWAP(array[lower], array[j]);
      partial_quickersort_double (array, lower, j - 1);
      partial_quickersort_double (array, i, upper);
    }
}

void  partial_quickersort_short (array, lower, upper)
register short array[];
register int    lower, upper;
{
    register int  i, j;
    register short      temp, pivot;

    if (upper - lower > CUTOFF) {
      SWAP(array[lower], array[(upper+lower)/2]);
      i = lower;  j = upper + 1;  pivot = array[lower];
      while (1) {
          do i++; while (LT(array[i], pivot));
          do j--; while (GT(array[j], pivot));
          if (j < i) break;
          SWAP(array[i], array[j]);
      }
      SWAP(array[lower], array[j]);
      partial_quickersort_short (array, lower, j - 1);
      partial_quickersort_short (array, i, upper);
    }
}

/*
 |  void  _sedgesort (array, len)
 |  KEY_T  array[];
 |  int    len;
 |
 |  Abstract:
 |    Sort array[0..len-1] into increasing order.
 |
 |  Method:
 |    Use partial_quickersort() with a sentinel (ala Sedgewick)
 |    to reach a partial order, leave the unsorted segments of
 |    length == CUTOFF to a simpler low-overhead, insertion sort.
 |
 |    This method seems to me the ultimative sort method in terms
 |    of average efficiency (Skeptic ? try to beat it).
 |
 |  BIG NOTE:
 |    precondition: array[len] must hold a sentinel (largest
 |    possible value) in order for this to work correctly.
 |    An easy way to do this is to declare an array that has
 |    len+1 elements [0..len], and assign MAXINT or some such
 |    to the last location before starting the sort (see sorttest.c)
 */
void _sedgesort_long (long *array, int len)
{
    /*
     * ------------------------- NOTE --------------------------
     * ignoring BIG NOTE above may lead to an infinite loop here
     * ---------------------------------------------------------
     */
    partial_quickersort_long (array, 0, len - 1);
    insort_long (array, len);
}

void _sedgesort_float (array, len)
register float  array[];
register int    len;
{
    partial_quickersort_float (array, 0, len - 1);
    insort_float (array, len);
}

void _sedgesort_double (array, len)
register double array[];
register int    len;
{
    partial_quickersort_double (array, 0, len - 1);
    insort_double (array, len);
}

void _sedgesort_short (array, len)
register short  array[];
register int    len;
{
    partial_quickersort_short (array, 0, len - 1);
    insort_short (array, len);
}


Generated by  Doxygen 1.6.0   Back to index