Fra*_* Q. 8 algorithm mergesort
我从一个谈论外部合并排序的链接得到了这个.
从幻灯片6示例:使用5个缓冲页面,对108页面文件进行排序
Pass0:[108/5] = 22个分类运行,每个5页(最后一次只运行3页)
Pass1 [22/4] = 6个分类运行,每个20页(最后一次只运行8页)
Pass2:[6/3] = 2个分类运行,80页和28页
通过3:[2/2] = 1 108页的分类文件
问题:我的理解是在外部合并排序中,在传递0中,您创建块然后对每个块进行排序.在剩余的传球中,你不断合并它们.因此,将其应用于上面的示例,因为我们只有5个缓冲页面,在Pass 0中它清楚我们需要22个排序的运行,每个5页.
现在,为什么我们要为剩余的传递进行排序运行而不是合并？
当我们只有5个缓冲页面时,它怎么告诉传递1,6个分类的每个20页的运行？
这里合并的确切位置在哪里？如何在每次通过中减少N,即从108减少到22到6到2？
Jus*_*son 16
如果无法将所有数据存储到内存中,则必须进行外部合并排序.您可以做的最好的事情是将数据分解为已排序的运行并在后续过程中合并运行.运行的长度与可用的缓冲区大小相关联.
Pass0:你正在进行IN PLACE操作.因此,您将5页数据加载到缓冲区中,然后使用就地排序算法对其进行排序.这5页将作为运行存储在一起.
以下过程:由于您正在合并许多页面的运行,因此您无法再进行操作.4页被加载到缓冲区,第5页是写缓冲区.该合并是相同的合并排序算法,但你会被划分并在写入缓冲区被填满,它被写入到磁盘上和下页开始B-1而不是2倍征服.
复杂性:在分析外部合并排序的复杂性时,正在考虑的是I/O的数量.在每次传递中,您必须阅读页面并编写页面.设N为页数.每次运行将花费2N.阅读页面,写下页面.
设B是可以容纳缓冲区空间的页数,N是页数.
将有ceil(log_B-1(ceil(N/B)))通过.每个传递将有2N I/O. 所以O(nlogn).
在每次传递中,运行的页面长度增加了B-1倍,并且排序的运行数量减少了B-1倍.
Pass0:ceil(108/5)= 22,每次运行5页
Pass1:ceil(22/4)= 6,每次运行20页
Pass2:ceil(6/4)=
2,80 页每次运行Pass3:ceil(2/4)= 1 - 完成,1次运行108页