0 
object BubbleSort {
  def main(args : Array[String]) : Unit = {
    bubbleSort(Array(50,33,62,21,100)) foreach println
  }
  def bubbleSort(a:Array[Int]):Array[Int]={
    for(i<- 1 to a.length-1){
      for(j <- (i-1) to 0 by -1){
        if(a(j)>a(j+1)){
          val temp=a(j+1)
          a(j+1)=a(j)
          a(j)=temp
        }
      }
    }
    a
  }
}

Scalaでバブルソートを実装していると思われる上記のコードがあります。主に与えられた数字をソートしていますが、うまく実装されたバブルソートアルゴリズムですか? また、このコード行は疑似コードで何を意味しますか: for(j <- (i-1) to 0 by -1){

理解できません。

ご協力いただきありがとうございます

4

4 に答える 4

3

少しの Scala コードが何をするかを理解する最良の方法は、REPL で実行することです。

scala> 5 to 0 by -1
res0: scala.collection.immutable.Range = Range(5, 4, 3, 2, 1, 0)

そのため、コードは(i-1)0 から逆方向にカウントされます。

より一般的にx to yは、Range from integer xto integer を作成しyます。このby部分は、このカウントを変更します。たとえば、0 to 6 by 2は「0 から 6 までを 2 ずつ数える」、または を意味しRange(0, 2, 4, 6)ます。この場合、は 1 ずつ逆算by -1する必要があることを示しています。

バブル ソートがどのように機能するかを理解するには、ウィキペディアの記事を読んで、コードが何をしているのかを理解するのに役立ててください。

于 2013-01-09T00:18:06.990 に答える
2

あなたが投稿した例は、基本的にScalaでバブルソートを行う命令的またはJavaの方法であり、悪くはありませんが、Scalaでの関数型プログラミングの目的に反しています..同じコードを以下のようにソーターで書くことができます(基本的に両方のforループを組み合わせます1行でソースの長さの範囲を実行する）

 def imperativeBubbleSort[T <% Ordered[T]](source: Array[T]): Array[T] = {
    for (i <- 0 until source.length - 1; j <- 0 until source.length - 1 - i) {
      if (source(j) > source(j + 1)) {
         val temp = source(j)
         source(j) = source(j + 1)
         source(j + 1) = temp
      }
    }
    source
   }

Scala Flavor of bubble sort can be different and simple example is below
(basically usage of Pattern matching..)

    def bubbleSort[T <% Ordered[T]](inputList: List[T]): List[T] = {
      def sort(source: List[T], result: List[T]) = {
          if (source.isEmpty) result
          else bubble(source, Nil, result)
      }


    def bubble(source: List[T], tempList: List[T], result: List[T]): List[T] = source match {
          case h1 :: h2 :: t =>
              if (h1 > h2) bubble(h1 :: t, h2 :: tempList, result)
              else bubble(h2 :: t, h1 :: tempList, result)
          case h1 :: t => sort(tempList, h1 :: result)
    }
    sort(inputList, Nil)
   }
于 2013-12-27T19:10:48.753 に答える