"Fossies" - the Fresh Open Source Software Archive

Member "heaplayers-351/benchmarks/roboop/newmat/sort.cpp" (17 Oct 2003, 4829 Bytes) of package /linux/misc/old/heaplayers_3_5_1.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "sort.cpp" see the Fossies "Dox" file reference documentation.

    1 //$$ sort.cpp                            Sorting
    2 
    3 // Copyright (C) 1991,2,3,4: R B Davies
    4 
    5 #define WANT_MATH
    6 
    7 #include "include.h"
    8 
    9 #include "newmatap.h"
   10 
   11 #ifdef use_namespace
   12 namespace NEWMAT {
   13 #endif
   14 
   15 
   16 /******************************** Quick sort ********************************/
   17 
   18 // Quicksort.
   19 // Essentially the method described in Sedgewick's algorithms in C++
   20 // My version is still partially recursive, unlike Segewick's, but the
   21 // smallest segment of each split is used in the recursion, so it should
   22 // not overlead the stack.
   23 
   24 // If the process does not seems to be converging an exception is thrown.
   25 
   26 
   27 #define DoSimpleSort 17            // when to switch to insert sort
   28 #define MaxDepth 50                // maximum recursion depth
   29 
   30 static void MyQuickSortDescending(Real* first, Real* last, int depth);
   31 static void InsertionSortDescending(Real* first, const int length,
   32    int guard);
   33 static Real SortThreeDescending(Real* a, Real* b, Real* c);
   34 
   35 static void MyQuickSortAscending(Real* first, Real* last, int depth);
   36 static void InsertionSortAscending(Real* first, const int length,
   37    int guard);
   38 
   39 
   40 void SortDescending(GeneralMatrix& GM)
   41 {
   42 
   43    Tracer et("QuickSortDescending");
   44 
   45    Real* data = GM.Store(); int max = GM.Storage();
   46 
   47    if (max > DoSimpleSort) MyQuickSortDescending(data, data + max - 1, 0);
   48    InsertionSortDescending(data, max, DoSimpleSort);
   49 
   50 }
   51 
   52 static Real SortThreeDescending(Real* a, Real* b, Real* c)
   53 {
   54    // sort *a, *b, *c; return *b; optimise for already sorted
   55    if (*a >= *b)
   56    {
   57       if (*b >= *c) return *b;
   58       else if (*a >= *c) { Real x = *c; *c = *b; *b = x; return x; }
   59       else { Real x = *a; *a = *c; *c = *b; *b = x; return x; }
   60    }
   61    else if (*c >= *b) { Real x = *c; *c = *a; *a = x; return *b; }
   62    else if (*a >= *c) { Real x = *a; *a = *b; *b = x; return x; }
   63    else { Real x = *c; *c = *a; *a = *b; *b = x; return x; }
   64 }
   65 
   66 static void InsertionSortDescending(Real* first, const int length,
   67    int guard)
   68 // guard gives the length of the sequence to scan to find first
   69 // element (eg = length)
   70 {
   71    if (length <= 1) return;
   72 
   73    // scan for first element
   74    Real* f = first; Real v = *f; Real* h = f;
   75    if (guard > length) guard = length; int i = guard - 1;
   76    while (i--) if (v < *(++f)) { v = *f; h = f; }
   77    *h = *first; *first = v;
   78 
   79    // do the sort
   80    i = length - 1; f = first;
   81    while (i--)
   82    {
   83       Real* g = f++; h = f; v = *h;
   84       while (*g < v) *h-- = *g--;
   85       *h = v;
   86    }
   87 }
   88 
   89 static void MyQuickSortDescending(Real* first, Real* last, int depth)
   90 {
   91    for (;;)
   92    {
   93       const int length = last - first + 1;
   94       if (length < DoSimpleSort) return;
   95       if (depth++ > MaxDepth)
   96          Throw(ConvergenceException("QuickSortDescending fails: "));
   97       Real* centre = first + length/2;
   98       const Real test = SortThreeDescending(first, centre, last);
   99       Real* f = first; Real* l = last;
  100       for (;;)
  101       {
  102          while (*(++f) > test) {}
  103          while (*(--l) < test) {}
  104          if (l <= f) break;
  105          const Real temp = *f; *f = *l; *l = temp;
  106       }
  107       if (f > centre) { MyQuickSortDescending(l+1, last, depth); last = f-1; }
  108       else { MyQuickSortDescending(first, f-1, depth); first = l+1; }
  109    }
  110 }
  111 
  112 void SortAscending(GeneralMatrix& GM)
  113 {
  114 
  115    Tracer et("QuickSortAscending");
  116 
  117    Real* data = GM.Store(); int max = GM.Storage();
  118 
  119    if (max > DoSimpleSort) MyQuickSortAscending(data, data + max - 1, 0);
  120    InsertionSortAscending(data, max, DoSimpleSort);
  121 
  122 }
  123 
  124 static void InsertionSortAscending(Real* first, const int length,
  125    int guard)
  126 // guard gives the length of the sequence to scan to find first
  127 // element (eg guard = length)
  128 {
  129    if (length <= 1) return;
  130 
  131    // scan for first element
  132    Real* f = first; Real v = *f; Real* h = f;
  133    if (guard > length) guard = length; int i = guard - 1;
  134    while (i--) if (v > *(++f)) { v = *f; h = f; }
  135    *h = *first; *first = v;
  136 
  137    // do the sort
  138    i = length - 1; f = first;
  139    while (i--)
  140    {
  141       Real* g = f++; h = f; v = *h;
  142       while (*g > v) *h-- = *g--;
  143       *h = v;
  144    }
  145 }
  146 static void MyQuickSortAscending(Real* first, Real* last, int depth)
  147 {
  148    for (;;)
  149    {
  150       const int length = last - first + 1;
  151       if (length < DoSimpleSort) return;
  152       if (depth++ > MaxDepth)
  153          Throw(ConvergenceException("QuickSortAscending fails: "));
  154       Real* centre = first + length/2;
  155       const Real test = SortThreeDescending(last, centre, first);
  156       Real* f = first; Real* l = last;
  157       for (;;)
  158       {
  159          while (*(++f) < test) {}
  160          while (*(--l) > test) {}
  161          if (l <= f) break;
  162          const Real temp = *f; *f = *l; *l = temp;
  163       }
  164       if (f > centre) { MyQuickSortAscending(l+1, last, depth); last = f-1; }
  165       else { MyQuickSortAscending(first, f-1, depth); first = l+1; }
  166    }
  167 }
  168 
  169 #ifdef use_namespace
  170 }
  171 #endif
  172