Recursive sort in scala with tail recursion

Question

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

Rado Buransky · Accepted Answer · 2014-01-14 06:46:26Z

2

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)
}

edited Jan 14, 2014 at 6:46

answered Jan 14, 2014 at 6:38

Rado Buransky

3,29420 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Rodrigo Cifuentes Gómez Over a year ago

Thank you for your answer, you were right about my compilation errors. Your answer is good but actually I'm looking for an immutable solution . Thank you again sir.

Rado Buransky Over a year ago

I thought so. Scala sorting goes like this: val list = List(3, 2, 1).sorted

Rado Buransky Over a year ago

Scala immutable List is implemented as a linked list which is a different data structure than java ArrayList and therefore different sorting algorithms are used.

Bask.ws · Accepted Answer · 2014-01-14 09:08:28Z

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)

seanmcl · Accepted Answer · 2019-05-06 19:55:11Z

0

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)
}

answered May 6, 2019 at 19:55

seanmcl

9,9793 gold badges42 silver badges47 bronze badges

Collectives™ on Stack Overflow

Recursive sort in scala with tail recursion

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related