tests/sorting/non_recursive_mergesort.cc

0001 // name=non_recursive_mergesort ; gcc $name.cc -g -std=c++11 -I$OPTICKS_PREFIX/include/SysRap -lstdc++ -o /tmp/$name && /tmp/$name
0002
0003 #include <iostream>
0004 #include "NP.hh"
0005
0006 /**
0007
0008 https://stackoverflow.com/questions/1557894/non-recursive-merge-sort
0009
0010 **/
0011
0012 template <typename T>
0013 void mergesort(int num, T* a, T* b)
0014 {
0015     int left, rght, wid, rend;
0016     int i,j,m,t;
0017
0018     for (int k=1; k < num; k *= 2 )
0019     {
0020         std::cout << " k " << k << std::endl ;
0021         for (left=0; left+k < num; left += k*2 )
0022         {
0023             rght = left + k;
0024             rend = rght + k;
0025
0026             std::cout
0027                 << " left " << left
0028                 << " rght " << rght
0029                 << " rend " << rend
0030                 << std::endl
0031                 ;
0032
0033             if (rend > num) rend = num;
0034
0035             m = left; i = left; j = rght;
0036             while (i < rght && j < rend)
0037             {
0038                 if (a[i] <= a[j])
0039                 {
0040                     b[m] = a[i]; i++;
0041                 }
0042                 else
0043                 {
0044                     b[m] = a[j]; j++;
0045                 }
0046                 m++;
0047             }
0048             while (i < rght)
0049             {
0050                 b[m]=a[i];
0051                 i++; m++;
0052             }
0053             while (j < rend)
0054             {
0055                 b[m]=a[j];
0056                 j++; m++;
0057             }
0058             for (m=left; m < rend; m++)
0059             {
0060                 a[m] = b[m];
0061             }
0062         }
0063     }
0064 }
0065
0066
0067 int main(int argc, char** argv)
0068 {
0069     const char* dir = argc > 1 ? argv[1] : "/tmp" ;
0070     NP* aa = NP::Load(dir, "a.npy") ;
0071     if( aa == nullptr ) return 1 ;
0072
0073     int num = aa->shape[0] ;
0074
0075     NP* tt = NP::Make<float>(num) ;
0076
0077     std::cout << "aa " << aa->sstr() << std::endl ;
0078     std::cout << "tt " << tt->sstr() << std::endl ;
0079
0080     float* a = aa->values<float>();
0081     float* b = tt->values<float>();
0082
0083     std::cout << " a[i] " ;
0084     for(int i=0 ; i < 10 ; i++) std::cout << a[i] << " " ;
0085     std::cout << std::endl ;
0086
0087     mergesort<float>( num, a, b);
0088
0089     aa->save(dir, "b.npy");
0090
0091     return 0 ;
0092 }
0093
0094