## "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 hlOpen(12,1);{
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 hlOpen(41,2);{
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 hlClose(2, 50);}
51
52 static Real SortThreeDescending(Real* a, Real* b, Real* c)
53 hlOpen(53,2);{
54    // sort *a, *b, *c; return *b; optimise for already sorted
55    if (*a >= *b)
56    hlOpen(56,3);{
57       if (*b >= *c) return *b;
58       else if (*a >= *c) hlOpen(58,4);{ Real x = *c; *c = *b; *b = x; return x; hlClose(5, 58);}
59       else hlOpen(59,4);{ Real x = *a; *a = *c; *c = *b; *b = x; return x; hlClose(6, 59);}
60    hlClose(4, 60);}
61    else if (*c >= *b) hlOpen(61,3);{ Real x = *c; *c = *a; *a = x; return *b; hlClose(7, 61);}
62    else if (*a >= *c) hlOpen(62,3);{ Real x = *a; *a = *b; *b = x; return x; hlClose(8, 62);}
63    else hlOpen(63,3);{ Real x = *c; *c = *a; *a = *b; *b = x; return x; hlClose(9, 63);}
64 hlClose(3, 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 hlOpen(70,2);{
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)) hlOpen(76,3);{ v = *f; h = f; hlClose(11, 76);}
77    *h = *first; *first = v;
78
79    // do the sort
80    i = length - 1; f = first;
81    while (i--)
82    hlOpen(82,3);{
83       Real* g = f++; h = f; v = *h;
84       while (*g < v) *h-- = *g--;
85       *h = v;
86    hlClose(12, 86);}
87 hlClose(10, 87);}
88
89 static void MyQuickSortDescending(Real* first, Real* last, int depth)
90 hlOpen(90,2);{
91    for (;;)
92    hlOpen(92,3);{
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       hlOpen(101,4);{
102          while (*(++f) > test) hlOpen(102,5);{hlClose(16, 102);}
103          while (*(--l) < test) hlOpen(103,5);{hlClose(17, 103);}
104          if (l <= f) break;
105          const Real temp = *f; *f = *l; *l = temp;
106       hlClose(15, 106);}
107       if (f > centre) hlOpen(107,4);{ MyQuickSortDescending(l+1, last, depth); last = f-1; hlClose(18, 107);}
108       else hlOpen(108,4);{ MyQuickSortDescending(first, f-1, depth); first = l+1; hlClose(19, 108);}
109    hlClose(14, 109);}
110 hlClose(13, 110);}
111
112 void SortAscending(GeneralMatrix& GM)
113 hlOpen(113,2);{
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 hlClose(20, 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 hlOpen(128,2);{
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)) hlOpen(134,3);{ v = *f; h = f; hlClose(22, 134);}
135    *h = *first; *first = v;
136
137    // do the sort
138    i = length - 1; f = first;
139    while (i--)
140    hlOpen(140,3);{
141       Real* g = f++; h = f; v = *h;
142       while (*g > v) *h-- = *g--;
143       *h = v;
144    hlClose(23, 144);}
145 hlClose(21, 145);}
146 static void MyQuickSortAscending(Real* first, Real* last, int depth)
147 hlOpen(147,2);{
148    for (;;)
149    hlOpen(149,3);{
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       hlOpen(158,4);{
159          while (*(++f) < test) hlOpen(159,5);{hlClose(27, 159);}
160          while (*(--l) > test) hlOpen(160,5);{hlClose(28, 160);}
161          if (l <= f) break;
162          const Real temp = *f; *f = *l; *l = temp;
163       hlClose(26, 163);}
164       if (f > centre) hlOpen(164,4);{ MyQuickSortAscending(l+1, last, depth); last = f-1; hlClose(29, 164);}
165       else hlOpen(165,4);{ MyQuickSortAscending(first, f-1, depth); first = l+1; hlClose(30, 165);}
166    hlClose(25, 166);}
167 hlClose(24, 167);}
168
169 #ifdef use_namespace
170 hlClose(1, 170);}
171 #endif
172
```