Insertion sort implementation in scala

Question

I'm trying out Scala and I want to see how one would implement insertion sort in scala with the following requirements:

1. Nested for loops
2. Array[Int] for input
3. If possible a way to modify the contents of the function in a call by reference way otherwise return an Array[Int]

If this isn't the Scala way of implementing insertion sort can you still provide code for the above and explain what is wrong with the approach. edit: This is an attempt using a while loop (doest work) and no it isn't a homework question, why the hostility?

def insert_sort(a:Array[Int]):Array[Int]={
for(i <- 0 until a.length)
{
  var j=i+1

  while(j>1&&a(j)<a(j-1)&&j<a.length)
  {
      var c=a(j)
      a(j)=a(j-1)
      a(j-1)=c
      j-=1
  }
}
return a
}

Answer 1

Nested for loops are probably not the answer in Scala, whatever is the problem. They make sense in languages where for loops stand for "repeat until condition, changing this each iteration", which is not what for loops or for comprehensions are in Scala (a for comprehension is a for loop which yields something for each iteration).

In Scala, for loops and for comprehensions are iterations over the elements of a collection (or weirder things for non-collection monads), but for insertion sort you want to find a position, either swapping places up to that position, or inserting the element at that position. Finding stuff should not be done with for loops or for comprehensions.

Also, there's no pass-by-reference in Scala. And, in fact, Array is not even a Scala collection, but a Java thingy which has unique characteristics granted to it by the JVM that are not reproducible with classes, so it can't be replaced.

Answer 2

My version of the insertion sort procedure is the following. It consists of two functions, isort and insert which have the following signatures:

• isort(xs: List[int]) : List[int]: Takes an input list of integers and outputs a list of integers.
• insert(x: Int, xs: List[int]) : List[int] Takes a sorted input list and an integer x and adds x to the right position in the list to maintain the invariant that the list is sorted. Example: insert(3, [1, 2]) = [1, 2, 3]

First let us code up the insert function.

1. If the list is empty, return a list of the integer to be added.

2. Otherwise, there are two possible cases. The head of the list is greater or equal to the given input integer, in which case we simply append the input integer to the beginning of the list and return it. The other case is when the input integer is greater than the head of the input list. In this case, we recursively insert the input integer into the tail of the list.

   def insert(x : Int, xs : List[Int]) : List[Int] = {
   
   xs match{
       case Nil => List(x)
       case y :: xs1 =>
           if(y >= x) x :: xs
           else y :: insert(x,  xs1)
    }
   
   }
   

The second function is isort, which takes an input list and sorts it. The algorithm is as follows:

1. If the input list is equal to Nil, return Nil.

2. Otherwise, recursively sort the tail of the list, and add the head at the right position in the (sorted) tail (using the insert procedure)

    def isort(xs : List[Int]) : List[Int] = {
     xs match{
       case Nil => Nil
       case x :: xs1 => insert(x, isort(xs1))
   
      }
   
    } 
   

We can test this as isort(List(1, 6, 4, -2, 5, 12)) and we get the correct expected output.

Answer 3

Here is a code sample written using foldLeft.

def insertionSort(input: List[Int]): List[Int] = {

  input.foldLeft(List[Int]())( (acc, element) => {

    val (firstHalf, secondHalf) = acc.span(_ < element)

    //inserting the element at the right place
    firstHalf ::: element :: secondHalf
  })
}

The example can be found in this github repo.

Answer 4

This is what I came up with, which seems to be functional, generic, tail-recursive (foldLeft is tail-recursive)...:

def insertionSort[A](la: List[A])(implicit ord: Ordering[A]): List[A] = {
  def insert(la: List[A], a: A) = {
    val (h, t) = la.span(ord.lt(_, a))
    h ::: (a :: t)
  }

  la.foldLeft(List[A]()) {(acc, a) => insert(acc, a)}
}

Answer 5

here's another generic version of insertion sort:

  def less[T <: Comparable[T]](i: T, j: T) = i.compareTo(j) < 0

  def swap[T](xs: Array[T], i: Int, j: Int) { val tmp = xs(i); xs(i) = xs(j); xs(j) = tmp }

  def insertSort[T <: Comparable[T]](xs: Array[T]) {
    for { i <- 1 to xs.size
          j <- List.range(1, i).reverse
          if less(xs(j),xs(j - 1)) } swap(xs, j, j -1)
  }

Answer 6

The most elegant insertion sort algorithm implementation that I'we seen so far:

val rand = List(5,3,1,2)

def isort(xs: List[Int]): List[Int] =
  if (xs.isEmpty) Nil
  else insert(xs.head, isort(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)

isort(rand) // Produces List(1,2,3,5)

Algorithm implementation is taken from this great book: https://www.artima.com/shop/programming_in_scala_3ed