CODEWITHSUNDEEP
scalasortingrecursiontail-recursion
Rodrigo Cifuentes Gómez
Rodrigo Cifuentes Gómez

Reputation: 1324

Recursive sort in scala with tail recursion

I'm trying to write this algorithm with tail recursion in Scala.

public ArrayList sort(ArrayList<int> toSort)
{
  ArrayList<int> list=toSort;
      for(int i=0; i<list.size();i++)
      {    int min=100;
           int pos=-1;
           for(int j=i+1; j<list.size();j++)
           {
                if(list.get(i)>list.get(j) && list.get(j)<min)
                {
                    min=list.get(j);
                    pos=j;
                }
           }
           if(pos!=-1)
           {
                int a=list.get(i);
                list.set(i,list.get(pos));
                list.set(pos,a);
           }
      }
    return list;
}

I'm new in Scala and functional programming so I don't know very well how to code that. can anybody help me with some ideas?

Thank you very much in advance

Upvotes: 2

Views: 1390

Answers (3)

seanmcl
seanmcl

Reputation: 9946

You can use continuation-passing-style for this.

val sort: List[Int] => List[Int] = {
  @tailrec def ins(n: Int, l: List[Int], acc: List[Int]): List[Int] = l match {
    case Nil => (n :: acc).reverse
    case x :: xs => if (n < x) acc.reverse ++ (n :: l) else ins(n, xs, x :: acc)
  }

  @tailrec def sort1[A](l: List[Int], k: List[Int] => A): A = l match {
    case Nil => k(Nil)
    case x :: xs => sort1(xs, l => k(ins(x, l, Nil)))
  }

  l => sort1(l, x => x)
}

Upvotes: 0

Bask.ws
Bask.ws

Reputation: 843

Here is immutable tailrec solution. It's not complicated, I just correctly transformed your code to immutable methods.

import annotation.tailrec

val list = List(1,4,2,7,6,9,8)

@tailrec
final def inner(min: Int, pos: Int, item: Int, i: Int, list: List[(Int, Int)]): Map[Int, Int] = list match {
  case (pItem, p) :: tail if(item > pItem &&  pItem < min) => inner(pItem, p, item, i, tail)
  case (pItem, p) :: tail => inner(min, pos, item, i, tail)
  case Nil if(pos != -1) => Map(i -> min, pos -> item)
  case Nil => Map.empty[Int, Int]
}

@tailrec
final def outer(list: List[(Int, Int)], acc: Map[Int, Int] = Map.empty[Int, Int]): Map[Int, Int] = list match {
  case (item, i) :: tail => outer(tail, acc ++ inner(100, -1, item, i, tail))
  case Nil => acc
}

def tailSort(list: List[Int]) = {
  val zipped = list.zipWithIndex
  outer(zipped, zipped.map(_.swap).toMap).toList.sortBy(_._1).map(_._2)
}

tailSort(list)

res41: List[Int] = List(1, 2, 4, 6, 7, 8, 9)

Upvotes: 0

Rado Buransky
Rado Buransky

Reputation: 3294

Here is a code which "is" in Scala even though it's the worst Scala code I have ever written. I wanted to keep it 1:1 to your code. BUT I hope it serves the purpose to demonstrate how you can write tail recursion. Nothing more, nothing less.

def sort(toSort: util.ArrayList[Int]): util.ArrayList[Int] = {
  val list = toSort

  @tailrec
  def outerLoop(i: Int) {

    if (i < list.size) {
      var min = 100
      var pos = -1

      @tailrec
      def innerLoop(j: Int) {
        if (j < list.size) {
          if (list.get(i) > list.get(j) && list.get(j) < min) {
            min = list.get(j)
            pos = j
          }

          innerLoop(j + 1)
        }
      }

      if (pos != -1) {
        val a = list.get(i)
        list.set(i, list.get(pos))
        list.set(pos, a)
      }

      outerLoop(i + 1)
    }
  }

  outerRec(0)
}

Upvotes: 2

Related Questions