CODEWITHSUNDEEP
scalainsertion-sort
Learner
Learner

Reputation: 35

Insertion sort not working in my code written in Scala

I am writing a function to perform insertion sort. While writing the code, I am getting the same list as output again.

def insertionSort(xs: List[Int]): List[Int] =
{
  if (xs.isEmpty) Nil
  else insert(xs.head, xs.tail)
}

def insert(x: Int, xs: List[Int]): List[Int] =
{
  if (xs.isEmpty || x <= xs.head) x :: xs
  else xs.head :: insert(x, xs.tail)
}

Can somebody please let me know where I am going wrong.

Upvotes: 2

Views: 126

Answers (1)

Chaitanya
Chaitanya

Reputation: 3638

I guess you are missing a small recursive call in your function. Please refer the code below.

def insertionSort(xs: List[Int]): List[Int] =
{
  if (xs.isEmpty) Nil
  else insert(xs.head, insertionSort(xs.tail))
}


def insert(x: Int, xs: List[Int]): List[Int] =
{
  if (xs.isEmpty || x <= xs.head) x :: xs
  else xs.head :: insert(x, xs.tail)
}

I guess that should work now.

Upvotes: 2

Related Questions