title: Understanding a median selection algorithm?
body: <p>I'm currently learning algorithms in my spare time but have the following question while studying chapter 3 select() algorithms.</p>
  
  <p>I understand that I can use the select() algorithm to find the median number (n/2 th smallest number) if I was using a array from A to n numbers.</p>
  
  <p>1) but this is the bit I'm struggling to understand. A = [3, 7, 5, 1, 4, 2, 6, 2]. suppose that is the array. what is contents of the array after each call to Partition(), and the parameters in each recursive call of Select().</p>
  
  <p>can some one explain how they are working this out please?</p>
  
  <p>below is the pseudo-code for the 2 algorithms.</p>
  
  <pre><code>Select(A, p, r, k) {
      /* return k-th smallest number in A[p..r] */
      if (p==r) return A[p] /* base case */
      q := Partition(A,p,r)
      len := q – p + 1
      if (k == len) return A[q]
      else if (k&lt;len) return Select(A,p,q-1,k)
      else return Select(A,q+1,r,k-len)
  }
  </code></pre>
  
  <p>and the second code is</p>
  
  <pre><code>Partition(A, p, r) { /* partition A[p..r] */
      x := A[r] /* pivot */
      i := p-1
      for j := p to r-1 {
          if (A[j] &lt;= x) {
              i++
              swap(A[i], A[j])
          }
      }
      swap(A[i+1], A[r])
      return i+1
  }
  </code></pre>
  
  <p>The book I am using is called <em>The Derivation of Algorithms</em> by Anne Kaldewaij.</p>