|
/**
* FuzzySort.cpp
* @Author Tu Yongce
* @Created 2008-2-26
* @Modified 2008-2-26
* @Version 0.1
*/
// 《算法导论》（第二版）P164，思考题7-6：对区间的模糊排序
/**
* 考虑这样的一种排序问题，即无法准确地知道待排序的各个数字到底是多少。对于其中的每个数字，
* 我们只知道它落在实轴上的某个区间内。亦即，给定的是n个形如[a(i), b(i)]的闭区间（这里小括
* 后起下标的作用，后同），其中a(i) <= b(i)。算法的目标是对这些区间进行模糊排序
* （fuzzy-sort），亦即，产生各区间的一个排列，使得存在一个c(j)属于
* 区间[a(i(j)), b(i(j))]，满足c(1) <= c(2) <= c(3) <= ... <= c(n)。
* a) 为n个区间的模糊排序设计一个算法。你的算法应该具有算法的一般结构，它可以快速排序左部
* 端点（即各a(i)），也要能充分利用重叠区间来改善运行时间。（随着各区间重叠得越来越多，
* 对各区间进行模糊排序的问题会变得越来越容易。你的算法应能充分利用这种重叠。）
* b) 证明：在一般情况下，你的算法的期望运行时间为Θ(nlgn)，但当所有的区间都重叠时，期望的
* 运行时间为Θ(n)（亦即，当存在一个值x，使得对所有的i，都有x∈[a(i), b(i)]）。你的算法
* 不应显式地检查这种情况，而是应随着重叠量的增加，性能自然地有所改善。
*/
#include <iostream>
#include <utility>
using namespace std;
typedef pair<int, int> pair_int;
template <typename T>
pair_int fuzzy_partition(pair<T, T> *arr, int p, int r)
{
// 类似快速排序的划分，arr[i..k-1]范围内的区间元素有共同的重叠区间，该重叠区间作为主元
// 时间复杂度为O(n)
int i = p, k = p + 1, j = r;
pair<T, T> x = arr[p]; // 主元区间
while (k <= j) {
if (arr[k].second < x.first) {
// 比主元区间小
swap(arr[k], arr[i]);
++i;
++k;
} else if (arr[k].first > x.second) {
// 比主元区间大
swap(arr[k], arr[j]);
--j;
} else {
// 与主元区间有重叠，则更新主元为重叠区间（交集）
x.first = max(x.first, arr[k].first);
x.second = min(x.second, arr[k].second);
++k;
}
}
return pair_int(i, j);
}
template <typename T>
void fuzzy_sort(pair<T, T> *arr, int p, int r)
{
// 对区间的模糊排序，类似于快速排序算法
if (p < r) {
pair_int q = fuzzy_partition(arr, p, r);
fuzzy_sort(arr, p, q.first - 1);
fuzzy_sort(arr, q.second + 1, r);
}
}
void fuzzy_sort_test()
{
pair_int arr1[] = {pair_int(7, 9), pair_int(2, 5)};
pair_int arr2[] = {pair_int(4, 8), pair_int(2, 5)};
pair_int arr3[] = {pair_int(5, 9), pair_int(2, 7), pair_int(4, 8), pair_int(3, 6)};
pair_int arr4[] = {pair_int(7, 9), pair_int(9, 10), pair_int(2, 5), pair_int(4, 8), pair_int(1, 10)};
pair_int arr5[] = {pair_int(1, 2), pair_int(2, 3), pair_int(3, 4), pair_int(4, 5), pair_int(5, 6)};
pair_int *arr[] = {arr1, arr2, arr3, arr4, arr5};
const size_t NUM2[] = {
sizeof(arr1) / sizeof(arr1[0]),
sizeof(arr2) / sizeof(arr2[0]),
sizeof(arr3) / sizeof(arr3[0]),
sizeof(arr4) / sizeof(arr4[0]),
sizeof(arr5) / sizeof(arr5[0]),
};
const size_t NUM = sizeof(arr) / sizeof(arr[0]);
for (size_t i = 0; i < NUM; ++i) {
cout << "初始区间序列：" << endl;
for (size_t j = 0; j < NUM2[i]; ++j)
cout << "(" << arr[i][j].first << "," << arr[i][j].second << ") ";
cout << endl;
fuzzy_sort(arr[i], 0, NUM2[i] - 1);
cout << "模糊排序后的区间序列：" << endl;
for (size_t j = 0; j < NUM2[i]; ++j)
cout << "(" << arr[i][j].first << "," << arr[i][j].second << ") ";
cout << "\n" << endl;
}
}
|
