fusion_sort.cc

   1
   2 ///////////////////////////////////////////////////////////////////////////
   3 // This program is free software: you can redistribute it and/or modify  //
   4 // it under the terms of the version 3 of the GNU General Public License //
   5 // as published by the Free Software Foundation.                         //
   6 //                                                                       //
   7 // This program is distributed in the hope that it will be useful, but   //
   8 // WITHOUT ANY WARRANTY; without even the implied warranty of            //
   9 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU      //
  10 // General Public License for more details.                              //
  11 //                                                                       //
  12 // You should have received a copy of the GNU General Public License     //
  13 // along with this program. If not, see <http://www.gnu.org/licenses/>.  //
  14 //                                                                       //
  15 // Written by Francois Fleuret                                           //
  16 // (C) Idiap Research Institute                                          //
  17 //                                                                       //
  18 // Contact <francois.fleuret@idiap.ch> for comments & bug reports        //
  19 ///////////////////////////////////////////////////////////////////////////
  20
  21 #include "fusion_sort.h"
  22 #include <string.h>
  23
  24 inline void indexed_fusion(int na, int *ia, int nb, int *ib, int *ic, scalar_t *values) {
  25   int *ma = ia + na, *mb = ib + nb;
  26   while(ia < ma && ib < mb)
  27     if(values[*ia] <= values[*ib]) *(ic++) = *(ia++);
  28     else                           *(ic++) = *(ib++);
  29   while(ia < ma) *(ic++) = *(ia++);
  30   while(ib < mb) *(ic++) = *(ib++);
  31 }
  32
  33 void indexed_fusion_sort(int n, int *from, int *result, scalar_t *values) {
  34   ASSERT(n > 0);
  35   if(n == 1) result[0] = from[0];
  36   else {
  37     int k = n/2;
  38     indexed_fusion_sort(k, from, result, values);
  39     indexed_fusion_sort(n - k, from + k, result + k, values);
  40     memcpy((void *) from, (void *) result, n * sizeof(int));
  41     indexed_fusion(k, from, n - k, from + k, result, values);
  42   }
  43 }
  44
  45 // Sorting in decreasing order
  46
  47 inline void indexed_fusion_dec(int na, int *ia,
  48                            int nb, int *ib,
  49                            int *ic, scalar_t *values) {
  50   int *ma = ia + na, *mb = ib + nb;
  51   while(ia < ma && ib < mb)
  52     if(values[*ia] > values[*ib]) *(ic++) = *(ia++);
  53     else                          *(ic++) = *(ib++);
  54   while(ia < ma) *(ic++) = *(ia++);
  55   while(ib < mb) *(ic++) = *(ib++);
  56 }
  57
  58 void indexed_fusion_dec_sort(int n, int *from, int *result, scalar_t *values) {
  59   ASSERT(n > 0);
  60   if(n == 1) result[0] = from[0];
  61   else {
  62     int k = n/2;
  63     indexed_fusion_dec_sort(k, from, result, values);
  64     indexed_fusion_dec_sort(n - k, from + k, result + k, values);
  65     memcpy((void *) from, (void *) result, n * sizeof(int));
  66     indexed_fusion_dec(k, from, n - k, from + k, result, values);
  67   }
  68 }
  69
  70 void fusion_two_cells(int n1, scalar_t *cell1, int n2, scalar_t *cell2, scalar_t *result) {
  71   scalar_t *max1 = cell1 + n1, *max2 = cell2 + n2;
  72   while(cell1 < max1 && cell2 < max2) {
  73     if(*(cell1) <= *(cell2)) *(result++) = *(cell1++);
  74     else                     *(result++) = *(cell2++);
  75   }
  76   while(cell1 < max1) *(result++) = *(cell1++);
  77   while(cell2 < max2) *(result++) = *(cell2++);
  78 }
  79
  80 void fusion_sort(int n, scalar_t *from, scalar_t *result) {
  81   if(n > 1) {
  82     fusion_sort(n/2, from, result);
  83     fusion_sort(n - n/2, from + n/2, result + n/2);
  84     memcpy(from, result, sizeof(scalar_t) * n);
  85     fusion_two_cells(n/2, from, n - n/2, from + n/2, result);
  86   } else result[0] = from[0];
  87 }