title: How can I make my quickselect algorithm faster
body: <p>I have taken a course that examines algorithms and we have an assignment to do the classic k:th smallest element (0 being the smallest and <code>sequence.length-1</code> being the biggest) with quickselect. </p>
  
  <p>The algorithm should be on average 2*faster than the sorting method</p>
  
  <pre><code>Arrays.sort
  </code></pre>
  
  <p>My algorithm works but it isn't fast enough. It is on average 5 times slower than the above method for sorting arrays. Here is my implementation so far:</p>
  
  <pre><code>  def find(sequence: Seq[Int], k: Int): Int = {
      require(0 &lt;= k &amp;&amp; k &lt; sequence.length)
      val a: Array[Int] = sequence.toArray[Int]
      select(a,k)
    }
  
    def select(a: Array[Int], k: Int): Int = {
      val pivot = rand.nextInt(a.length)     
      val (low, middle, high) = partition(a,a(pivot))
      if (low.length == k) a(pivot)
      else if(low.length &gt; k) select(low, k) 
      else if (low.length + middle.length &gt;= k+1) middle(0)
      else if (low.length == 0) select(high, k - low.length-middle.length)
      else  findFast(high, k - low.length-middle.length)
    }
  
    def partition(array: Array[Int],pivot: Int): (Array[Int],Array[Int],Array[Int])={
      (array.filter(_&lt;pivot),array.filter(_==pivot),array.filter(_&gt;pivot))
    }
  </code></pre>
  
  <p>Could you give me some tips with which to improve the runtime of my implementation?</p>