私は Scala を試しています。次の要件で scala に挿入ソートを実装する方法を確認したいと思います。
これが挿入ソートを実装する Scala の方法ではない場合でも、上記のコードを提供し、アプローチの何が問題なのかを説明できます。編集: これは while ループを使用した試みです (動作します)。いいえ、それは宿題の質問ではありません。なぜ敵意があるのですか?
def insert_sort(a:Array[Int]):Array[Int]={
for(i <- 0 until a.length)
{
var j=i+1
while(j>1&&a(j)<a(j-1)&&j<a.length)
{
var c=a(j)
a(j)=a(j-1)
a(j-1)=c
j-=1
}
}
return a
}
これは私が思いついたもので、機能的で、一般的で、末尾再帰的 (foldLeft末尾再帰的です) のようです...:
def insertionSort[A](la: List[A])(implicit ord: Ordering[A]): List[A] = {
def insert(la: List[A], a: A) = {
val (h, t) = la.span(ord.lt(_, a))
h ::: (a :: t)
}
la.foldLeft(List[A]()) {(acc, a) => insert(acc, a)}
}
挿入ソートの別の一般的なバージョンを次に示します。
def less[T <: Comparable[T]](i: T, j: T) = i.compareTo(j) < 0
def swap[T](xs: Array[T], i: Int, j: Int) { val tmp = xs(i); xs(i) = xs(j); xs(j) = tmp }
def insertSort[T <: Comparable[T]](xs: Array[T]) {
for { i <- 1 to xs.size
j <- List.range(1, i).reverse
if less(xs(j),xs(j - 1)) } swap(xs, j, j -1)
}
ネストされた for ループは、問題が何であれ、おそらく Scala の答えではありません。これらは、for ループが「条件まで繰り返し、反復ごとにこれを変更する」ことを表す言語では意味があります。これは、 Scala の for ループまたは for 内包表記とは異なります (for 内包表記は、反復ごとに何かを生成する for ループです)。
Scala では、for ループと for 内包表記はコレクションの要素 (または非コレクション モナドの場合はもっと奇妙なこと) の反復ですが、挿入ソートの場合は、その位置まで場所を交換するか、要素を挿入するかのいずれかで位置を見つけたいと考えています。その位置で。for ループや for 内包表記を使用して検索を行うべきではありません。
また、Scala には参照渡しはありません。そして、実際にArrayは、Scala コレクションでさえありませんが、JVM によってクラスで再現できない固有の特性を持つ Java のものであるため、置き換えることはできません。
何のために必要ですか？
ソートされた配列が必要な場合は、次をお勧めしますdef sortArray(a: Array[Int]): Array[Int] = a.sortWith(_ < _)。
以下は、foldLeft を使用して記述されたコード サンプルです。
def insertionSort(input: List[Int]): List[Int] = {
input.foldLeft(List[Int]())( (acc, element) => {
val (firstHalf, secondHalf) = acc.span(_ < element)
//inserting the element at the right place
firstHalf ::: element :: secondHalf
})
}
この例は、このgithubリポジトリにあります。
最初に、次を追加することを忘れないでください。
import scala.util.control.Breaks._
これは、リストを入力として使用する私のソリューションです
def insertionSortLoop(list :List[Int]) : List[Int] = {
val intArray: Array[Int] = list.toArray
for ( j <- 1 until intArray.length ) {
breakable {
for ( i <- (1 to j).reverse ) {
if (intArray(i-1) < intArray(i)) {
break
} else {
val temp = intArray(i)
intArray(i) = intArray(i-1)
intArray(i-1) = temp
}
}
}
}
intArray.toList
}
ここgithubに実装があります。
ウィキペディアの記事に記載されている実装は、あなたの法案に適合しています。これをコピーして貼り付け、Scala 構文に変換します。
def insertionSort(a: Array[Int]): Array[Int] = {
for (i <- 1 until a.length) {
// A[ i ] is added in the sorted sequence A[0, .. i-1]
// save A[i] to make a hole at index iHole
val item = a(i)
var iHole = i
// keep moving the hole to next smaller index until A[iHole - 1] is <= item
while (iHole > 0 && a(iHole - 1) > item) {
// move hole to next smaller index
a(iHole) = a(iHole - 1)
iHole = iHole - 1
}
// put item in the hole
a(iHole) = item
}
a
}
挿入ソートの不変の実装が必要な場合、adijoと@RB_の答えはほとんど正しいです。
ただし、これらの実装では、約 50.000 エントリを超えるリストの場合、StackOverflow エラーでスタックが爆発します。これは、そこで使用されている再帰メソッドが @tailrec ではないためです。
考えられる解決策の 1 つは、次のように、 CPSを使用してメソッド tailrec を作成することです。
object Sort {
def apply[A: Ordering](list: List[A]): List[A] = {
@tailrec
// In order to make this code tailrec, we are using CPS (continuation passing style)
def insert(entry: A, list: List[A])(k: List[A] => List[A]): List[A] =
list match {
case Nil => k(List(entry))
case head :: _ if entry < head => k(entry :: list)
case head :: tail => insert(entry, tail)(r => k(head :: r))
}
@tailrec
def inner(sorted: List[A], rest: List[A]): List[A] =
rest match {
case Nil => sorted
case head :: tail => inner(insert(head, sorted)(identity), tail)
}
inner(Nil, list)
}
}
不変の実装は常に可変の実装よりも遅くなることに注意してください。