rheolef  6.6
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  v - values to sort. Unchanged
9  p - permutation array. Must be initialized to 0:n-1 on input.
10  n - number of values to sort
11 
12  Notes:
13  inspirated from petsc-2.0.22/sortip.c
14  with a bug fix in quicksort as in http://iulib.googlecode.com/hg/colib/quicksort.h
15 */
16 
17 #include "rheolef/compiler.h"
18 namespace rheolef {
19 
20 template<class RandomIterator, class SizeRandomIterator, class Size>
21 void
23  RandomIterator v,
24  SizeRandomIterator p,
25  Size start,
26  Size end)
27 {
28  if (start + 1 >= end) return;
29  typedef typename std::iterator_traits<RandomIterator>::value_type T;
30  const T& pivot = v[p[(start+end-1)/2]];
31  Size lo = start, hi = end;
32  for(;;) {
33  while (lo < hi && v[p[lo]] < pivot) lo++;
34  while (lo < hi && v[p[hi-1]] >= pivot) hi--;
35  if (lo == hi || lo+1 == hi) break;
36  std::swap (p[lo], p[hi-1]);
37  lo++; hi--;
38  }
39  Size split1 = lo;
40  hi = end;
41  for(;;) {
42  while (lo < hi && v[p[lo]] == pivot) lo++;
43  while (lo < hi && v[p[hi-1]] > pivot) hi--;
44  if (lo == hi || lo+1 == hi) break;
45  std::swap (p[lo], p[hi-1]);
46  lo++; hi--;
47  }
48  Size split2 = lo;
49  quick_sort_with_permutation (v, p, start, split1);
50  quick_sort_with_permutation (v, p, split2, end);
51 }
52 template<class RandomIterator, class SizeRandomIterator, class Size>
53 void
55  RandomIterator v,
56  SizeRandomIterator p,
57  Size n)
58 {
59  for (Size k = 0; k < n; k++) {
60  Size vk = v [p [k]];
61  for (Size j = k+1; j < n; j++) {
62  if (vk > v [p [j]]) {
63  std::swap (p[k], p[j]);
64  vk = v [p [k]];
65  }
66  }
67  }
68 }
69 template<class RandomIterator, class SizeRandomIterator, class Size>
70 void
72  RandomIterator v,
73  SizeRandomIterator p,
74  Size n)
75 {
76  const Size n_qsort_min = 8;
77  if (n >= n_qsort_min) {
78  quick_sort_with_permutation (v, p, Size(0), n);
79  } else {
81  }
82 }
83 
84 } // namespace rheolef
85 #endif // _RHEOLEF_MSG_SORT_WITH_PERMUTATION_H
void quick_sort_with_permutation(RandomIterator v, SizeRandomIterator p, Size start, Size end)
void bubble_sort_with_permutation(RandomIterator v, SizeRandomIterator p, Size n)
irheostream, orheostream - large data streams
Definition: compiler.h:7
void sort_with_permutation(RandomIterator v, SizeRandomIterator p, Size n)