Scala - Remove while loop in quick sort

Question

def QuickSort(arr:Array[Int],first:Int,last:Int): List[Int] = {
    var pivot:Int = 0
    var temp:Int = 0
    if (first < last) {
        pivot = first
        var i:Int = first
        var j:Int = last;
        while(i<j){
            while(arr(i) <= arr(pivot) && i < last)
                i=i+1
            while(arr(j) > arr(pivot))
                j=j+1
            if(i<j)
            {
                temp = arr(i)
                arr(i) = arr(j)
                arr(j) = temp
            }
        }
        temp = arr(pivot)
        arr(pivot) = arr(j)
        arr(j) = temp
        QuickSort(arr, first, j-1)
        QuickSort(arr, j+1, last)
    }
    arr.toList
  }

Hello I m new to scala and trying to implement quick sort. Program is working correctly but I want to remove the while loop since I read that while and do while are not recommended in scala because they do not return any value.

Is there any way to remove while loop in above code.

Answer 1

The classic quicksort algorithm, as you've coded here, requires a mutable collection (like Array) and the swapping of element values, which requires mutable variables (i.e. var). These things are discouraged in functional programming and aren't held in high esteem in the Scala community.

Here's a similar approach that is a little more in keeping to the spirit of the FP ethic.

// pseudo-quicksort -- from Array[Int] to List[Int]
def pqs(arr:Array[Int]): List[Int] = arr match {
  case Array()    => List()
  case Array(x)   => List(x)
  case Array(x,y) => if (x < y) List(x,y) else List(y,x)
  case _ => val (below, above) = arr.partition(_ < arr(0))
            pqs(below) ++ List(arr(0)) ++ pqs(above.tail)
}

Better yet is to use one of the sort methods (sortBy, sortWith, sorted) as offered in the standard library.