Jak zmienić funkcjonalny kod wstawiania-sortowania na rekurencyjny ogon

Question

Niedawno zaimplementowałem algorytm insert_sort według funkcjonalnego stylu programowania, który staje się bardziej zwięzły i deklaratywny. Pytanie brzmi, jak zmienić go za ogon rekurencyjnej, kod rzuci wyjątek, jeśli wielkość listy dorasta do 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

właśnie wprowadził Akumulatory

@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 

::: i :+ wezmą O (n) dla domyślnej implementacji List, więc lepiej użyć bardziej odpowiedniej kolekcji (np. ListBuffer). Możesz także przepisać go na foldLeft zamiast jawnej rekursji.

Szybsze opcja (z foldLeft bez :+):

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

I wreszcie z span (jak w użytkownika @ roterl odpowiedź, ale span jest trochę szybciej - przemierza kolekcji tylko do > x występuje):

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

Aby to ogon rekurencyjne należy zdać posortowana lista jako parametr zamiast budować ją w wartości zwracanej:

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