gpt4 book ai didi

c - 合并插入排序如何工作?

转载 作者:太空狗 更新时间:2023-10-29 15:35:34 24 4
gpt4 key购买 nike

我目前正在研究排序算法并找到了合并插入排序。我几乎找不到任何东西,但只有几篇论文和书籍引用。所以这个算法是由 Lester Ford, Jr. 和 Selmer Johnson 发现的。此处对其进行了部分描述:http://www2.warwick.ac.uk/fac/sci/dcs/teaching/material/cs341/FJ.pdf

我现在的问题是了解插入部分的工作原理以及 1、3、5、11 是什么数字序列,在如何插入的解释中提到。它看起来很眼熟,但我就是想不起它是什么。

我现在的代码是这样的:

//pointer to array, array size, element size, compare function pointer
void sort(void *data, size_t n, size_t s, int (*fcomp)(void*, void*))
{
if(!data) return;
if(n < 2 || s == 0) return;

size_t i = 0, j = 0, k = 0, l = 0, r = 0, m = 0;

void *be = malloc((n/2)*s); //elements greater in pair comparison
void *le = malloc((n/2 + n%2)*s);//elements lesser in pair comparison
void *mc = malloc(n*s); //main chain

//compare pair-wise K_1:K_2, ... , K_N:K_N-1
for(i = 0; i < n; i+=2)
{
if(fcomp(voidAdd(data, s, i), voidAdd(data, s, i+1)) >= 0)
{
//element at i bigger than i+1 so, put it in be and i+1 in le
memcpy(voidAdd(be, s, k++), voidAdd(data, s, i), s);
memcpy(voidAdd(le, s, j++), voidAdd(data, s, i+1), s);
}
else
{
//element i+1 bigger than i so put it in be and i in le
memcpy(voidAdd(be, s, k++), voidAdd(data, s, i+1), s);
memcpy(voidAdd(le, s, j++), voidAdd(data, s, i), s);
}
}

sort(be, n/2, s, fcomp); //recursivly repeat process for bigger elements
/*
now we have chain a_1, ..., a_n/2 and b_1, ..., b_n/2 with a_i > b_i and
a_1 < ... a_n/2
*/

memcpy(mc, le, s); //insert b_1 into the main-chain
memcpy(voidAdd(mc, s, 1), be, (n/2)*s); //copy a_1, ... a_n/2 in main chain
//now we have b_1, a_1, ..., a_n/2 as main chain

//start insertion here
j = n/2 + 1;
for(i = 1; i < n/2; i++)
{
k = ...;//number from sequence 1, 3, 5, 11, ...
}

memcpy(data, mc, n*s);
free(mc);
free(be);
free(le);

}

根据链接的 pdf 中的内容,它现在需要通过二进制插入将 b_3、b_2、b_5、b_4 ...这些数字来自。

最佳答案

我其实implemented this algorithm in C++本周并且能够理解插入部分的工作原理。我真的不想重复自己,所以我会引用自己的话:

To perform a minimal number of comparisons, we need to take into account the following observation about binary search: the maximal number of comparisons needed to perform a binary search on a sorted sequence is the same when the number of elements is 2^n and when it is 2^(n+1)−1. For example, looking for an element in a sorted sequence of 8 or 15 elements requires the same number of comparisons.

基本上,在主链中插入第一个pend元素后,算法会取最远的pend元素,需要进行2次比较要做的:你需要 2 次比较才能插入少于 4 个元素,所以我们采用 b3在论文中,因为我们可以将其插入 {b1, a1, a2} .接下来,我们知道 b2 < a2所以我们可以插入 a2在主链中要么是{b1, a1}{b1, a1, b2} ,这意味着我们将它插入到最多 3 个元素的链中,因此我们最多需要 2 次比较才能插入它。接下来,我们需要一个最多可插入 3 次比较的元素,因此需要将其插入最多 7 个元素的主链中:我们有 b5 < a5 , 所以我们可以插入 b5{b1, a1, b2, a2, a3, b3, a4}这恰好是 7 个元素的主链,等等......

下一个pend b选择将始终对应于您可以插入大小为 2^n - 1 的主链中的元素。Knuth 设法找到@orlp 给出的生成公式:t(k) = (2^(k+1) + (-1)^k)/3 .生成的数字恰好对应于 Jacobsthal numbers ;该系列增长如此之快,以至于您可以简单地缓存它们,第 66 个 Jacobsthal 数字甚至不适合 64 位整数。一旦你插入了这样一个元素 bk , 您可以以相反的顺序插入所有 bk k 的元素小于当前的 Jacobsthal 数。如果在排序末尾有pend 元素,但它们都没有对应于 Jacobsthal 数的索引,只需将它们插入主链;插入顺序无关紧要,因为无论插入顺序如何,插入其中任何一个所需的比较次数应该相同。

关于c - 合并插入排序如何工作?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27751132/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com