htswanalysis/MACS/lib/gsl/gsl-1.11/sort/sortvec_source.c

   1 /*
   2  * Implement Heap sort -- direct and indirect sorting
   3  * Based on descriptions in Sedgewick "Algorithms in C"
   4  *
   5  * Copyright (C) 1999  Thomas Walter
   6  *
   7  * 18 February 2000: Modified for GSL by Brian Gough
   8  *
   9  * This is free software; you can redistribute it and/or modify it
  10  * under the terms of the GNU General Public License as published by the
  11  * Free Software Foundation; either version 3, or (at your option) any
  12  * later version.
  13  *
  14  * This source is distributed in the hope that it will be useful, but WITHOUT
  15  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  16  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  17  * for more details.
  18  */
  19
  20 static inline void FUNCTION (my, downheap) (BASE * data, const size_t stride, const size_t N, size_t k);
  21
  22 static inline void
  23 FUNCTION (my, downheap) (BASE * data, const size_t stride, const size_t N, size_t k)
  24 {
  25   BASE v = data[k * stride];
  26
  27   while (k <= N / 2)
  28     {
  29       size_t j = 2 * k;
  30
  31       if (j < N && data[j * stride] < data[(j + 1) * stride])
  32         {
  33           j++;
  34         }
  35
  36       if (!(v < data[j * stride]))  /* avoid infinite loop if nan */
  37         {
  38           break;
  39         }
  40
  41       data[k * stride] = data[j * stride];
  42
  43       k = j;
  44     }
  45
  46   data[k * stride] = v;
  47 }
  48
  49 void
  50 TYPE (gsl_sort) (BASE * data, const size_t stride, const size_t n)
  51 {
  52   size_t N;
  53   size_t k;
  54
  55   if (n == 0)
  56     {
  57       return;                   /* No data to sort */
  58     }
  59
  60   /* We have n_data elements, last element is at 'n_data-1', first at
  61      '0' Set N to the last element number. */
  62
  63   N = n - 1;
  64
  65   k = N / 2;
  66   k++;                          /* Compensate the first use of 'k--' */
  67   do
  68     {
  69       k--;
  70       FUNCTION (my, downheap) (data, stride, N, k);
  71     }
  72   while (k > 0);
  73
  74   while (N > 0)
  75     {
  76       /* first swap the elements */
  77       BASE tmp = data[0 * stride];
  78       data[0 * stride] = data[N * stride];
  79       data[N * stride] = tmp;
  80
  81       /* then process the heap */
  82       N--;
  83
  84       FUNCTION (my, downheap) (data, stride, N, 0);
  85     }
  86 }
  87
  88 void
  89 TYPE (gsl_sort_vector) (TYPE (gsl_vector) * v)
  90 {
  91   TYPE (gsl_sort) (v->data, v->stride, v->size) ;
  92 }
  93