| 182 | typename compare |
| 183 | > |
| 184 | inline unsigned long qsort_partition ( |
| 185 | T& array, |
| 186 | Y& pivot, |
| 187 | const unsigned long left, |
| 188 | const unsigned long right, |
| 189 | const compare& comp |
| 190 | ) |
| 191 | /*! |
| 192 | requires |
| 193 | - &pivot == &array[right] |
| 194 | - T implements operator[] |
| 195 | - the items in array must be comparable by comp |
| 196 | - left and right are within the bounts of the array |
| 197 | - left < right |
| 198 | ensures |
| 199 | - returns a number called partition_element such that: |
| 200 | - left <= partition_element <= right |
| 201 | - all elements in #array < #array[partition_element] have |
| 202 | indices >= left and < partition_element |
| 203 | - all elements in #array > #array[partition_element] have |
| 204 | indices > partition_element and <= right |
| 205 | !*/ |
| 206 | { |
| 207 | DLIB_ASSERT (&pivot == &array[right] && left < right, |
| 208 | "\tunsigned long qsort_partition()" |
| 209 | << "\n\t&pivot: " << &pivot |
| 210 | << "\n\t&array[right]: " << &array[right] |
| 211 | << "\n\tleft: " << left |
| 212 | << "\n\tright: " << right ); |
| 213 | |
| 214 | exchange(array[(right-left)/2 +left],pivot); |
| 215 | |
| 216 | unsigned long i = left; |
| 217 | for (unsigned long j = left; j < right; ++j) |
| 218 | { |
| 219 | if (comp(array[j] , pivot)) |
| 220 | { |
| 221 | swap(array[i],array[j]); |
| 222 | ++i; |
| 223 | } |
| 224 | } |
| 225 | exchange(array[i],pivot); |
| 226 | |
| 227 | return i; |
| 228 | } |
| 229 | |
| 230 | // ---------------------------------------------------------------------------------------- |
| 231 |
no test coverage detected