1#ifndef _RHEOLEF_MSG_SORT_WITH_PERMUTATION_H
2#define _RHEOLEF_MSG_SORT_WITH_PERMUTATION_H
37#include "rheolef/compiler.h"
40template<
class RandomIterator,
class SizeRandomIterator,
class Size>
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;
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]);
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]);
72template<
class RandomIterator,
class SizeRandomIterator,
class Size>
79 for (Size k = 0; k < n; k++) {
81 for (Size j = k+1; j < n; j++) {
83 std::swap (
p[k],
p[j]);
89template<
class RandomIterator,
class SizeRandomIterator,
class Size>
96 const Size n_qsort_min = 8;
97 if (n >= n_qsort_min) {
This file is part of Rheolef.
void sort_with_permutation(RandomIterator v, SizeRandomIterator p, Size n)
void quick_sort_with_permutation(RandomIterator v, SizeRandomIterator p, Size start, Size end)
void bubble_sort_with_permutation(RandomIterator v, SizeRandomIterator p, Size n)