How to return Kth smallest/largest element from an array using quicksort's pivot?

1
votes

I am trying to find Kth smallest element in an array => val a = Array[Int](10, 1, 7, 2, 25, 11, 14)

To do this, I used the pivot mechanism of quicksort algorithm. Based on the Pivot position, I am recursively calling the pivot method from start to pivot position or from pivot+1 position to the end of the array.

Below is the logic I wrote.

object KthLargestSmallestOfArray extends App {
  val a = Array[Int](10, 1, 7, 2, 25, 11, 14)
  val k = 3
  println(kthSmallest(a, 0, a.length-1, k))

  def partition(arr: Array[Int], low: Int, high: Int): Int = {
    val pivot = high
    var i = low - 1
    for(j <- low until high) {
      if(arr(j)<arr(pivot)) {
        i += 1
        swap(arr, i, j)
      }
    }
    swap(arr, i+1, high)
    i+1
  }

  def swap(arr: Array[Int], l: Int, h: Int): Unit = {
    val temp = arr(l)
    arr(l) = arr(h)
    arr(h) = temp
  }

  @tailrec
  def kthSmallest(arr: Array[Int], p: Int, q: Int, index: Int): Int = {
    if(p==q && p==index) {
        arr(p)
    } else {
      val r = partition(arr, p, q)
      if(r == k) {
        arr(r)
      } else if(r < k) {
        kthSmallest(arr, r+1, q, k)
      } else kthSmallest(arr, p, r-1, k)
    }
  }
}

When I run the code, with input of k = 3, the code is considering 10 as the output.

If I sort the elements of the array => (1, 2, 7, 10, 11, 14, 25), 7 is the third biggest element. The array has 10 as its 4th element (0 to 3..6) and the array(k) is 10 and hence it is returning 10. If I supply k as 4, output is 11 and so on.

Is there anyway I can return 7 instead of 10 ? Because 7 is the third smallest element from the beginning which matches with the value of k I am supplying.

Could anyone let me where am I making the mistake and how can I correct it ?

2
arraysalgorithmscala
Are you aware of the QuickSelect algorithm? en.wikipedia.org/wiki/…. - RBarryYoung
I am aware of it but I cant use the partitions for sorting. Instead I just have to return the value of K - Metadata
It's not the mistake you're looking for, but pay attention to using index instead of k in the kthSmallest method (or just rename index to k), otherwise you'll use the value outside the local scope instead of the parameter). - stefanobaghino
Just noticed this was already reported in the answer by @trincot. - stefanobaghino

2 Answers

3
votes

I am not fluent in scala, but I see two potential issues:

  • The function has a parameter with name index, but you continue to reference k in the body of the function. This is not really a bug, as you never pass any other value than the original k value, but it just looks bad, so better change the name of that parameter to k. The real issue is the next one:

  • As k really is a 1-based position, while p and q are 0-based indices, you should adjust the comparisons between r and k (or index) accordingly. You are looking to match (r == k - 1) (at two places), and also change (r < k) to (r < k - 1).

1
votes

@trincot is correct:

  • The kthSmallest() method references k when you mean to reference index.
  • The smallest would be at index 0, the 2nd smallest at index 1, etc. So the kth smallest would be at index k-1.

But there's more:

  • Your code throws a runtime error if index is out-of-bounds for array arr. Maybe that's by design, but there are better ways of handling that.
  • The code has a nasty side effect of leaving the arr array in an indeterminate state. It might be sorted, it might be semi-sorted (i.e. just shuffled). That's a bug waiting to happen.

But the real issue here is that it's not Scala. You're using the Scala language to write C code.

Scala has a rich Standard Library that enables more concise coding. You might, for example, use a PriorityQueue which only sorts its elements as much as needed to retrieve the next-priority item.

def kthSmallest[A:Ordering](arr: Array[A], idx: Int): A = {
  val rpq = mutable.PriorityQueue(arr:_*).reverse
  Iterator.continually(rpq.dequeue())
          .drop(idx min arr.length-1)
          .next()
}

If you're keen on using a partition method, why not partition() the Array directly?

@annotation.tailrec
def kthSmallest[A:Ordering](arr: Array[A], idx: Int): A = {
  import Ordering.Implicits._
  if (idx > arr.length-2) arr.max
  else if (idx < 1)       arr.min
  else arr.partition(_ < arr.head) match {
    case (Array(), b) => kthSmallest(b.tail, idx-1)
    case (a, b) => if (a.length > idx) kthSmallest(a, idx)
                   else kthSmallest(b, idx - a.length)
  }
}

It all depends on what purpose this code is supposed to serve. If you're going through some simple exercises in order to learn the language then, so far, you're missing out on what makes Scala, Scala.