So ändern Sie die funktionale Einfügung-Sortiercode, um tail rekursiv zu sein

Question

Kürzlich implementiere ich den insert_sort-Algorithmus nach funktionalen Programmierstil, und es wird prägnanter und deklarativer. die Frage ist, wie man es ändern Schwanz rekursiv zu sein, wird der Code Ausnahme auslösen, wenn die Größe der Liste bis zu 10000.

def InsertSort(xs: List[Int]): List[Int] = xs match { 
    case Nil => Nil 
    case x::rest => 
     def insert (x: Int, sorted_xs:List[Int]) :List[Int] = sorted_xs match{ 
      case Nil => List(x) 
      case y::ys => if (x <= y) x::y::ys else y::insert(x,ys) 
     } 
     insert(x,InsertSort(rest)) 
} 

Answer 1

gerade eingeführten Akkumulatoren wächst:

@tailrec def InsertSort(xs: List[Int], acc: List[Int] = Nil): List[Int] = 
    if (xs.nonEmpty) { 
    val x :: rest = xs 
    @tailrec 
    def insert(x: Int, sorted_xs: List[Int], acc: List[Int] = Nil): List[Int] = 
     if (sorted_xs.nonEmpty) { 
     val y :: ys = sorted_xs 
     if (x <= y) acc ::: x :: y :: ys else insert(x,ys, acc :+ y) 
     } else acc ::: List(x) 
    InsertSort(rest, insert(x, acc)) 
    } else acc 

::: und :+ nehmen O (n) für die Standard-Implementierung List, so ist es besser, eine geeignetere Sammlung zu verwenden (wie ListBuffer). Sie können es auch mit foldLeft anstelle von expliziter Rekursion umschreiben.

Schnellere Option (mit foldLeft, ohne :+):

@tailrec 
def insert(sorted_xs: List[Int], x: Int, acc: List[Int] = Nil): List[Int] = 
    if (sorted_xs.nonEmpty) { 
    val y::ys = sorted_xs 
    if (x <= y) acc.reverse ::: x :: y :: ys else insert(ys, x, y :: acc) 
    } else (x :: acc).reverse 

scala> List(1,5,3,6,9,6,7).foldLeft(List[Int]())(insert(_, _)) 
res22: List[Int] = List(1, 3, 5, 6, 6, 7, 9) 

Und schließlich mit span (wie in @ roterl Antwort, aber span ist ein wenig schneller - es durchläuft Sammlung nur bis > x gefunden wird):

def insert(sorted_xs: List[Int], x: Int) = if (sorted_xs.nonEmpty) { 
    val (smaller, larger) = sorted_xs.span(_ < x) 
    smaller ::: x :: larger 
} else x :: Nil 

scala> List(1,5,3,6,9,6,7).foldLeft(List[Int]())(insert) 
res25: List[Int] = List(1, 3, 5, 6, 6, 7, 9) 

Answer 2

Um es Schwanz rekursive machen Sie das sortierte Liste als Parameter bei dem Rückgabewert es statt bauen passieren sollen:

def InsertSort(xs: List[Int]): List[Int] = { 
    @tailrec 
    def doSort(unsortXs: List[Int], sorted_xs: List[Int]): List[Int] = { 
    unsortXs match { 
     case Nil => sorted_xs 
     case x::rest => 
     val (smaller, larger) = sorted_xs.partition(_ < x) 
     doSort(rest, smaller ::: x :: larger) 
    } 
    } 
    doSort(xs, List()) 
}