rheolef  6.5
msg_sort_with_permutation.h
Go to the documentation of this file.
1 #ifndef _RHEOLEF_MSG_SORT_WITH_PERMUTATION_H
2 #define _RHEOLEF_MSG_SORT_WITH_PERMUTATION_H
3 /*
4  sort_with_permutation - Computes the permutation of values that gives
5  a sorted sequence.
6 
7  Input Parameters:
8  n - number of values to sort
9  i - values to sort
10  vdx - permutation array. Must be initialized to 0:n-1 on input.
11 
12  Notes:
13  i is unchanged on output.
14  inspirated from petsc-2.0.22/sortip.c
15 */
16 
17 #include "rheolef/compiler.h"
18 namespace rheolef {
19 
20 #ifdef TODO
21 template<class Size, class SizeRandomIterator, class T>
22 void
23 qsort_with_permutation(
24  T *v,
25  SizeRandomIterator vdx,
26  Size right)
27 {
28  if (right <= 1) {
29  if (right == 1) {
30  if (v[vdx[0]] > v[vdx[1]]) {
31  std::swap (vdx[0], vdx[1]);
32  }
33  }
34  return;
35  }
36  std::swap (vdx[0], vdx[right/2]);
37  Size vl = v[vdx[0]];
38  Size last = 0;
39  for (Size i = 1; i <= right; i++) {
40  if (v[vdx[i]] < vl ) {
41  last++;
42  std::swap (vdx[last], vdx[i]);
43  }
44  }
45  std::swap (vdx[0], vdx[last]);
46  qsort_with_permutation (v, vdx, last-1);
47  qsort_with_permutation (v, vdx+last+1, right-(last+1));
48 }
49 #endif // TODO
50 template<class Size, class SizeRandomIterator, class T>
51 void
53  Size n,
54  T *v,
55  SizeRandomIterator vdx)
56 {
57 #ifdef TODO
58  const size_t n_qsort_min = 8; // buggy qsort
59  if (n >= n_qsort_min) {
60  qsort_with_permutation(v,vdx,n-1);
61  return;
62  }
63 #endif // TODO
64  for (Size k = 0; k < n; k++) {
65  Size vk = v [vdx [k]];
66  for (Size j = k+1; j < n; j++) {
67  if (vk > v [vdx [j]]) {
68  std::swap (vdx[k], vdx[j]);
69  vk = v [vdx [k]];
70  }
71  }
72  }
73 }
74 
75 } // namespace rheolef
76 #endif // _RHEOLEF_MSG_SORT_WITH_PERMUTATION_H
77