v******a
发帖数: 54 | 1 Given an array of n elements and an integer k where k
Elements {a[0].....a[k] and a[k+1].....a[n] are already sorted. Give an
algorithm to sort in O(n) time and O(1) space.
怎么做这个？ |
f*********5
发帖数: 576 | 2 有人告诉过你这题有解？
如果有的话，merge sort就不需要额外空间了吧
【在 v******a 的大作中提到】
: Given an array of n elements and an integer k where k: Elements {a[0].....a[k] and a[k+1].....a[n] are already sorted. Give an
: algorithm to sort in O(n) time and O(1) space.
: 怎么做这个？
|
b********e
发帖数: 53 | 3 #ifndef MERGE_SORTED_ARRAY_H
#define MERGE_SORTED_ARRAY_H
#include
using namespace std;
/* problem statement:
* Given an array of n elements and an integer k where k
* Elements {a[0].....a[k] and a[k+1].....a[n] are already sorted. Give an
* algorithm to sort in O(n) time and O(1) space.
*/
class MergeSortedArray
{
public:
// [begin, end), inflection is the beginning of the second sorted
beginning
void sort(int * begin, int * end, int * inflection)
{
if (begin > |
f*********5
发帖数: 576 | 4 BTW,
sort->sort->sort...
it will not be O(1) space.
each time,you may shorten your array,i assume that by average
you need log2n times to finish
it may be considered as O(log2n) extra space.(for call stack)
an
【在 b********e 的大作中提到】
: #ifndef MERGE_SORTED_ARRAY_H
: #define MERGE_SORTED_ARRAY_H
: #include
: using namespace std;
: /* problem statement:
: * Given an array of n elements and an integer k where k: * Elements {a[0].....a[k] and a[k+1].....a[n] are already sorted. Give an
: * algorithm to sort in O(n) time and O(1) space.
: */
: class MergeSortedArray
|
i*****e
发帖数: 113 | 5 批判一下我的程序
假设数组是[0..k-1], [k..n-1]，这样看起来舒服一些
第一个是递归的形式，尾递归所以空间没问题，第二个改写成了循环
考虑最差情况，k=1，这时候时间复杂度是O(n)
using namespace std;
void sort_recurse(int a[], int n, int k)
{
int ll = k, lr = n - k;
if (ll == 0 || lr == 0) {
return;
}
if (ll == lr) {
for (int i = 0; i < ll; ++i)
swap(a[i], a[k+i]);
return;
} else if (ll < lr) {
for (int i = 0; i < ll; ++i)
swap(a[i], a[n-k+i]);
return sort_recurse(a, n - ll, k);
} else { |
f*********5
发帖数: 576 | 6 please check whether your code work well with below array
1,6,7,2,3,4,5,8
BTW,why 尾递归所以空间没问题?
recursion will use extra space
【在 i*****e 的大作中提到】
: 批判一下我的程序
: 假设数组是[0..k-1], [k..n-1]，这样看起来舒服一些
: 第一个是递归的形式，尾递归所以空间没问题，第二个改写成了循环
: 考虑最差情况，k=1，这时候时间复杂度是O(n)
: using namespace std;
: void sort_recurse(int a[], int n, int k)
: {
: int ll = k, lr = n - k;
: if (ll == 0 || lr == 0) {
: return;
|
d**e
发帖数: 6098 | 7 idesire的程序我还没看，但前面betterlate的好像是对的，不过他的while那部分我暂
时还没想得清楚，而他用的是tail recursion，所以空间方面没问题。
【在 f*********5 的大作中提到】
: please check whether your code work well with below array
: 1,6,7,2,3,4,5,8
: BTW,why 尾递归所以空间没问题?
: recursion will use extra space
|
I**A
发帖数: 2345 | 8 你能不能说一下betterlate的思路
为什么(*p2 < *p3）就要swap p2 and p1?
【在 d**e 的大作中提到】
: idesire的程序我还没看，但前面betterlate的好像是对的，不过他的while那部分我暂
: 时还没想得清楚，而他用的是tail recursion，所以空间方面没问题。
|
d**e
发帖数: 6098 | 9 这个就是我不明白的地方。
之前试了几个例子也是对的，不过我现在找到例子，他的程序错了。
比如3,4,5,6,1,2,7，最后的结果只是1,2,3,5,6,4,7
开始他可能是手误，if没加上判断 begin==inflection，否则如果array本来就是排好
的，比如1,2, 3, 4, 5,6,7，那么会进入死循环。不过这个问题不是很大。
我不是很明白while loop里面的，也就是你问的这个问题。最好betterlate可以说明一
下。
【在 I**A 的大作中提到】
: 你能不能说一下betterlate的思路
: 为什么(*p2 < *p3）就要swap p2 and p1?
|
d**e
发帖数: 6098 | 10 赞成你的说法，应该是无解。
呼唤大牛出来确认一下 :)
【在 f*********5 的大作中提到】
: 有人告诉过你这题有解？
: 如果有的话，merge sort就不需要额外空间了吧
|
|
|
s*****t
发帖数: 737 | 11 p2上存的数只可能来自之前p1上存的数，因为这个数比p3大，
所以被替换到p2上，如果现在p2比当前p3的数小，那么肯定p2是最小值。
所以要swap p2 and p1.
【在 I**A 的大作中提到】
: 你能不能说一下betterlate的思路
: 为什么(*p2 < *p3）就要swap p2 and p1?
|
s*****t
发帖数: 737 | 12 I see, you are right.
His code could not handle this case.
【在 d**e 的大作中提到】
: 这个就是我不明白的地方。
: 之前试了几个例子也是对的，不过我现在找到例子，他的程序错了。
: 比如3,4,5,6,1,2,7，最后的结果只是1,2,3,5,6,4,7
: 开始他可能是手误，if没加上判断 begin==inflection，否则如果array本来就是排好
: 的，比如1,2, 3, 4, 5,6,7，那么会进入死循环。不过这个问题不是很大。
: 我不是很明白while loop里面的，也就是你问的这个问题。最好betterlate可以说明一
: 下。
|
d**e
发帖数: 6098 | 13 是的，运行的结果是错的。
【在 s*****t 的大作中提到】
: I see, you are right.
: His code could not handle this case.
|
p*u
发帖数: 136 | 14 这个问题是有解的。不过面试考这样的题，太不厚道了，完全是超出能力范围的题目。
这是TAOCP上的一个练习题，有一篇196x年的论文专门给了解法的。
基本思想是把数组分成 sqrt(n + m) 这样的块，然后重复利用空间。
1，前n个数有序，后m个数有序。把前n个数和后m个数，分别划分成sqrt(n + m)大小的块。这样最多有sqrt(n + m)个块。
2，把前n个数的块和后m个数的块，做merge，用最后一个sqrt(n + m)大小的块做swap空间。这样下来的时间复杂度是O(n + m)，空间复杂度是O(1)的。
3，对于作为swap空间的最后一个块，直接做冒泡排序。时间复杂度O(n + m)，空间复杂度是O(1)的。
大致思想是上面这样的，具体细节我也记不清楚了。可以看看TAOCP，上面有习题解答。
【在 f*********5 的大作中提到】
: 有人告诉过你这题有解？
: 如果有的话，merge sort就不需要额外空间了吧
|
i*****e
发帖数: 113 | 15 嗯，的确有问题
前些日子看到一道面试题，第一子题目是把一个有序数组给分段了，第二个是如何合并
，大致这个意思。所以先入为主了
删原帖
【在 f*********5 的大作中提到】
: please check whether your code work well with below array
: 1,6,7,2,3,4,5,8
: BTW,why 尾递归所以空间没问题?
: recursion will use extra space
|
d**e
发帖数: 6098 | 16 牛！
看到我头晕
的块。这样最多有sqrt(n + m)个块。
swap空间。这样下来的时间复杂度是O(n + m)，空间复杂度是O(1)的。
复杂度是O(1)的。
答。
【在 p*u 的大作中提到】
: 这个问题是有解的。不过面试考这样的题，太不厚道了，完全是超出能力范围的题目。
: 这是TAOCP上的一个练习题，有一篇196x年的论文专门给了解法的。
: 基本思想是把数组分成 sqrt(n + m) 这样的块，然后重复利用空间。
: 1，前n个数有序，后m个数有序。把前n个数和后m个数，分别划分成sqrt(n + m)大小的块。这样最多有sqrt(n + m)个块。
: 2，把前n个数的块和后m个数的块，做merge，用最后一个sqrt(n + m)大小的块做swap空间。这样下来的时间复杂度是O(n + m)，空间复杂度是O(1)的。
: 3，对于作为swap空间的最后一个块，直接做冒泡排序。时间复杂度O(n + m)，空间复杂度是O(1)的。
: 大致思想是上面这样的，具体细节我也记不清楚了。可以看看TAOCP，上面有习题解答。
|
l******e
发帖数: 12192 | 17 nod，merge-sort O(1) space，太狠了
的块。这样最多有sqrt(n + m)个块。
swap空间。这样下来的时间复杂度是O(n + m)，空间复杂度是O(1)的。
复杂度是O(1)的。
答。
【在 p*u 的大作中提到】
: 这个问题是有解的。不过面试考这样的题，太不厚道了，完全是超出能力范围的题目。
: 这是TAOCP上的一个练习题，有一篇196x年的论文专门给了解法的。
: 基本思想是把数组分成 sqrt(n + m) 这样的块，然后重复利用空间。
: 1，前n个数有序，后m个数有序。把前n个数和后m个数，分别划分成sqrt(n + m)大小的块。这样最多有sqrt(n + m)个块。
: 2，把前n个数的块和后m个数的块，做merge，用最后一个sqrt(n + m)大小的块做swap空间。这样下来的时间复杂度是O(n + m)，空间复杂度是O(1)的。
: 3，对于作为swap空间的最后一个块，直接做冒泡排序。时间复杂度O(n + m)，空间复杂度是O(1)的。
: 大致思想是上面这样的，具体细节我也记不清楚了。可以看看TAOCP，上面有习题解答。
|
d********e
发帖数: 132 | 18 请问一下是TACOP 的第几个volumn？ thx
的块。这样最多有sqrt(n + m)个块。
swap空间。这样下来的时间复杂度是O(n + m)，空间复杂度是O(1)的。
复杂度是O(1)的。
答。
【在 p*u 的大作中提到】
: 这个问题是有解的。不过面试考这样的题，太不厚道了，完全是超出能力范围的题目。
: 这是TAOCP上的一个练习题，有一篇196x年的论文专门给了解法的。
: 基本思想是把数组分成 sqrt(n + m) 这样的块，然后重复利用空间。
: 1，前n个数有序，后m个数有序。把前n个数和后m个数，分别划分成sqrt(n + m)大小的块。这样最多有sqrt(n + m)个块。
: 2，把前n个数的块和后m个数的块，做merge，用最后一个sqrt(n + m)大小的块做swap空间。这样下来的时间复杂度是O(n + m)，空间复杂度是O(1)的。
: 3，对于作为swap空间的最后一个块，直接做冒泡排序。时间复杂度O(n + m)，空间复杂度是O(1)的。
: 大致思想是上面这样的，具体细节我也记不清楚了。可以看看TAOCP，上面有习题解答。
|
y****n
发帖数: 579 | |
c******n
发帖数: 4965 | 20 I think you guys can stop wasting time on this,
if merge sort O(n) time O(1) space is possible, no one would use qsort
in ur step 2)
": 2，把前n个数的块和后m个数的块，做merge，用最后一个sqrt(n + m)大小的块做
swap空间。这样下来的时间复杂度是O(n + m)，空间复杂度是O(1)的。"
why is "空间复杂度是O(1)" ? the "swap" space u use, isn't it already
occupied by the last sqrt(n+m) block? even if u can use that block, it's
size sqrt(n+m)
的块。这样最多有sqrt(n + m)个块。
swap空间。这样下来的时间复杂度是O(n + m)，空间复杂度是O(1)的。
复杂度是O(1)的。
答。
【在 p*u 的大作中提到】
: 这个问题是有解的。不过面试考这样的题，太不厚道了，完全是超出能力范围的题目。
: 这是TAOCP上的一个练习题，有一篇196x年的论文专门给了解法的。
: 基本思想是把数组分成 sqrt(n + m) 这样的块，然后重复利用空间。
: 1，前n个数有序，后m个数有序。把前n个数和后m个数，分别划分成sqrt(n + m)大小的块。这样最多有sqrt(n + m)个块。
: 2，把前n个数的块和后m个数的块，做merge，用最后一个sqrt(n + m)大小的块做swap空间。这样下来的时间复杂度是O(n + m)，空间复杂度是O(1)的。
: 3，对于作为swap空间的最后一个块，直接做冒泡排序。时间复杂度O(n + m)，空间复杂度是O(1)的。
: 大致思想是上面这样的，具体细节我也记不清楚了。可以看看TAOCP，上面有习题解答。
|
|
|
c******n
发帖数: 4965 | 21 I take it back, found it
indeed it's very cryptic:
http://en.wikipedia.org/wiki/Merge_sort#CITEREFKatajainenPasanenTeuhola1996
search "Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). "Practical
in-place mergesort". Nordic Journal of Computing 3:"
【在 c******n 的大作中提到】
: I think you guys can stop wasting time on this,
: if merge sort O(n) time O(1) space is possible, no one would use qsort
: in ur step 2)
: ": 2，把前n个数的块和后m个数的块，做merge，用最后一个sqrt(n + m)大小的块做
: swap空间。这样下来的时间复杂度是O(n + m)，空间复杂度是O(1)的。"
: why is "空间复杂度是O(1)" ? the "swap" space u use, isn't it already
: occupied by the last sqrt(n+m) block? even if u can use that block, it's
: size sqrt(n+m)
:
: 的块。这样最多有sqrt(n + m)个块。
|
d**e
发帖数: 6098 | 22 这个时间不是O(n)
【在 y****n 的大作中提到】
: TAOCP没找到.
|
y****n
发帖数: 579 | 23 没仔细看。
时间上O(n^2)了。
【在 d**e 的大作中提到】
: 这个时间不是O(n)
|
d**e
发帖数: 6098 | 24 所以前面creation也说了，如果时间是O(n),空间是O(1)，那其它sort不用也罢了。
【在 y****n 的大作中提到】
: 没仔细看。
: 时间上O(n^2)了。
|
w******a
发帖数: 236 | 25 这道题可不可以用in-place merge sort来解？当然需要两个指针first, second，查找
后分别指向需要swap的两个已排序的子数组的起始点，比如：
1 6 7 2 3 4 5 8 k=2, n=7, a[0..k] sorted, a[k+1..n] sorted
那么first指向6，second指向5，将“6 7 2 3 4 5”段swap，然后“5 4 3 2”和“7 6
”swap, 得到“2 3 4 5 6 7”，最后数组排好序：1 2 3 4 5 6 7 8
确定first和second:
first=0;
while (first <=k && a[first] < a[k+1]) first++;
second=k+1;maxmove=0;
while (second <=n && a[second] < a[first]) {second++;maxmove++;}
swap(a,first,second);
swap(a,first,first+maxmove);
swap(a,second-(k-first+1),second);
可以进一 |
p*u
发帖数: 136 | 26 是第三册的习题，讲排序的那一章。
严蔚敏版本的数据结构书，后面有个习题也是和这个类似，但是有一个特殊条件，前n
个数和后m个数的大小满足关系：n >= m * m
具体的大家可以去查一查课后习题，好像是在讲外部排序的那一章的习题吧，具体不太
记得了。
【在 d********e 的大作中提到】
: 请问一下是TACOP 的第几个volumn？ thx
:
: 的块。这样最多有sqrt(n + m)个块。
: swap空间。这样下来的时间复杂度是O(n + m)，空间复杂度是O(1)的。
: 复杂度是O(1)的。
: 答。
|
c******n
发帖数: 4965 | 27 http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html
现成的code 大伙儿仔细看看吧
n
【在 p*u 的大作中提到】
: 是第三册的习题，讲排序的那一章。
: 严蔚敏版本的数据结构书，后面有个习题也是和这个类似，但是有一个特殊条件，前n
: 个数和后m个数的大小满足关系：n >= m * m
: 具体的大家可以去查一查课后习题，好像是在讲外部排序的那一章的习题吧，具体不太
: 记得了。
|
c******n
发帖数: 4965 | 28 I see it now
I can understand the code, but the code is kind of different from the
paper from the Finnish guys.
the paper's most important point is "
given 2 sorted arrays, size N and M, N
we need only a size N extra workspace to merge these 2"
but the following code does not utilize that assertion.
the code is fairly clear:
array_A, array_B, let's say size(array_A) > size(array_B)
then cut A into halves
A1 A2 B
then for the first element x of A2, find the largest element in B that
is small
【在 c******n 的大作中提到】
: http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html
: 现成的code 大伙儿仔细看看吧
:
: n
|
c******n
发帖数: 4965 | 29 now I understand the Finnish paper:
just take the first element of the smaller array, x, binary search it in
the large one, find the prefix that's smaller than x, rotate first array
and the prefix, then you have
prefix < ( smaller array, what_is_left_of_the_bigger_array)
then treat the part of the smaller_array from second element on, and
recursively carry out this procedure.
in the end, each element is rotated at most once.
【在 v******a 的大作中提到】
: Given an array of n elements and an integer k where k: Elements {a[0].....a[k] and a[k+1].....a[n] are already sorted. Give an
: algorithm to sort in O(n) time and O(1) space.
: 怎么做这个？
|
c******n
发帖数: 4965 | 30 the code for the Finnish paper algorithm
// O(n) time O(1) space merge of 2 arrays
//
public class smart_merge {
static int N=50;
//// return the largest i so that data[i]<= data[key_pos]
public static int lower(int data[] , int start, int key_pos ) {// we
know that the largest is 2N;
int end = N * 2;
start --; // if the return value is this one, that means
everything in the sub array is larger than key_pos
while ( start < end -1 ) {
int mid = ( s
【在 v******a 的大作中提到】
: Given an array of n elements and an integer k where k: Elements {a[0].....a[k] and a[k+1].....a[n] are already sorted. Give an
: algorithm to sort in O(n) time and O(1) space.
: 怎么做这个？
|
|
|
d**e
发帖数: 6098 | 31 谢谢。明天再仔细研究一下。
【在 c******n 的大作中提到】
: the code for the Finnish paper algorithm
: // O(n) time O(1) space merge of 2 arrays
: //
: public class smart_merge {
: static int N=50;
: //// return the largest i so that data[i]<= data[key_pos]
: public static int lower(int data[] , int start, int key_pos ) {// we
: know that the largest is 2N;
: int end = N * 2;
: start --; // if the return value is this one, that means
|
