CODEWITHSUNDEEP
scalarecursion
Michael Hagar
Michael Hagar

Reputation: 646

Scala stack overflow error

I'm new to Scala and having trouble with this portion of code. I'm getting a stack overflow error on line 18 / 20, but I am not sure why.

def quicksort(list : List[Int]) : List[Int] = list match {
  case Nil => List()
  case x::Nil => List(x)
  case x::xs => {
    val lesserList = partitionLesser(list.tail, list(0))
    val greaterList = partitionGreater(list.tail, list(0))
    quicksort(lesserList ::: List(x) ::: greaterList)
  }
}

def partitionLesser(list : List[Int], pivot : Int) : List[Int] = list match{
  case Nil => List()
  case x::Nil => List(x)
  case x::xs => {
    if(x <= pivot) { x :: partitionLesser(list.tail, pivot) }
    else { partitionLesser(list.tail, pivot) } 
  }
}

def partitionGreater(list : List[Int], pivot : Int) : List[Int] = list match {
  case Nil => List()
  case x::Nil => List(x)
  case x::xs => {
    if(x > pivot) { x :: partitionGreater(list.tail, pivot) }
    else { partitionLesser(list.tail, pivot)}
  }
}

Upvotes: 0

Views: 125

Answers (1)

Tim Green
Tim Green

Reputation: 3649

def quicksort(list : List[Int]) : List[Int] = list match {
  case Nil => List()
  case x::Nil => List(x)
  case x::xs => {
    val lesserList = partitionLesser(list.tail, list(0))
    val greaterList = partitionGreater(list.tail, list(0))
    // quicksort(lesserList ::: List(x) ::: greaterList)
    quicksort(lesserList) ::: List(x) ::: quicksort(greaterList)
  }
}

Upvotes: 2

Related Questions