通过枢轴在选择算法复发 [英] recur by using the pivot in Select algorithm

问题描述

我有一个问题，我不能让这个网站的选择算法线（14,15,16,17）的目的。

这有这个问题的是位于该网站<​​一href="http://webcache.googleusercontent.com/search?q=cache:2PhiYQ1r76kJ%3awww.cse.yorku.ca/~andy/courses/3101/lecture-notes/LN4.ps%20Linear%20general%20selection%20algorithm%20$c$c&cd=3&hl=en&ct=clnk"相对=nofollow>这里。

编辑：还有，这是正确的写这些线路的部分的的分区，并通过枢轴复发的？ （M是我的支点和i是该算法的输入）

  arrOne＆LT;  -  {一ARR的：A＆LT，M}
         arrTwo＆其中 -  {一个改编的：a取代;米}
         如果（ⅰ＆其中;米），则
               返回选择（arrOne，I）
         否则如果（ⅰ＆GT;米），则
                返回选择（arrTwo，I-M）
         其他
                回报米
 

解决方案

这是它选择在递归分区。

为了便于说明，我们假设你正在寻找有100个元素的数组的中位数。当您第一次分区，你得到的，比如分区，60和40项。既然你正在寻找的50 ^日的项目，你知道它的必须的是在左侧分区（其中有60个项目）。

您再分区，并得到，我们会说，左，25和35项分别正确的分区。这个时候我们可以看到，50 ^日的项目必须在正确的分区，所以我们递归到一个。

我们继续这样直到我们达到一个分区只包含一个项目 - 。我们正在寻找一个

I have a problem and I can not get the purpose of lines (14,15,16,17) of this site for Select algorithm.

The site which had this question was located here.

EDITED: Also, is this correct to write these lines for the part "partition and recur by using the pivot"? ("m" is my pivot and "i" is the input of this algorithm)

         arrOne<--{a of arr : a<m}
         arrTwo<--{a of arr : a>m}
         if    (i < m ) then
               return Select(arrOne,i)
         else if (i > m)  then
                return Select(arrTwo,i-m)
         else 
                return m

解决方案

This is where it selects the partition in which to recurse.

For the sake of illustration, let's assume you're looking for the median of an array with 100 elements. The first time you partition, you get partitions of, say, 60 and 40 items. Since you're looking for the 50^th item, you know it must be in the left partition (which has 60 items).

You then partition that, and get, we'll say, left and right partitions of 25 and 35 items respectively. This time we can see that the 50^th item must be in the right partition, so we recurse into that one.

We continue this until we reach a partition that contains only one item -- the one we're looking for.

这篇关于通过枢轴在选择算法复发的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！