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, (C) IDIAP                                //
  16 // Contact <francois.fleuret@idiap.ch> for comments & bug reports        //
  17 ///////////////////////////////////////////////////////////////////////////
  18
  19 #include "fusion_sort.h"
  20 #include <string.h>
  21
  22 inline void indexed_fusion(int na, int *ia, int nb, int *ib, int *ic, scalar_t *values) {
  23   int *ma = ia + na, *mb = ib + nb;
  24   while(ia < ma && ib < mb)
  25     if(values[*ia] <= values[*ib]) *(ic++) = *(ia++);
  26     else                           *(ic++) = *(ib++);
  27   while(ia < ma) *(ic++) = *(ia++);
  28   while(ib < mb) *(ic++) = *(ib++);
  29 }
  30
  31 void indexed_fusion_sort(int n, int *from, int *result, scalar_t *values) {
  32   ASSERT(n > 0);
  33   if(n == 1) result[0] = from[0];
  34   else {
  35     int k = n/2;
  36     indexed_fusion_sort(k, from, result, values);
  37     indexed_fusion_sort(n - k, from + k, result + k, values);
  38     memcpy((void *) from, (void *) result, n * sizeof(int));
  39     indexed_fusion(k, from, n - k, from + k, result, values);
  40   }
  41 }
  42
  43 // Sorting in decreasing order
  44
  45 inline void indexed_fusion_dec(int na, int *ia,
  46                            int nb, int *ib,
  47                            int *ic, scalar_t *values) {
  48   int *ma = ia + na, *mb = ib + nb;
  49   while(ia < ma && ib < mb)
  50     if(values[*ia] > values[*ib]) *(ic++) = *(ia++);
  51     else                          *(ic++) = *(ib++);
  52   while(ia < ma) *(ic++) = *(ia++);
  53   while(ib < mb) *(ic++) = *(ib++);
  54 }
  55
  56 void indexed_fusion_dec_sort(int n, int *from, int *result, scalar_t *values) {
  57   ASSERT(n > 0);
  58   if(n == 1) result[0] = from[0];
  59   else {
  60     int k = n/2;
  61     indexed_fusion_dec_sort(k, from, result, values);
  62     indexed_fusion_dec_sort(n - k, from + k, result + k, values);
  63     memcpy((void *) from, (void *) result, n * sizeof(int));
  64     indexed_fusion_dec(k, from, n - k, from + k, result, values);
  65   }
  66 }
  67
  68 void fusion_two_cells(int n1, scalar_t *cell1, int n2, scalar_t *cell2, scalar_t *result) {
  69   scalar_t *max1 = cell1 + n1, *max2 = cell2 + n2;
  70   while(cell1 < max1 && cell2 < max2) {
  71     if(*(cell1) <= *(cell2)) *(result++) = *(cell1++);
  72     else                     *(result++) = *(cell2++);
  73   }
  74   while(cell1 < max1) *(result++) = *(cell1++);
  75   while(cell2 < max2) *(result++) = *(cell2++);
  76 }
  77
  78 void fusion_sort(int n, scalar_t *from, scalar_t *result) {
  79   if(n > 1) {
  80     fusion_sort(n/2, from, result);
  81     fusion_sort(n - n/2, from + n/2, result + n/2);
  82     memcpy(from, result, sizeof(scalar_t) * n);
  83     fusion_two_cells(n/2, from, n - n/2, from + n/2, result);
  84   } else result[0] = from[0];
  85 }