Rheolef  7.1
an efficient C++ finite element environment
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
23 /*
24  sort_with_permutation - Computes the permutation of values that gives
25  a sorted sequence.
26 
27  Input Parameters:
28  v - values to sort. Unchanged
29  p - permutation array. Must be initialized to 0:n-1 on input.
30  n - number of values to sort
31 
32  Notes:
33  inspirated from petsc-2.0.22/sortip.c
34  with a bug fix in quicksort as in http://iulib.googlecode.com/hg/colib/quicksort.h
35 */
36 
37 #include "rheolef/compiler.h"
38 namespace rheolef {
39 
40 template<class RandomIterator, class SizeRandomIterator, class Size>
41 void
43  RandomIterator v,
44  SizeRandomIterator p,
45  Size start,
46  Size end)
47 {
48  if (start + 1 >= end) return;
49  typedef typename std::iterator_traits<RandomIterator>::value_type T;
50  const T& pivot = v[p[(start+end-1)/2]];
51  Size lo = start, hi = end;
52  for(;;) {
53  while (lo < hi && v[p[lo]] < pivot) lo++;
54  while (lo < hi && v[p[hi-1]] >= pivot) hi--;
55  if (lo == hi || lo+1 == hi) break;
56  std::swap (p[lo], p[hi-1]);
57  lo++; hi--;
58  }
59  Size split1 = lo;
60  hi = end;
61  for(;;) {
62  while (lo < hi && v[p[lo]] == pivot) lo++;
63  while (lo < hi && v[p[hi-1]] > pivot) hi--;
64  if (lo == hi || lo+1 == hi) break;
65  std::swap (p[lo], p[hi-1]);
66  lo++; hi--;
67  }
68  Size split2 = lo;
69  quick_sort_with_permutation (v, p, start, split1);
70  quick_sort_with_permutation (v, p, split2, end);
71 }
72 template<class RandomIterator, class SizeRandomIterator, class Size>
73 void
75  RandomIterator v,
76  SizeRandomIterator p,
77  Size n)
78 {
79  for (Size k = 0; k < n; k++) {
80  Size vk = v [p [k]];
81  for (Size j = k+1; j < n; j++) {
82  if (vk > v [p [j]]) {
83  std::swap (p[k], p[j]);
84  vk = v [p [k]];
85  }
86  }
87  }
88 }
89 template<class RandomIterator, class SizeRandomIterator, class Size>
90 void
92  RandomIterator v,
93  SizeRandomIterator p,
94  Size n)
95 {
96  const Size n_qsort_min = 8;
97  if (n >= n_qsort_min) {
98  quick_sort_with_permutation (v, p, Size(0), n);
99  } else {
101  }
102 }
103 
104 } // namespace rheolef
105 #endif // _RHEOLEF_MSG_SORT_WITH_PERMUTATION_H
Expr1::float_type T
Definition: field_expr.h:261
This file is part of Rheolef.
void quick_sort_with_permutation(RandomIterator v, SizeRandomIterator p, Size start, Size end)
void bubble_sort_with_permutation(RandomIterator v, SizeRandomIterator p, Size n)
void sort_with_permutation(RandomIterator v, SizeRandomIterator p, Size n)
Definition: sphere.icc:25