Unione di due sequenze in scala in modo ordinato

Question

Sto cercando di unire due sequenze in modo tale che essi rimangono ordinati. Quanto segue è il codice che ho scritto:

val seq1 = Seq(1,3,5,7,9) 
    val seq2 = Seq(2,4,6,8) 
    var arr = Seq[Int]() 
    for(b <- seq2) 
    { 
    for(a <- seq1) 
    { 
     if(a < b) 
     arr = arr :+ a 
     else 
     { 
     arr = arr :+ b;break; 
     } 
    } 
    } 
    println(arr) 

l'output che ho bisogno deve essere:

Seq(1,2,3,4,5,6,7,8,9)  

Ma sembra pausa non funziona a Scala. Sono relativamente nuovo alla lingua. Quale sarebbe il modo migliore per eseguire questa operazione?

Answer 1

Il modo più semplice sarebbe probabilmente questo:

(seq1 ++ seq2).sorted 

Se seq1 e seq2 contengono qualche altro tipo, si dovrà fornire una Ordering per quel tipo; o, in alternativa, utilizzare il metodo sortBy, mappatura ciascun elemento ad un elemento di un altro tipo per il quale un Ordering può implicitamente essere trovato:

(seq1 ++ seq2).sortBy(_.toDate) 

Answer 2

per interlacciare due sequenze pur mantenendo la loro ordinamento individuale, si può utilizzare:

scala> seq1.zip(seq2).flatMap(pair => Seq(pair._1,pair._2)) 
res1: Seq[Int] = List(1, 2, 3, 4, 5, 6, 7, 8) 

Si noti, tuttavia, che per le sequenze di lunghezza diversa questo perde gli elementi aggiuntivi della sequenza più lunga. Questo può essere risolto con un po 'più di sforzo (trovare il più lungo dei due elenchi e aggiungere longer.drop(shorter.length)).

Answer 3

Di seguito funziona anche per le sequenze non interlacciati:

def mergeSorted[E: Ordering](x: Seq[E], y: Seq[E]): Seq[E] = { 
    val ordering = implicitly[Ordering[E]] 
    @tailrec 
    def rec(x: Seq[E], y: Seq[E], acc: Seq[E]): Seq[E] = { 
    (x, y) match { 
     case (Nil, Nil) => acc 
     case (_, Nil) => acC++ x 
     case (Nil, _) => acC++ y 
     case (xh :: xt, yh :: yt) => 
     if (ordering.lteq(xh, yh)) 
      rec(xt, y, acc :+ xh) 
     else 
      rec(x, yt, acc :+ yh) 
    } 
    } 
    rec(x, y, Seq()) 
} 

prega di notare che per motivi di prestazioni probabilmente usereste Builders (vs.: +, + :, inverso).

Answer 4

sono stato felice di trovare @ soluzione CaringDev e di adattare in modo da utilizzare un Builder:

def mergeSortedBuilder[E: Ordering](x: Seq[E], y: Seq[E])(implicit ordering: Ordering[E]): Seq[E] = { 
    @tailrec 
    def rec(x: Seq[E], y: Seq[E], acc: Builder[E, Seq[E]]): Builder[E, Seq[E]] = { 
    (x, y) match { 
    case (Nil, Nil) => acc 
    case (_, Nil) => acC++= x 
    case (Nil, _) => acC++= y 
    case (xh :: xt, yh :: yt) => 
     if (ordering.lteq(xh, yh)) 
     rec(xt, y, acc += xh) 
     else 
     rec(x, yt, acc += yh) 
    } 
} 
rec(x, y, Seq.newBuilder).result 
}