ITPub博客

首页 > 数据库 > PostgreSQL > REPLACEMENT SELECTION SORT

REPLACEMENT SELECTION SORT

PostgreSQL 作者:husthxd 时间:2019-05-29 18:43:15 0 删除 编辑

REPLACEMENT SELECTION SORT,适用于内存较小的情况(在高德纳提出该算法的年代,内存比起现在少了N个数量级).
该算法在PG 9.x或以下版本在使用,在高版本已被废弃.其算法实现如下:

Let m be the number of records to be sorted which can be kept in the main memory. Imagine that these memory locations are registers and assume we can mark them as “on” or “off”. Replacement selection can overlap reading, sorting and writing.


Step1: The m registers are filled with records from the input to be sorted.
Step2: All registers are put into the “on” state.
Step3: Select the register which has the smallest of all “on” registers.
Step4: Transfer the contents of the selected register to the output (call it as key Y).
Step5: Replace the contents of the selected register by the next input record.
            If new record key > Y
                        Go to step 3
            If new record key = =Y
                        Go to step 4
            If new record key < Y
                        Go to step 6
Step6: Turn the selected key register  “off”.
            If all registers are now  “off”
                        We have completed a sorted substring(run).
                        We start a new substring group and go to step 2.
            Else
                        Go to step 3

下面是该算法的一个例子:


Example: Suppose number of registers is 3 and input keys are 5, 2, 9, 7, 0, 8, 1, 6, 3, 4 ...
            Registers                               Output
            5 2 9                                       2
            5 7 9                                       5
*0 7 9                                     7
*0 8 9                                     8
*0*1 9                                    9
*0*1*6
0 1 6                                       0
3 1 6                                       1
3 4 6                                       3
- 4 6                                        4
- - 6                                        6
- - -

相关的数据结构:两个数组,一个存储读取的实际数据,一个标记数组;一个外存,用于存储已完成排序的一个run.
如标记数组全为F(非活动状态),则产生一个run,周而复始,直至所有输入被耗尽为止.
通过这个方法,可以生成N个runs(每个run对应的是已完成排序的部分数据).

CS 351 -Data Organization and Management ( Section: 02)
External_sorting
replacement-selection-sort vs selection-sort

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/6906/viewspace-2646119/,如需转载,请注明出处,否则将追究法律责任。

下一篇: Polyphase Merge Sort
请登录后发表评论 登录
全部评论
长期从事政务、金融等行业产品研发和架构设计工作,ITPUB数据库版块资深版主,对Oracle、PostgreSQL有深入研究。现就职于广州云图数据技术有限公司,系统架构师。

注册时间:2007-12-28

  • 博文量
    1270
  • 访问量
    3746634