w****x
发帖数: 2483 | 1 算法导论上的一道, 觉得蛮好的...
/*
Consider a sorting problem in which the numbers are not known exactly.
Instead, for each number, we know an interval on the real line to which it
belongs.
That is, we are given n closed intervals of the form [ai, bi], where ai ≤
bi.
The goal is to fuzzy-sort these intervals, i.e., produce a permutation 〈i1,
i2,..., in〉
of the intervals such that there exist , satisfying c1 ≤ c2 ≤ ··· ≤ cn.
Design an algorithm for fuzzy-sorting n intervals.
Your algorithm should have the general structure of an algorithm
that quicksorts the left endpoints (the ai 's), but it should take advantage
of overlapping intervals to improve the running time.
(As the intervals overlap more and more, the problem of
fuzzy-sorting the intervals gets easier and easier.
Your algorithm should take advantage of such overlapping, to the extent that
it exists.)
*/
struct SEGMENT
{
int a;
int b;
};
void partition(SEGMENT a[], int beg, int end, int& x, int& y)
{
if (beg >= end) return;
int i = beg;
for (int j = beg; j < end; j++)
{
if (a[j].a <= a[end].a)
swap(a[i++], a[j]);
}
swap(a[i], a[end]);
int k = beg;
for (int j = beg; j < i; j++)
{
if (a[j].b < a[i].b)
swap(a[k++], a[j]);
}
x = k-1;
y = i+1;
}
void seg_sort(SEGMENT a[], int b, int e)
{
if (NULL == a || b >= e)
return;
int x,y;
partition(a, b, e, x, y);
seg_sort(a, b, x);
seg_sort(a, y, e);
}
void segmentSort(SEGMENT a[], int n)
{
if (NULL == a || n <= 0)
return;
seg_sort(a, 0, n-1);
} | s***u
发帖数: 101 | 2 请教一下， 第一部分中
int i = beg;
for (int j = beg; j < end; j++)
{
if (a[j].a <= a[end].a)
swap(a[i++], a[j]);
}
swap(a[i], a[end]);
这样不能够把和 end overlap 的interval 全部放在end之前吧
是不是要写成:
if (a[j].a <= a[end].b) ？ | l*********8
发帖数: 4642 | 3 怎样定义intervals 之间的大小关系？
i1,
cn.
【在 w****x 的大作中提到】
: 算法导论上的一道, 觉得蛮好的...
: /*
: Consider a sorting problem in which the numbers are not known exactly.
: Instead, for each number, we know an interval on the real line to which it
: belongs.
: That is, we are given n closed intervals of the form [ai, bi], where ai ≤
: bi.
: The goal is to fuzzy-sort these intervals, i.e., produce a permutation 〈i1,
: i2,..., in〉
: of the intervals such that there exist , satisfying c1 ≤ c2 ≤ ··· ≤ cn.
| w****x
发帖数: 2483 | 4
大概就是先把起点小于pivot segment的intervals排出在左部, 然后再在那部分
intervals里面排出end point大于pivot interval起点的线段, 这部分线段有共同的
overlap就当已经排好序了
【在 s***u 的大作中提到】
: 请教一下， 第一部分中
: int i = beg;
: for (int j = beg; j < end; j++)
: {
: if (a[j].a <= a[end].a)
: swap(a[i++], a[j]);
: }
: swap(a[i], a[end]);
: 这样不能够把和 end overlap 的interval 全部放在end之前吧
: 是不是要写成:
|
|
