Recursive sorting in Scala including an exit condition

Question

I am attempting to sort a List of names using Scala, and I am trying to learn how to do this recursively. The List is a List of Lists, with the "element" list containing two items (lastName, firstName). My goal is to understand how to use recursion to sort the names. For the purpose of this post my goal is just to sort by the length of lastName.

If I call my function several times on a small sample list, it will successfully sort lastName by length from shortest to longest, but I have not been able to construct a satisfactory exit condition using recursion. I have tried variations of foreach and other loops, but I have been unsuccessful. Without a satisfactory exit condition, the recursion just continues forever.

  import scala.collection.mutable.ListBuffer 
  import scala.annotation.tailrec
  val nameListBuffer = new ListBuffer[List[String]]
  val source = Source.fromFile("shortnames.txt")
  val lines = source.getLines()
  for (line <- lines) {
    nameListBuffer += line.split(" ").reverse.toList
  } 

  @tailrec
  def sorting(x: ListBuffer[List[String]]): Unit = {
    for (i <- 0 until ((x.length)-1)) {
      var temp = x(i)
       if (x(i)(0).length > x(i+1)(0).length) {
        x(i) = x(i+1)
        x(i+1) = temp
       }
    }
    var continue = false
    while (continue == false) {
      for (i <- 0 until ((x.length)-1)) {
        if (x(i)(0).length <= x(i+1)(0).length) {
          continue == false//want to check ALL i's before evaluating
        }
        else continue == true
      }
    }
    sorting(x)
  }
sorting(nameListBuffer)

Answer 1

Sorry about the runtime complexity it's basically an inefficient bubble sort at O(n^4) but the exit criteria - focus on that. For tail recursion, the key is that the recursive call is to a smaller element than the preceding recursive call. Also, keep two arguments, one is the original list, and one is the list that you are accumulating (or whatever you want to return, it doesn't have to be a list). The recursive call keeps getting smaller until eventually you can return what you have accumulated. Use pattern matching to catch when the recursion has ended, and then you return what you were accumulating. This is why Lists are so popular in Scala, because of the Nil and Cons subtypes and because of operators like the :: can be handled nicely with pattern matching. One more thing, to be tail recursive, the last case has to make a recursive or it won't run.

 import scala.collection.mutable.ListBuffer 
 import scala.annotation.tailrec

  // I did not ingest from file I just created the test  list from some literals
  val dummyNameList = List(
    List("Johanson", "John"), List("Nim", "Bryan"), List("Mack", "Craig")
    , List("Youngs", "Daniel"), List("Williamson", "Zion"), List("Rodgersdorf", "Aaron"))

  // You can use this code to populate nameList though I didn't run this code
  val source = Source.fromFile("shortnames.txt")
  val lines = source.getLines()
  val nameList = { 
    for (line <- lines) yield line.split(" ").reverse.toList
  }.toList

  println("\nsorted:")
  sortedNameList.foreach(println(_))

  //This take one element and it will return the lowest element from the list
  //of the other argument.  
  @tailrec
  private def swapElem(elem: List[String], listOfLists: List[List[String]]): List[String] = listOfLists match {
     case Nil => elem 
     case h::t if (elem(0).length > h(0).length) => swapElem(h, t)
     case h::t => swapElem(elem, t)
    }

  //If the head is not the smallest element, then swap out the element 
  //with the smallest element of the list. I probably could have returned
  // a tuple it might have looked nicer. It just keeps iterating though until
  // there is no elements 
  @tailrec
  private def iterate(listOfLists: List[List[String]], acc: List[List[String]]): List[List[String]] = listOfLists match {
     case h::Nil => acc :+ h
     case h::t if (swapElem(h, t) != h) => iterate(h :: t.filterNot(_ == swapElem(h, t)), acc :+ swapElem(h, t))
     case h::t => iterate(t, acc :+ swapElem(h, t))
    }


val sortedNameList = iterate(nameList, List.empty[List[String]])

println("\nsorted:")
sortedNameList.foreach(println(_))

sorted:

List(Nim, Bryan) 
List(Mack, Craig)
List(Youngs, Daniel)
List(Johanson, John)
List(Williamson, Zion)
List(Rodgersdorf, Aaron)