title: kth smallest number - quicksort faster than quickselect
body: <p>I have implemented the following quickselect algorithm to achieve <code>O(n)</code> complexity for median selection (more generally kth smallest number):</p>
  
  <pre><code>static size_t partition(struct point **points_ptr, size_t points_size, size_t pivot_idx)
  {
      const double pivot_value = points_ptr[pivot_idx]-&gt;distance;
  
      /* Move pivot to the end. */
      SWAP(points_ptr[pivot_idx], points_ptr[points_size - 1], struct point *);
  
      /* Perform the element moving. */
      size_t border_idx = 0;
      for (size_t i = 0; i &lt; points_size - 1; ++i) {
              if (points_ptr[i]-&gt;distance &lt; pivot_value) {
                      SWAP(points_ptr[border_idx], points_ptr[i], struct point *);
                      border_idx++;
              }
      }
  
      /* Move pivot to act as a border element. */
      SWAP(points_ptr[border_idx], points_ptr[points_size - 1], struct point *);
  
      return border_idx;
  }
  
  static struct point * qselect(struct point **points_ptr, size_t points_size, size_t k)
  {
      const size_t pivot_idx = partition(points_ptr, points_size, rand() % points_size);
  
      if (k == pivot_idx) { //k lies on the same place as a pivot
              return points_ptr[pivot_idx];
      } else if (k &lt; pivot_idx) { //k lies on the left of the pivot
              //points_ptr remains the same
              points_size = pivot_idx;
              //k remains the same
      } else { //k lies on the right of the pivot
              points_ptr += pivot_idx + 1;
              points_size -= pivot_idx + 1;
              k -= pivot_idx + 1;
      }
  
      return qselect(points_ptr, points_size, k);
  }
  </code></pre>
  
  <p>Then I tried to compare it with a glibc's <code>qsort()</code> with <code>O(nlog(n))</code> and was surprised by its superior performance. Here is the measurement code:</p>
  
  <pre><code>double wtime;
  wtime = 0.0;
  for (size_t i = 0; i &lt; 1000; ++i) {
      qsort(points_ptr, points_size, sizeof (*points_ptr), compar_rand);
      wtime -= omp_get_wtime();
      qsort(points_ptr, points_size, sizeof (*points_ptr), compar_distance);
      wtime += omp_get_wtime();
  }
  printf("qsort took %f\n", wtime);
  
  wtime = 0.0;
  for (size_t i = 0; i &lt; 1000; ++i) {
      qsort(points_ptr, points_size, sizeof (*points_ptr), compar_rand);
      wtime -= omp_get_wtime();
      qselect(points_ptr, points_size, points_size / 2);
      wtime += omp_get_wtime();
  }
  printf("qselect took %f\n", wtime);
  </code></pre>
  
  <p>with results similar to <code>qsort took 0.280432</code>, <code>qselect took 8.516676</code> for an array of 10000 elements. Why is quicksort faster than quickselect?</p>