title: Partition in Quickselect
body: <p>I have to implement an algorithm that returns the median of an array. So I chose to implement Quickselect which seems to be efficient for this and I saw that for the tripartition I can use the same partition algorithm used in Quicksort.</p>
  
  <p>The <strong>partition algorithm</strong> reported in my lecture notes (in C code) is the following:</p>
  
  <pre><code>for (i = lo, j = hi;
       (i &lt;= j);)
  {
      while (a[i] &lt; pivot)
      {
          i++;
      }
  
      while (a[j] &gt; pivot)
      {
          j--;
      }
  
      if (i &lt;= j)
      {
          if (i &lt; j)
          {
              /* exchange values */
              tmp = a[i];  
              a[i] = a[j];
              a[j] = tmp;
          }
  
          i++;
          j--;
      }
  
  }
  </code></pre>
  
  <p>Now, if my array is: a = [40, 20, 100, 60, 80] and I choose as pivot the number 80, the result is: a = [40, 20, <strong>80</strong>, 60, 100], but as you can see the values in the right partition are not all > 80 (we have 60). If I choose any other number the algorithm works properly.</p>
  
  <p>Is this algorithm wrong?</p>
  
  <p>Thank you for your help in advance!</p>