CODEWITHSUNDEEP
scalarecursioninfinite
user_123945839432
user_123945839432

Reputation: 189

Sorting function in Scala runs for a long time

I am trying to write a recursive function in SCALA that take sin a list and sorts it.

However, the code seems to run for a long time. It doesn't even give me an error message. 

def sort(list:List[Int]):List[Int] = list match{

  case Nil => Nil
   case h::t => insert (h, sort(t))
def insert(num:Int, list:List[Int]): List[Int]=list match{
  case Nil => List()
   case head::tail=>
     if(head>=num)
        num::list
     else
       head::insert(num,tail)
   }
 sort(list)
}

Upvotes: 1

Views: 178

Answers (1)

yǝsʞǝla
yǝsʞǝla

Reputation: 16412

You had 2 problems:

1) you are calling sort recursively from sort function directly - remove sort(list) because insert already calls it. This will make it terminate.

2) you return an empty list in one of the cases instead of constructing a list with 1 elem - base case is wrong.

This version works:

    def sort(list: List[Int]): List[Int] = {
        def insert(num: Int, list: List[Int]): List[Int] = list match {
          case Nil => num :: Nil
          case head::tail =>
            if(head >= num)
              num::list
            else
              head::insert(num, tail)
        }
        list match {
          case Nil => Nil
          case h::t => insert(h, sort(t))
        }
    }

Upvotes: 1

Related Questions