2

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
JavaAndCSharp
  • 1,507
  • 3
  • 23
  • 47
user355002
  • 871
  • 2
  • 10
  • 22

1 Answers1

4

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 50th 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 50th 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.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
  • 2
    I would remark it requires either to modify the structure OR to use `O(N)` storage (ie copy and partition the copy). – Matthieu M. Jun 26 '10 at 19:04