| 1 | <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> |
|---|
| 2 | <html><head><meta http-equiv="Content-Type" content="text/html;charset=UTF-8"> |
|---|
| 3 | <title>mixpp: sort.h Source File</title> |
|---|
| 4 | <link href="tabs.css" rel="stylesheet" type="text/css"> |
|---|
| 5 | <link href="doxygen.css" rel="stylesheet" type="text/css"> |
|---|
| 6 | </head><body> |
|---|
| 7 | <!-- Generated by Doxygen 1.5.8 --> |
|---|
| 8 | <script type="text/javascript"> |
|---|
| 9 | <!-- |
|---|
| 10 | function changeDisplayState (e){ |
|---|
| 11 | var num=this.id.replace(/[^[0-9]/g,''); |
|---|
| 12 | var button=this.firstChild; |
|---|
| 13 | var sectionDiv=document.getElementById('dynsection'+num); |
|---|
| 14 | if (sectionDiv.style.display=='none'||sectionDiv.style.display==''){ |
|---|
| 15 | sectionDiv.style.display='block'; |
|---|
| 16 | button.src='open.gif'; |
|---|
| 17 | }else{ |
|---|
| 18 | sectionDiv.style.display='none'; |
|---|
| 19 | button.src='closed.gif'; |
|---|
| 20 | } |
|---|
| 21 | } |
|---|
| 22 | function initDynSections(){ |
|---|
| 23 | var divs=document.getElementsByTagName('div'); |
|---|
| 24 | var sectionCounter=1; |
|---|
| 25 | for(var i=0;i<divs.length-1;i++){ |
|---|
| 26 | if(divs[i].className=='dynheader'&&divs[i+1].className=='dynsection'){ |
|---|
| 27 | var header=divs[i]; |
|---|
| 28 | var section=divs[i+1]; |
|---|
| 29 | var button=header.firstChild; |
|---|
| 30 | if (button!='IMG'){ |
|---|
| 31 | divs[i].insertBefore(document.createTextNode(' '),divs[i].firstChild); |
|---|
| 32 | button=document.createElement('img'); |
|---|
| 33 | divs[i].insertBefore(button,divs[i].firstChild); |
|---|
| 34 | } |
|---|
| 35 | header.style.cursor='pointer'; |
|---|
| 36 | header.onclick=changeDisplayState; |
|---|
| 37 | header.id='dynheader'+sectionCounter; |
|---|
| 38 | button.src='closed.gif'; |
|---|
| 39 | section.id='dynsection'+sectionCounter; |
|---|
| 40 | section.style.display='none'; |
|---|
| 41 | section.style.marginLeft='14px'; |
|---|
| 42 | sectionCounter++; |
|---|
| 43 | } |
|---|
| 44 | } |
|---|
| 45 | } |
|---|
| 46 | window.onload = initDynSections; |
|---|
| 47 | --> |
|---|
| 48 | </script> |
|---|
| 49 | <div class="navigation" id="top"> |
|---|
| 50 | <div class="tabs"> |
|---|
| 51 | <ul> |
|---|
| 52 | <li><a href="main.html"><span>Main Page</span></a></li> |
|---|
| 53 | <li><a href="pages.html"><span>Related Pages</span></a></li> |
|---|
| 54 | <li><a href="modules.html"><span>Modules</span></a></li> |
|---|
| 55 | <li><a href="annotated.html"><span>Classes</span></a></li> |
|---|
| 56 | <li class="current"><a href="files.html"><span>Files</span></a></li> |
|---|
| 57 | </ul> |
|---|
| 58 | </div> |
|---|
| 59 | <div class="tabs"> |
|---|
| 60 | <ul> |
|---|
| 61 | <li><a href="files.html"><span>File List</span></a></li> |
|---|
| 62 | <li><a href="globals.html"><span>File Members</span></a></li> |
|---|
| 63 | </ul> |
|---|
| 64 | </div> |
|---|
| 65 | <h1>sort.h</h1><a href="sort_8h.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 |
|---|
| 66 | <a name="l00029"></a>00029 <span class="preprocessor">#ifndef SORT_H</span> |
|---|
| 67 | <a name="l00030"></a>00030 <span class="preprocessor"></span><span class="preprocessor">#define SORT_H</span> |
|---|
| 68 | <a name="l00031"></a>00031 <span class="preprocessor"></span> |
|---|
| 69 | <a name="l00032"></a>00032 <span class="preprocessor">#include <<a class="code" href="vec_8h.html" title="Templated Vector Class Definitions.">itpp/base/vec.h</a>></span> |
|---|
| 70 | <a name="l00033"></a>00033 <span class="preprocessor">#include <<a class="code" href="converters_8h.html" title="Definitions of converters between different vector and matrix types.">itpp/base/converters.h</a>></span> |
|---|
| 71 | <a name="l00034"></a>00034 <span class="preprocessor">#include <<a class="code" href="log__exp_8h.html" title="Logarithmic and exponenential functions - header file.">itpp/base/math/log_exp.h</a>></span> |
|---|
| 72 | <a name="l00035"></a>00035 |
|---|
| 73 | <a name="l00036"></a>00036 |
|---|
| 74 | <a name="l00037"></a>00037 <span class="keyword">namespace </span>itpp |
|---|
| 75 | <a name="l00038"></a>00038 { |
|---|
| 76 | <a name="l00039"></a>00039 |
|---|
| 77 | <a name="l00048"></a>00048 <span class="keyword">enum</span> SORTING_METHOD { INTROSORT = 0, QUICKSORT = 1, HEAPSORT = 2, |
|---|
| 78 | <a name="l00049"></a>00049 INSERTSORT = 3 |
|---|
| 79 | <a name="l00050"></a>00050 }; |
|---|
| 80 | <a name="l00051"></a>00051 |
|---|
| 81 | <a name="l00098"></a>00098 <span class="keyword">template</span><<span class="keyword">class</span> T> |
|---|
| 82 | <a name="l00099"></a><a class="code" href="classitpp_1_1Sort.html">00099</a> <span class="keyword">class </span><a class="code" href="classitpp_1_1Sort.html" title="Class for sorting of vectors.">Sort</a> |
|---|
| 83 | <a name="l00100"></a>00100 { |
|---|
| 84 | <a name="l00101"></a>00101 <span class="keyword">public</span>: |
|---|
| 85 | <a name="l00103"></a><a class="code" href="classitpp_1_1Sort.html#e89f0cdcd430af54b41520385b06c9b9">00103</a> <a class="code" href="classitpp_1_1Sort.html#e89f0cdcd430af54b41520385b06c9b9" title="Constructor that sets Intro Sort method by default.">Sort</a>(SORTING_METHOD method = INTROSORT): sort_method(method) {} |
|---|
| 86 | <a name="l00104"></a>00104 |
|---|
| 87 | <a name="l00106"></a><a class="code" href="classitpp_1_1Sort.html#0fe6dbe275ae1eb38d34e0bea3604044">00106</a> <span class="keywordtype">void</span> <a class="code" href="classitpp_1_1Sort.html#0fe6dbe275ae1eb38d34e0bea3604044" title="Set sorting method.">set_method</a>(SORTING_METHOD method) { sort_method = method; } |
|---|
| 88 | <a name="l00107"></a>00107 |
|---|
| 89 | <a name="l00109"></a><a class="code" href="classitpp_1_1Sort.html#17222b0f57479cf93632b0caabbe6abc">00109</a> SORTING_METHOD <a class="code" href="classitpp_1_1Sort.html#17222b0f57479cf93632b0caabbe6abc" title="Get current sorting method.">get_method</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> sort_method; } |
|---|
| 90 | <a name="l00110"></a>00110 |
|---|
| 91 | <a name="l00118"></a>00118 <span class="keywordtype">void</span> <a class="code" href="classitpp_1_1Sort.html#0ccff5c48c69b4680347935039a0d3f1" title="Sorting function of a subset of a vector data.">sort</a>(<span class="keywordtype">int</span> low, <span class="keywordtype">int</span> high, <a class="code" href="classitpp_1_1Vec.html">Vec<T></a> &data); |
|---|
| 92 | <a name="l00119"></a>00119 |
|---|
| 93 | <a name="l00127"></a>00127 ivec <a class="code" href="classitpp_1_1Sort.html#5eefe31327b1987cf9799562333ebccb" title="Sorting function that returns a sorted index vector.">sort_index</a>(<span class="keywordtype">int</span> low, <span class="keywordtype">int</span> high, <span class="keyword">const</span> <a class="code" href="classitpp_1_1Vec.html">Vec<T></a> &data); |
|---|
| 94 | <a name="l00128"></a>00128 |
|---|
| 95 | <a name="l00142"></a>00142 <span class="keywordtype">void</span> <a class="code" href="classitpp_1_1Sort.html#5730b92e4812e1cd376619c16cda36d8" title="Introsort function of a subset of a vector data.">intro_sort</a>(<span class="keywordtype">int</span> low, <span class="keywordtype">int</span> high, <span class="keywordtype">int</span> max_depth, <a class="code" href="classitpp_1_1Vec.html">Vec<T></a> &data); |
|---|
| 96 | <a name="l00143"></a>00143 |
|---|
| 97 | <a name="l00157"></a>00157 ivec <a class="code" href="classitpp_1_1Sort.html#b738462d713bcdb42d758e730819b499" title="Introsort function, which returns a sorted index vector.">intro_sort_index</a>(<span class="keywordtype">int</span> low, <span class="keywordtype">int</span> high, <span class="keywordtype">int</span> max_depth, |
|---|
| 98 | <a name="l00158"></a>00158 <span class="keyword">const</span> <a class="code" href="classitpp_1_1Vec.html">Vec<T></a> &data); |
|---|
| 99 | <a name="l00159"></a>00159 |
|---|
| 100 | <a name="l00160"></a>00160 <span class="keyword">private</span>: |
|---|
| 101 | <a name="l00161"></a>00161 SORTING_METHOD sort_method; |
|---|
| 102 | <a name="l00162"></a>00162 |
|---|
| 103 | <a name="l00163"></a>00163 <span class="keywordtype">void</span> IntroSort(<span class="keywordtype">int</span> low, <span class="keywordtype">int</span> high, <span class="keywordtype">int</span> max_depth, T data[]); |
|---|
| 104 | <a name="l00164"></a>00164 <span class="keywordtype">void</span> IntroSort_Index(<span class="keywordtype">int</span> low, <span class="keywordtype">int</span> high, <span class="keywordtype">int</span> max_depth, <span class="keywordtype">int</span> indexlist[], |
|---|
| 105 | <a name="l00165"></a>00165 <span class="keyword">const</span> T data[]); |
|---|
| 106 | <a name="l00166"></a>00166 |
|---|
| 107 | <a name="l00167"></a>00167 <span class="keywordtype">void</span> QuickSort(<span class="keywordtype">int</span> low, <span class="keywordtype">int</span> high, T data[]); |
|---|
| 108 | <a name="l00168"></a>00168 <span class="keywordtype">void</span> QuickSort_Index(<span class="keywordtype">int</span> low, <span class="keywordtype">int</span> high, <span class="keywordtype">int</span> indexlist[], <span class="keyword">const</span> T data[]); |
|---|
| 109 | <a name="l00169"></a>00169 |
|---|
| 110 | <a name="l00170"></a>00170 <span class="keywordtype">void</span> HeapSort(<span class="keywordtype">int</span> low, <span class="keywordtype">int</span> high, T data[]); |
|---|
| 111 | <a name="l00171"></a>00171 <span class="keywordtype">void</span> HeapSort_Index(<span class="keywordtype">int</span> low, <span class="keywordtype">int</span> high, <span class="keywordtype">int</span> indexlist[], <span class="keyword">const</span> T data[]); |
|---|
| 112 | <a name="l00172"></a>00172 |
|---|
| 113 | <a name="l00173"></a>00173 <span class="keywordtype">void</span> InsertSort(<span class="keywordtype">int</span> low, <span class="keywordtype">int</span> high, T data[]); |
|---|
| 114 | <a name="l00174"></a>00174 <span class="keywordtype">void</span> InsertSort_Index(<span class="keywordtype">int</span> low, <span class="keywordtype">int</span> high, <span class="keywordtype">int</span> indexlist[], <span class="keyword">const</span> T data[]); |
|---|
| 115 | <a name="l00175"></a>00175 }; |
|---|
| 116 | <a name="l00176"></a>00176 |
|---|
| 117 | <a name="l00177"></a>00177 |
|---|
| 118 | <a name="l00186"></a>00186 <span class="keyword">template</span><<span class="keyword">class</span> T> |
|---|
| 119 | <a name="l00187"></a><a class="code" href="classitpp_1_1Vec.html#6d62d1911501ca2b7884c7506eb17125">00187</a> <span class="keywordtype">void</span> sort(<a class="code" href="classitpp_1_1Vec.html">Vec<T></a> &data, SORTING_METHOD method = INTROSORT) |
|---|
| 120 | <a name="l00188"></a>00188 { |
|---|
| 121 | <a name="l00189"></a>00189 <a class="code" href="classitpp_1_1Sort.html" title="Class for sorting of vectors.">Sort<T></a> s(method); |
|---|
| 122 | <a name="l00190"></a>00190 s.<a class="code" href="classitpp_1_1Sort.html#0ccff5c48c69b4680347935039a0d3f1" title="Sorting function of a subset of a vector data.">sort</a>(0, data.<a class="code" href="classitpp_1_1Vec.html#a906c893cd6184a774e4da8a47217d6a" title="The size of the vector.">size</a>() - 1, data); |
|---|
| 123 | <a name="l00191"></a>00191 } |
|---|
| 124 | <a name="l00192"></a>00192 |
|---|
| 125 | <a name="l00202"></a>00202 <span class="keyword">template</span><<span class="keyword">class</span> T> |
|---|
| 126 | <a name="l00203"></a><a class="code" href="classitpp_1_1Vec.html#0d210c6511931cde784bb4e6d92852ba">00203</a> <a class="code" href="classitpp_1_1Vec.html" title="Vector Class (Templated).">ivec</a> sort_index(<span class="keyword">const</span> <a class="code" href="classitpp_1_1Vec.html">Vec<T></a> &data, SORTING_METHOD method = INTROSORT) |
|---|
| 127 | <a name="l00204"></a>00204 { |
|---|
| 128 | <a name="l00205"></a>00205 <a class="code" href="classitpp_1_1Sort.html" title="Class for sorting of vectors.">Sort<T></a> s(method); |
|---|
| 129 | <a name="l00206"></a>00206 <span class="keywordflow">return</span> s.<a class="code" href="classitpp_1_1Sort.html#5eefe31327b1987cf9799562333ebccb" title="Sorting function that returns a sorted index vector.">sort_index</a>(0, data.<a class="code" href="classitpp_1_1Vec.html#a906c893cd6184a774e4da8a47217d6a" title="The size of the vector.">size</a>() - 1, data); |
|---|
| 130 | <a name="l00207"></a>00207 } |
|---|
| 131 | <a name="l00208"></a>00208 |
|---|
| 132 | <a name="l00209"></a>00209 |
|---|
| 133 | <a name="l00210"></a>00210 <span class="comment">// ----------------------------------------------------------------------</span> |
|---|
| 134 | <a name="l00211"></a>00211 <span class="comment">// Public functions for various sorting methods</span> |
|---|
| 135 | <a name="l00212"></a>00212 <span class="comment">// ----------------------------------------------------------------------</span> |
|---|
| 136 | <a name="l00213"></a>00213 |
|---|
| 137 | <a name="l00214"></a>00214 <span class="keyword">template</span><<span class="keyword">class</span> T> |
|---|
| 138 | <a name="l00215"></a><a class="code" href="classitpp_1_1Sort.html#0ccff5c48c69b4680347935039a0d3f1">00215</a> <span class="keywordtype">void</span> <a class="code" href="classitpp_1_1Sort.html#0ccff5c48c69b4680347935039a0d3f1" title="Sorting function of a subset of a vector data.">Sort<T>::sort</a>(<span class="keywordtype">int</span> low, <span class="keywordtype">int</span> high, <a class="code" href="classitpp_1_1Vec.html">Vec<T></a> &data) |
|---|
| 139 | <a name="l00216"></a>00216 { |
|---|
| 140 | <a name="l00217"></a>00217 <span class="keywordtype">int</span> N = data.<a class="code" href="classitpp_1_1Vec.html#a906c893cd6184a774e4da8a47217d6a" title="The size of the vector.">size</a>(); |
|---|
| 141 | <a name="l00218"></a>00218 <span class="comment">// Nothing to sort if data vector has only one or zero elements</span> |
|---|
| 142 | <a name="l00219"></a>00219 <span class="keywordflow">if</span> (N < 2) |
|---|
| 143 | <a name="l00220"></a>00220 <span class="keywordflow">return</span>; |
|---|
| 144 | <a name="l00221"></a>00221 |
|---|
| 145 | <a name="l00222"></a>00222 <a class="code" href="group__errorhandlingfunc.html#gd5c34b291e5018534fd2344486e2b5a1" title="Abort if t is not true.">it_assert</a>((low >= 0) && (high > low) && (high < N), <span class="stringliteral">"Sort::sort(): "</span> |
|---|
| 146 | <a name="l00223"></a>00223 <span class="stringliteral">"low or high out of bounds"</span>); |
|---|
| 147 | <a name="l00224"></a>00224 |
|---|
| 148 | <a name="l00225"></a>00225 <span class="keywordflow">switch</span> (sort_method) { |
|---|
| 149 | <a name="l00226"></a>00226 <span class="keywordflow">case</span> INTROSORT: |
|---|
| 150 | <a name="l00227"></a>00227 IntroSort(low, high, <a class="code" href="group__logexpfunc.html#g4a774bd5418520f574eddf730333dada" title="Calculate the number of bits needed to represent a numer of levels saved in a vector...">levels2bits</a>(N), data.<a class="code" href="classitpp_1_1Vec.html#b467e00509668d5f812431dfa17cc2b6" title="Get the pointer to the internal structure. Not recommended for use.">_data</a>()); |
|---|
| 151 | <a name="l00228"></a>00228 <span class="keywordflow">break</span>; |
|---|
| 152 | <a name="l00229"></a>00229 <span class="keywordflow">case</span> QUICKSORT: |
|---|
| 153 | <a name="l00230"></a>00230 QuickSort(low, high, data.<a class="code" href="classitpp_1_1Vec.html#b467e00509668d5f812431dfa17cc2b6" title="Get the pointer to the internal structure. Not recommended for use.">_data</a>()); |
|---|
| 154 | <a name="l00231"></a>00231 <span class="keywordflow">break</span>; |
|---|
| 155 | <a name="l00232"></a>00232 <span class="keywordflow">case</span> HEAPSORT: |
|---|
| 156 | <a name="l00233"></a>00233 HeapSort(low, high, data.<a class="code" href="classitpp_1_1Vec.html#b467e00509668d5f812431dfa17cc2b6" title="Get the pointer to the internal structure. Not recommended for use.">_data</a>()); |
|---|
| 157 | <a name="l00234"></a>00234 <span class="keywordflow">break</span>; |
|---|
| 158 | <a name="l00235"></a>00235 <span class="keywordflow">case</span> INSERTSORT: |
|---|
| 159 | <a name="l00236"></a>00236 InsertSort(low, high, data.<a class="code" href="classitpp_1_1Vec.html#b467e00509668d5f812431dfa17cc2b6" title="Get the pointer to the internal structure. Not recommended for use.">_data</a>()); |
|---|
| 160 | <a name="l00237"></a>00237 <span class="keywordflow">break</span>; |
|---|
| 161 | <a name="l00238"></a>00238 <span class="keywordflow">default</span>: |
|---|
| 162 | <a name="l00239"></a>00239 <a class="code" href="group__errorhandlingfunc.html#g22d38e98332f9edff88cc501463eedce" title="Abort unconditionally.">it_error</a>(<span class="stringliteral">"Sort<T>::sort(): Unknown sorting method"</span>); |
|---|
| 163 | <a name="l00240"></a>00240 } |
|---|
| 164 | <a name="l00241"></a>00241 } |
|---|
| 165 | <a name="l00242"></a>00242 |
|---|
| 166 | <a name="l00243"></a>00243 |
|---|
| 167 | <a name="l00244"></a>00244 <span class="keyword">template</span><<span class="keyword">class</span> T> |
|---|
| 168 | <a name="l00245"></a><a class="code" href="classitpp_1_1Sort.html#5eefe31327b1987cf9799562333ebccb">00245</a> ivec <a class="code" href="classitpp_1_1Sort.html#5eefe31327b1987cf9799562333ebccb" title="Sorting function that returns a sorted index vector.">Sort<T>::sort_index</a>(<span class="keywordtype">int</span> low, <span class="keywordtype">int</span> high, <span class="keyword">const</span> <a class="code" href="classitpp_1_1Vec.html">Vec<T></a> &data) |
|---|
| 169 | <a name="l00246"></a>00246 { |
|---|
| 170 | <a name="l00247"></a>00247 <span class="keywordtype">int</span> N = data.<a class="code" href="classitpp_1_1Vec.html#a906c893cd6184a774e4da8a47217d6a" title="The size of the vector.">size</a>(); |
|---|
| 171 | <a name="l00248"></a>00248 <span class="comment">// Nothing to sort if data vector has only one or zero elements</span> |
|---|
| 172 | <a name="l00249"></a>00249 <span class="keywordflow">if</span> (N == 1) |
|---|
| 173 | <a name="l00250"></a>00250 <span class="keywordflow">return</span> ivec(<span class="stringliteral">"0"</span>); |
|---|
| 174 | <a name="l00251"></a>00251 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (N == 0) |
|---|
| 175 | <a name="l00252"></a>00252 <span class="keywordflow">return</span> ivec(); |
|---|
| 176 | <a name="l00253"></a>00253 |
|---|
| 177 | <a name="l00254"></a>00254 <a class="code" href="group__errorhandlingfunc.html#gd5c34b291e5018534fd2344486e2b5a1" title="Abort if t is not true.">it_assert</a>((low >= 0) && (high > low) && (high < N), <span class="stringliteral">"Sort::sort(): "</span> |
|---|
| 178 | <a name="l00255"></a>00255 <span class="stringliteral">"low or high out of bounds"</span>); |
|---|
| 179 | <a name="l00256"></a>00256 |
|---|
| 180 | <a name="l00257"></a>00257 ivec indexlist(N); |
|---|
| 181 | <a name="l00258"></a>00258 <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = 0; i < N; ++i) { |
|---|
| 182 | <a name="l00259"></a>00259 indexlist(i) = i; |
|---|
| 183 | <a name="l00260"></a>00260 } |
|---|
| 184 | <a name="l00261"></a>00261 |
|---|
| 185 | <a name="l00262"></a>00262 <span class="keywordflow">switch</span> (sort_method) { |
|---|
| 186 | <a name="l00263"></a>00263 <span class="keywordflow">case</span> INTROSORT: |
|---|
| 187 | <a name="l00264"></a>00264 IntroSort_Index(low, high, <a class="code" href="group__logexpfunc.html#g4a774bd5418520f574eddf730333dada" title="Calculate the number of bits needed to represent a numer of levels saved in a vector...">levels2bits</a>(N), indexlist._data(), |
|---|
| 188 | <a name="l00265"></a>00265 data.<a class="code" href="classitpp_1_1Vec.html#b467e00509668d5f812431dfa17cc2b6" title="Get the pointer to the internal structure. Not recommended for use.">_data</a>()); |
|---|
| 189 | <a name="l00266"></a>00266 <span class="keywordflow">break</span>; |
|---|
| 190 | <a name="l00267"></a>00267 <span class="keywordflow">case</span> QUICKSORT: |
|---|
| 191 | <a name="l00268"></a>00268 QuickSort_Index(low, high, indexlist._data(), data.<a class="code" href="classitpp_1_1Vec.html#b467e00509668d5f812431dfa17cc2b6" title="Get the pointer to the internal structure. Not recommended for use.">_data</a>()); |
|---|
| 192 | <a name="l00269"></a>00269 <span class="keywordflow">break</span>; |
|---|
| 193 | <a name="l00270"></a>00270 <span class="keywordflow">case</span> HEAPSORT: |
|---|
| 194 | <a name="l00271"></a>00271 HeapSort_Index(low, high, indexlist._data(), data.<a class="code" href="classitpp_1_1Vec.html#b467e00509668d5f812431dfa17cc2b6" title="Get the pointer to the internal structure. Not recommended for use.">_data</a>()); |
|---|
| 195 | <a name="l00272"></a>00272 <span class="keywordflow">break</span>; |
|---|
| 196 | <a name="l00273"></a>00273 <span class="keywordflow">case</span> INSERTSORT: |
|---|
| 197 | <a name="l00274"></a>00274 InsertSort_Index(low, high, indexlist._data(), data.<a class="code" href="classitpp_1_1Vec.html#b467e00509668d5f812431dfa17cc2b6" title="Get the pointer to the internal structure. Not recommended for use.">_data</a>()); |
|---|
| 198 | <a name="l00275"></a>00275 <span class="keywordflow">break</span>; |
|---|
| 199 | <a name="l00276"></a>00276 <span class="keywordflow">default</span>: |
|---|
| 200 | <a name="l00277"></a>00277 <a class="code" href="group__errorhandlingfunc.html#g22d38e98332f9edff88cc501463eedce" title="Abort unconditionally.">it_error</a>(<span class="stringliteral">"Sort<T>::sort_index(): Unknown sorting method"</span>); |
|---|
| 201 | <a name="l00278"></a>00278 } |
|---|
| 202 | <a name="l00279"></a>00279 |
|---|
| 203 | <a name="l00280"></a>00280 <span class="keywordflow">return</span> indexlist; |
|---|
| 204 | <a name="l00281"></a>00281 } |
|---|
| 205 | <a name="l00282"></a>00282 |
|---|
| 206 | <a name="l00283"></a>00283 |
|---|
| 207 | <a name="l00284"></a>00284 <span class="comment">// INTRO SORT</span> |
|---|
| 208 | <a name="l00285"></a>00285 <span class="keyword">template</span><<span class="keyword">class</span> T> |
|---|
| 209 | <a name="l00286"></a><a class="code" href="classitpp_1_1Sort.html#5730b92e4812e1cd376619c16cda36d8">00286</a> <span class="keywordtype">void</span> <a class="code" href="classitpp_1_1Sort.html#5730b92e4812e1cd376619c16cda36d8" title="Introsort function of a subset of a vector data.">Sort<T>::intro_sort</a>(<span class="keywordtype">int</span> low, <span class="keywordtype">int</span> high, <span class="keywordtype">int</span> max_depth, <a class="code" href="classitpp_1_1Vec.html">Vec<T></a> &data) |
|---|
| 210 | <a name="l00287"></a>00287 { |
|---|
| 211 | <a name="l00288"></a>00288 <a class="code" href="group__errorhandlingfunc.html#gd5c34b291e5018534fd2344486e2b5a1" title="Abort if t is not true.">it_assert</a>((low >= 0) && (high > low) && (high < data.<a class="code" href="classitpp_1_1Vec.html#a906c893cd6184a774e4da8a47217d6a" title="The size of the vector.">size</a>()), |
|---|
| 212 | <a name="l00289"></a>00289 <span class="stringliteral">"Sort::sort(): low or high out of bounds"</span>); |
|---|
| 213 | <a name="l00290"></a>00290 IntroSort(low, high, max_depth, data.<a class="code" href="classitpp_1_1Vec.html#b467e00509668d5f812431dfa17cc2b6" title="Get the pointer to the internal structure. Not recommended for use.">_data</a>()); |
|---|
| 214 | <a name="l00291"></a>00291 } |
|---|
| 215 | <a name="l00292"></a>00292 |
|---|
| 216 | <a name="l00293"></a>00293 <span class="comment">// INTRO SORT INDEX</span> |
|---|
| 217 | <a name="l00294"></a>00294 <span class="keyword">template</span><<span class="keyword">class</span> T> |
|---|
| 218 | <a name="l00295"></a><a class="code" href="classitpp_1_1Sort.html#b738462d713bcdb42d758e730819b499">00295</a> ivec <a class="code" href="classitpp_1_1Sort.html#b738462d713bcdb42d758e730819b499" title="Introsort function, which returns a sorted index vector.">Sort<T>::intro_sort_index</a>(<span class="keywordtype">int</span> low, <span class="keywordtype">int</span> high, <span class="keywordtype">int</span> max_depth, |
|---|
| 219 | <a name="l00296"></a>00296 <span class="keyword">const</span> <a class="code" href="classitpp_1_1Vec.html">Vec<T></a> &data) |
|---|
| 220 | <a name="l00297"></a>00297 { |
|---|
| 221 | <a name="l00298"></a>00298 <span class="keywordtype">int</span> N = data.<a class="code" href="classitpp_1_1Vec.html#a906c893cd6184a774e4da8a47217d6a" title="The size of the vector.">size</a>(); |
|---|
| 222 | <a name="l00299"></a>00299 <a class="code" href="group__errorhandlingfunc.html#gd5c34b291e5018534fd2344486e2b5a1" title="Abort if t is not true.">it_assert</a>((low >= 0) && (high > low) && (high < N), |
|---|
| 223 | <a name="l00300"></a>00300 <span class="stringliteral">"Sort::sort(): low or high out of bounds"</span>); |
|---|
| 224 | <a name="l00301"></a>00301 |
|---|
| 225 | <a name="l00302"></a>00302 ivec indexlist(N); |
|---|
| 226 | <a name="l00303"></a>00303 <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = 0; i < N; ++i) { |
|---|
| 227 | <a name="l00304"></a>00304 indexlist(i) = i; |
|---|
| 228 | <a name="l00305"></a>00305 } |
|---|
| 229 | <a name="l00306"></a>00306 |
|---|
| 230 | <a name="l00307"></a>00307 IntroSort_Index(low, high, max_depth, indexlist._data(), data.<a class="code" href="classitpp_1_1Vec.html#b467e00509668d5f812431dfa17cc2b6" title="Get the pointer to the internal structure. Not recommended for use.">_data</a>()); |
|---|
| 231 | <a name="l00308"></a>00308 |
|---|
| 232 | <a name="l00309"></a>00309 <span class="keywordflow">return</span> indexlist; |
|---|
| 233 | <a name="l00310"></a>00310 } |
|---|
| 234 | <a name="l00311"></a>00311 |
|---|
| 235 | <a name="l00312"></a>00312 |
|---|
| 236 | <a name="l00313"></a>00313 <span class="comment">// ----------------------------------------------------------------------</span> |
|---|
| 237 | <a name="l00314"></a>00314 <span class="comment">// Private functions for sorting methods</span> |
|---|
| 238 | <a name="l00315"></a>00315 <span class="comment">// ----------------------------------------------------------------------</span> |
|---|
| 239 | <a name="l00316"></a>00316 |
|---|
| 240 | <a name="l00317"></a>00317 <span class="keyword">template</span><<span class="keyword">class</span> T> |
|---|
| 241 | <a name="l00318"></a>00318 <span class="keywordtype">void</span> <a class="code" href="classitpp_1_1Sort.html" title="Class for sorting of vectors.">Sort<T>::IntroSort</a>(<span class="keywordtype">int</span> low, <span class="keywordtype">int</span> high, <span class="keywordtype">int</span> max_depth, T data[]) |
|---|
| 242 | <a name="l00319"></a>00319 { |
|---|
| 243 | <a name="l00320"></a>00320 <span class="keywordflow">if</span> (high - low > 16) { |
|---|
| 244 | <a name="l00321"></a>00321 max_depth--; |
|---|
| 245 | <a name="l00322"></a>00322 <span class="keywordflow">if</span> (max_depth == 0) { |
|---|
| 246 | <a name="l00323"></a>00323 HeapSort(low, high, data); |
|---|
| 247 | <a name="l00324"></a>00324 <span class="keywordflow">return</span>; |
|---|
| 248 | <a name="l00325"></a>00325 } |
|---|
| 249 | <a name="l00326"></a>00326 |
|---|
| 250 | <a name="l00327"></a>00327 <span class="keywordflow">if</span> (high > low) { |
|---|
| 251 | <a name="l00328"></a>00328 T a = data[low]; |
|---|
| 252 | <a name="l00329"></a>00329 <span class="keywordtype">int</span> plow = low; |
|---|
| 253 | <a name="l00330"></a>00330 <span class="keywordtype">int</span> phigh = high; |
|---|
| 254 | <a name="l00331"></a>00331 T test = data[phigh]; |
|---|
| 255 | <a name="l00332"></a>00332 <span class="keywordflow">while</span> (plow < phigh) { |
|---|
| 256 | <a name="l00333"></a>00333 <span class="keywordflow">if</span> (test < a) { |
|---|
| 257 | <a name="l00334"></a>00334 data[plow] = test; |
|---|
| 258 | <a name="l00335"></a>00335 plow++; |
|---|
| 259 | <a name="l00336"></a>00336 test = data[plow]; |
|---|
| 260 | <a name="l00337"></a>00337 } |
|---|
| 261 | <a name="l00338"></a>00338 <span class="keywordflow">else</span> { |
|---|
| 262 | <a name="l00339"></a>00339 data[phigh] = test; |
|---|
| 263 | <a name="l00340"></a>00340 phigh--; |
|---|
| 264 | <a name="l00341"></a>00341 test = data[phigh]; |
|---|
| 265 | <a name="l00342"></a>00342 } |
|---|
| 266 | <a name="l00343"></a>00343 } |
|---|
| 267 | <a name="l00344"></a>00344 data[plow] = a; |
|---|
| 268 | <a name="l00345"></a>00345 IntroSort(low, plow - 1, max_depth, data); |
|---|
| 269 | <a name="l00346"></a>00346 IntroSort(plow + 1, high, max_depth, data); |
|---|
| 270 | <a name="l00347"></a>00347 <span class="keywordflow">return</span>; |
|---|
| 271 | <a name="l00348"></a>00348 } |
|---|
| 272 | <a name="l00349"></a>00349 } |
|---|
| 273 | <a name="l00350"></a>00350 <span class="keywordflow">else</span> { |
|---|
| 274 | <a name="l00351"></a>00351 InsertSort(low, high, data); |
|---|
| 275 | <a name="l00352"></a>00352 <span class="keywordflow">return</span>; |
|---|
| 276 | <a name="l00353"></a>00353 } |
|---|
| 277 | <a name="l00354"></a>00354 } |
|---|
| 278 | <a name="l00355"></a>00355 |
|---|
| 279 | <a name="l00356"></a>00356 <span class="keyword">template</span><<span class="keyword">class</span> T> |
|---|
| 280 | <a name="l00357"></a>00357 <span class="keywordtype">void</span> Sort<T>::IntroSort_Index(<span class="keywordtype">int</span> low, <span class="keywordtype">int</span> high, <span class="keywordtype">int</span> max_depth, |
|---|
| 281 | <a name="l00358"></a>00358 <span class="keywordtype">int</span> indexlist[], <span class="keyword">const</span> T data[]) |
|---|
| 282 | <a name="l00359"></a>00359 { |
|---|
| 283 | <a name="l00360"></a>00360 <span class="keywordflow">if</span> (high - low > 16) { |
|---|
| 284 | <a name="l00361"></a>00361 max_depth--; |
|---|
| 285 | <a name="l00362"></a>00362 <span class="keywordflow">if</span> (max_depth == 0) { |
|---|
| 286 | <a name="l00363"></a>00363 HeapSort_Index(low, high, indexlist, data); |
|---|
| 287 | <a name="l00364"></a>00364 <span class="keywordflow">return</span>; |
|---|
| 288 | <a name="l00365"></a>00365 } |
|---|
| 289 | <a name="l00366"></a>00366 |
|---|
| 290 | <a name="l00367"></a>00367 <span class="keywordflow">if</span> (high > low) { |
|---|
| 291 | <a name="l00368"></a>00368 <span class="keywordtype">int</span> aindex = indexlist[low]; |
|---|
| 292 | <a name="l00369"></a>00369 T a = data[aindex]; |
|---|
| 293 | <a name="l00370"></a>00370 <span class="keywordtype">int</span> plow = low; |
|---|
| 294 | <a name="l00371"></a>00371 <span class="keywordtype">int</span> phigh = high; |
|---|
| 295 | <a name="l00372"></a>00372 <span class="keywordtype">int</span> testindex = indexlist[phigh]; |
|---|
| 296 | <a name="l00373"></a>00373 T test = data[testindex]; |
|---|
| 297 | <a name="l00374"></a>00374 <span class="keywordflow">while</span> (plow < phigh) { |
|---|
| 298 | <a name="l00375"></a>00375 <span class="keywordflow">if</span> (test < a) { |
|---|
| 299 | <a name="l00376"></a>00376 indexlist[plow] = testindex; |
|---|
| 300 | <a name="l00377"></a>00377 plow++; |
|---|
| 301 | <a name="l00378"></a>00378 testindex = indexlist[plow]; |
|---|
| 302 | <a name="l00379"></a>00379 test = data[testindex]; |
|---|
| 303 | <a name="l00380"></a>00380 } |
|---|
| 304 | <a name="l00381"></a>00381 <span class="keywordflow">else</span> { |
|---|
| 305 | <a name="l00382"></a>00382 indexlist[phigh] = testindex; |
|---|
| 306 | <a name="l00383"></a>00383 phigh--; |
|---|
| 307 | <a name="l00384"></a>00384 testindex = indexlist[phigh]; |
|---|
| 308 | <a name="l00385"></a>00385 test = data[testindex]; |
|---|
| 309 | <a name="l00386"></a>00386 } |
|---|
| 310 | <a name="l00387"></a>00387 } |
|---|
| 311 | <a name="l00388"></a>00388 indexlist[plow] = aindex; |
|---|
| 312 | <a name="l00389"></a>00389 IntroSort_Index(low, plow - 1, max_depth, indexlist, data); |
|---|
| 313 | <a name="l00390"></a>00390 IntroSort_Index(plow + 1, high, max_depth, indexlist, data); |
|---|
| 314 | <a name="l00391"></a>00391 } |
|---|
| 315 | <a name="l00392"></a>00392 } |
|---|
| 316 | <a name="l00393"></a>00393 <span class="keywordflow">else</span> { |
|---|
| 317 | <a name="l00394"></a>00394 InsertSort_Index(low, high, indexlist, data); |
|---|
| 318 | <a name="l00395"></a>00395 <span class="keywordflow">return</span>; |
|---|
| 319 | <a name="l00396"></a>00396 } |
|---|
| 320 | <a name="l00397"></a>00397 } |
|---|
| 321 | <a name="l00398"></a>00398 |
|---|
| 322 | <a name="l00399"></a>00399 <span class="keyword">template</span> <<span class="keyword">class</span> T> |
|---|
| 323 | <a name="l00400"></a>00400 <span class="keywordtype">void</span> Sort<T>::QuickSort(<span class="keywordtype">int</span> low, <span class="keywordtype">int</span> high, T data[]) |
|---|
| 324 | <a name="l00401"></a>00401 { |
|---|
| 325 | <a name="l00402"></a>00402 <span class="keywordflow">if</span> (high > low) { |
|---|
| 326 | <a name="l00403"></a>00403 T a = data[low]; |
|---|
| 327 | <a name="l00404"></a>00404 <span class="keywordtype">int</span> plow = low; |
|---|
| 328 | <a name="l00405"></a>00405 <span class="keywordtype">int</span> phigh = high; |
|---|
| 329 | <a name="l00406"></a>00406 T test = data[phigh]; |
|---|
| 330 | <a name="l00407"></a>00407 <span class="keywordflow">while</span> (plow < phigh) { |
|---|
| 331 | <a name="l00408"></a>00408 <span class="keywordflow">if</span> (test < a) { |
|---|
| 332 | <a name="l00409"></a>00409 data[plow] = test; |
|---|
| 333 | <a name="l00410"></a>00410 plow++; |
|---|
| 334 | <a name="l00411"></a>00411 test = data[plow]; |
|---|
| 335 | <a name="l00412"></a>00412 } |
|---|
| 336 | <a name="l00413"></a>00413 <span class="keywordflow">else</span> { |
|---|
| 337 | <a name="l00414"></a>00414 data[phigh] = test; |
|---|
| 338 | <a name="l00415"></a>00415 phigh--; |
|---|
| 339 | <a name="l00416"></a>00416 test = data[phigh]; |
|---|
| 340 | <a name="l00417"></a>00417 } |
|---|
| 341 | <a name="l00418"></a>00418 } |
|---|
| 342 | <a name="l00419"></a>00419 data[plow] = a; |
|---|
| 343 | <a name="l00420"></a>00420 QuickSort(low, plow - 1, data); |
|---|
| 344 | <a name="l00421"></a>00421 QuickSort(plow + 1, high, data); |
|---|
| 345 | <a name="l00422"></a>00422 } |
|---|
| 346 | <a name="l00423"></a>00423 } |
|---|
| 347 | <a name="l00424"></a>00424 |
|---|
| 348 | <a name="l00425"></a>00425 <span class="keyword">template</span><<span class="keyword">class</span> T> |
|---|
| 349 | <a name="l00426"></a>00426 <span class="keywordtype">void</span> Sort<T>::QuickSort_Index(<span class="keywordtype">int</span> low, <span class="keywordtype">int</span> high, <span class="keywordtype">int</span> indexlist[], |
|---|
| 350 | <a name="l00427"></a>00427 <span class="keyword">const</span> T data[]) |
|---|
| 351 | <a name="l00428"></a>00428 { |
|---|
| 352 | <a name="l00429"></a>00429 <span class="keywordflow">if</span> (high > low) { |
|---|
| 353 | <a name="l00430"></a>00430 <span class="keywordtype">int</span> aindex = indexlist[low]; |
|---|
| 354 | <a name="l00431"></a>00431 T a = data[aindex]; |
|---|
| 355 | <a name="l00432"></a>00432 <span class="keywordtype">int</span> plow = low; |
|---|
| 356 | <a name="l00433"></a>00433 <span class="keywordtype">int</span> phigh = high; |
|---|
| 357 | <a name="l00434"></a>00434 <span class="keywordtype">int</span> testindex = indexlist[phigh]; |
|---|
| 358 | <a name="l00435"></a>00435 T test = data[testindex]; |
|---|
| 359 | <a name="l00436"></a>00436 <span class="keywordflow">while</span> (plow < phigh) { |
|---|
| 360 | <a name="l00437"></a>00437 <span class="keywordflow">if</span> (test < a) { |
|---|
| 361 | <a name="l00438"></a>00438 indexlist[plow] = testindex; |
|---|
| 362 | <a name="l00439"></a>00439 plow++; |
|---|
| 363 | <a name="l00440"></a>00440 testindex = indexlist[plow]; |
|---|
| 364 | <a name="l00441"></a>00441 test = data[testindex]; |
|---|
| 365 | <a name="l00442"></a>00442 } |
|---|
| 366 | <a name="l00443"></a>00443 <span class="keywordflow">else</span> { |
|---|
| 367 | <a name="l00444"></a>00444 indexlist[phigh] = testindex; |
|---|
| 368 | <a name="l00445"></a>00445 phigh--; |
|---|
| 369 | <a name="l00446"></a>00446 testindex = indexlist[phigh]; |
|---|
| 370 | <a name="l00447"></a>00447 test = data[testindex]; |
|---|
| 371 | <a name="l00448"></a>00448 } |
|---|
| 372 | <a name="l00449"></a>00449 } |
|---|
| 373 | <a name="l00450"></a>00450 indexlist[plow] = aindex; |
|---|
| 374 | <a name="l00451"></a>00451 QuickSort_Index(low, plow - 1, indexlist, data); |
|---|
| 375 | <a name="l00452"></a>00452 QuickSort_Index(plow + 1, high, indexlist, data); |
|---|
| 376 | <a name="l00453"></a>00453 } |
|---|
| 377 | <a name="l00454"></a>00454 } |
|---|
| 378 | <a name="l00455"></a>00455 |
|---|
| 379 | <a name="l00456"></a>00456 <span class="keyword">template</span><<span class="keyword">class</span> T> |
|---|
| 380 | <a name="l00457"></a>00457 <span class="keywordtype">void</span> Sort<T>::HeapSort(<span class="keywordtype">int</span> low, <span class="keywordtype">int</span> high, T data[]) |
|---|
| 381 | <a name="l00458"></a>00458 { |
|---|
| 382 | <a name="l00459"></a>00459 <span class="keywordtype">int</span> <a class="code" href="group__matrix__functions.html#g3c1a2b0972c6a8e1215eb3f76d7c7512" title="Length of vector.">size</a> = (high + 1) - low; |
|---|
| 383 | <a name="l00460"></a>00460 <span class="keywordtype">int</span> i = size / 2; |
|---|
| 384 | <a name="l00461"></a>00461 T temp; |
|---|
| 385 | <a name="l00462"></a>00462 <span class="keywordflow">while</span> (1) { |
|---|
| 386 | <a name="l00463"></a>00463 <span class="keywordflow">if</span> (i > 0) |
|---|
| 387 | <a name="l00464"></a>00464 temp = data[--i + low]; |
|---|
| 388 | <a name="l00465"></a>00465 <span class="keywordflow">else</span> { |
|---|
| 389 | <a name="l00466"></a>00466 <span class="keywordflow">if</span> (size-- == 0) |
|---|
| 390 | <a name="l00467"></a>00467 <span class="keywordflow">break</span>; |
|---|
| 391 | <a name="l00468"></a>00468 temp = data[size + low]; |
|---|
| 392 | <a name="l00469"></a>00469 data[size + low] = data[low]; |
|---|
| 393 | <a name="l00470"></a>00470 } |
|---|
| 394 | <a name="l00471"></a>00471 |
|---|
| 395 | <a name="l00472"></a>00472 <span class="keywordtype">int</span> parent = i; |
|---|
| 396 | <a name="l00473"></a>00473 <span class="keywordtype">int</span> child = i * 2 + 1; |
|---|
| 397 | <a name="l00474"></a>00474 |
|---|
| 398 | <a name="l00475"></a>00475 <span class="keywordflow">while</span> (child < size) { |
|---|
| 399 | <a name="l00476"></a>00476 <span class="keywordflow">if</span> (child + 1 < size && data[child + 1 + low] > data[child + low]) |
|---|
| 400 | <a name="l00477"></a>00477 child++; |
|---|
| 401 | <a name="l00478"></a>00478 <span class="keywordflow">if</span> (data[child + low] > temp) { |
|---|
| 402 | <a name="l00479"></a>00479 data[parent + low] = data[child + low]; |
|---|
| 403 | <a name="l00480"></a>00480 parent = child; |
|---|
| 404 | <a name="l00481"></a>00481 child = parent * 2 + 1; |
|---|
| 405 | <a name="l00482"></a>00482 } |
|---|
| 406 | <a name="l00483"></a>00483 <span class="keywordflow">else</span> |
|---|
| 407 | <a name="l00484"></a>00484 <span class="keywordflow">break</span>; |
|---|
| 408 | <a name="l00485"></a>00485 } |
|---|
| 409 | <a name="l00486"></a>00486 data[parent + low] = temp; |
|---|
| 410 | <a name="l00487"></a>00487 } |
|---|
| 411 | <a name="l00488"></a>00488 } |
|---|
| 412 | <a name="l00489"></a>00489 |
|---|
| 413 | <a name="l00490"></a>00490 <span class="keyword">template</span><<span class="keyword">class</span> T> |
|---|
| 414 | <a name="l00491"></a>00491 <span class="keywordtype">void</span> Sort<T>::HeapSort_Index(<span class="keywordtype">int</span> low, <span class="keywordtype">int</span> high, <span class="keywordtype">int</span> indexlist[], |
|---|
| 415 | <a name="l00492"></a>00492 <span class="keyword">const</span> T data[]) |
|---|
| 416 | <a name="l00493"></a>00493 { |
|---|
| 417 | <a name="l00494"></a>00494 <span class="keywordtype">int</span> size = (high + 1) - low; |
|---|
| 418 | <a name="l00495"></a>00495 <span class="keywordtype">int</span> i = size / 2; |
|---|
| 419 | <a name="l00496"></a>00496 |
|---|
| 420 | <a name="l00497"></a>00497 <span class="keywordflow">while</span> (1) { |
|---|
| 421 | <a name="l00498"></a>00498 T tempValue; |
|---|
| 422 | <a name="l00499"></a>00499 <span class="keywordtype">int</span> tempIndex; |
|---|
| 423 | <a name="l00500"></a>00500 <span class="keywordflow">if</span> (i > 0) { |
|---|
| 424 | <a name="l00501"></a>00501 i--; |
|---|
| 425 | <a name="l00502"></a>00502 tempValue = data[indexlist[i + low]]; |
|---|
| 426 | <a name="l00503"></a>00503 tempIndex = indexlist[i + low]; |
|---|
| 427 | <a name="l00504"></a>00504 } |
|---|
| 428 | <a name="l00505"></a>00505 <span class="keywordflow">else</span> { |
|---|
| 429 | <a name="l00506"></a>00506 <span class="keywordflow">if</span> (size-- == 0) |
|---|
| 430 | <a name="l00507"></a>00507 <span class="keywordflow">break</span>; |
|---|
| 431 | <a name="l00508"></a>00508 tempValue = data[indexlist[size + low]]; |
|---|
| 432 | <a name="l00509"></a>00509 tempIndex = indexlist[size + low]; |
|---|
| 433 | <a name="l00510"></a>00510 indexlist[size+low] = indexlist[low]; |
|---|
| 434 | <a name="l00511"></a>00511 } |
|---|
| 435 | <a name="l00512"></a>00512 |
|---|
| 436 | <a name="l00513"></a>00513 <span class="keywordtype">int</span> parent = i; |
|---|
| 437 | <a name="l00514"></a>00514 <span class="keywordtype">int</span> child = i * 2 + 1; |
|---|
| 438 | <a name="l00515"></a>00515 |
|---|
| 439 | <a name="l00516"></a>00516 <span class="keywordflow">while</span> (child < size) { |
|---|
| 440 | <a name="l00517"></a>00517 <span class="keywordflow">if</span> ((child + 1 < size) |
|---|
| 441 | <a name="l00518"></a>00518 && data[indexlist[child + 1 + low]] > data[indexlist[child + low]]) |
|---|
| 442 | <a name="l00519"></a>00519 child++; |
|---|
| 443 | <a name="l00520"></a>00520 <span class="keywordflow">if</span> (data[indexlist[child + low]] > tempValue) { |
|---|
| 444 | <a name="l00521"></a>00521 indexlist[parent + low] = indexlist[child + low]; |
|---|
| 445 | <a name="l00522"></a>00522 parent = child; |
|---|
| 446 | <a name="l00523"></a>00523 child = parent * 2 + 1; |
|---|
| 447 | <a name="l00524"></a>00524 } |
|---|
| 448 | <a name="l00525"></a>00525 <span class="keywordflow">else</span> |
|---|
| 449 | <a name="l00526"></a>00526 <span class="keywordflow">break</span>; |
|---|
| 450 | <a name="l00527"></a>00527 } |
|---|
| 451 | <a name="l00528"></a>00528 indexlist[parent + low] = tempIndex; |
|---|
| 452 | <a name="l00529"></a>00529 } |
|---|
| 453 | <a name="l00530"></a>00530 } |
|---|
| 454 | <a name="l00531"></a>00531 |
|---|
| 455 | <a name="l00532"></a>00532 <span class="keyword">template</span><<span class="keyword">class</span> T> |
|---|
| 456 | <a name="l00533"></a>00533 <span class="keywordtype">void</span> Sort<T>::InsertSort(<span class="keywordtype">int</span> low, <span class="keywordtype">int</span> high, T data[]) |
|---|
| 457 | <a name="l00534"></a>00534 { |
|---|
| 458 | <a name="l00535"></a>00535 <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = low + 1; i <= high; i++) { |
|---|
| 459 | <a name="l00536"></a>00536 T value = data[i]; |
|---|
| 460 | <a name="l00537"></a>00537 <span class="keywordtype">int</span> j; |
|---|
| 461 | <a name="l00538"></a>00538 <span class="keywordflow">for</span> (j = i - 1; j >= low && data[j] > value; j--) { |
|---|
| 462 | <a name="l00539"></a>00539 data[j + 1] = data[j]; |
|---|
| 463 | <a name="l00540"></a>00540 } |
|---|
| 464 | <a name="l00541"></a>00541 data[j + 1] = value; |
|---|
| 465 | <a name="l00542"></a>00542 } |
|---|
| 466 | <a name="l00543"></a>00543 } |
|---|
| 467 | <a name="l00544"></a>00544 |
|---|
| 468 | <a name="l00545"></a>00545 <span class="keyword">template</span><<span class="keyword">class</span> T> |
|---|
| 469 | <a name="l00546"></a>00546 <span class="keywordtype">void</span> Sort<T>::InsertSort_Index(<span class="keywordtype">int</span> low, <span class="keywordtype">int</span> high, <span class="keywordtype">int</span> indexlist[], |
|---|
| 470 | <a name="l00547"></a>00547 <span class="keyword">const</span> T data[]) |
|---|
| 471 | <a name="l00548"></a>00548 { |
|---|
| 472 | <a name="l00549"></a>00549 <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = low + 1; i <= high; i++) { |
|---|
| 473 | <a name="l00550"></a>00550 T value = data[indexlist[i]]; |
|---|
| 474 | <a name="l00551"></a>00551 <span class="keywordtype">int</span> tempIndex = indexlist[i]; |
|---|
| 475 | <a name="l00552"></a>00552 <span class="keywordtype">int</span> j; |
|---|
| 476 | <a name="l00553"></a>00553 <span class="keywordflow">for</span> (j = i - 1; j >= low && data[indexlist[j]] > value; j--) { |
|---|
| 477 | <a name="l00554"></a>00554 indexlist[j + 1] = indexlist[j]; |
|---|
| 478 | <a name="l00555"></a>00555 } |
|---|
| 479 | <a name="l00556"></a>00556 indexlist[j + 1] = tempIndex; |
|---|
| 480 | <a name="l00557"></a>00557 } |
|---|
| 481 | <a name="l00558"></a>00558 } |
|---|
| 482 | <a name="l00559"></a>00559 |
|---|
| 483 | <a name="l00560"></a>00560 |
|---|
| 484 | <a name="l00561"></a>00561 } <span class="comment">// namespace itpp</span> |
|---|
| 485 | <a name="l00562"></a>00562 |
|---|
| 486 | <a name="l00563"></a>00563 <span class="preprocessor">#endif // #ifndef SORT_H</span> |
|---|
| 487 | </pre></div></div> |
|---|
| 488 | <hr size="1"><address style="text-align: right;"><small>Generated on Tue Jun 2 10:02:13 2009 for mixpp by |
|---|
| 489 | <a href="http://www.doxygen.org/index.html"> |
|---|
| 490 | <img src="doxygen.png" alt="doxygen" align="middle" border="0"></a> 1.5.8 </small></address> |
|---|
| 491 | </body> |
|---|
| 492 | </html> |
|---|
