Может ли кто-нибудь объяснить следующий код Scala? - PullRequest
Новая
       105

Может ли кто-нибудь объяснить следующий код Scala?

0 голосов
/ 07 мая 2020

Я должен описать BubbleSort в Scala, и я тестировал его с помощью этого кода. Но я точно не знаю, что делает каждая из функций. 

object BubbleSort {
  def sort(list: List[Int]): List[Int] = list match {
    case List() => List()
    case head :: tail => compute(head, sort(tail))
  }

  def compute(data: Int, dataSet: List[Int]): List[Int] = dataSet match {
    case List() => List(data)
    case head :: tail => if (data <= head) data :: dataSet else head :: compute(data, tail)
  }

  def main(args: Array[String]) {
    val list = List(3, 12, 43, 23, 7, 1, 2, 0)
    println(sort(list))
  }
}

Кто-нибудь может мне это объяснить?

Ответы [ 2 ]

2 голосов
/ 07 мая 2020

Посмотрите, как работают ваши функции, начиная с последнего элемента 

sort(List()) // List()
compute(0, List()) // List(0)
sort(List(0))      // List(0)
compute(2, List(0)) // List(0, 2)
sort(List(2, 0))    // List(0, 2)
compute(1, List(0, 2)) // List(0, 1, 2)
sort(List(1, 0, 2))    // List(0, 1, 2)
compute(7, List(0, 1, 2)) // List(0, 1, 2, 7)
sort(List(7, 0, 1, 2))    // List(0, 1, 2, 7)
compute(23, List(0, 1, 2, 7)) // List(0, 1, 2, 7, 23)
sort(List(23, 0, 1, 2, 7))    // List(0, 1, 2, 7, 23)
compute(43, List(0, 1, 2, 7, 23)) // List(0, 1, 2, 7, 23, 43)
sort(List(43, 0, 1, 2, 7, 23))    // List(0, 1, 2, 7, 23, 43)
compute(12, List(0, 1, 2, 7, 23, 43)) // List(0, 1, 2, 7, 12, 23, 43)
sort(List(12, 0, 1, 2, 7, 23, 43))    // List(0, 1, 2, 7, 12, 23, 43)
compute(3, List(0, 1, 2, 7, 12, 23, 43)) // List(0, 1, 2, 3, 7, 12, 23, 43)
sort(List(3, 0, 1, 2, 7, 12, 23, 43))    // List(0, 1, 2, 3, 7, 12, 23, 43)

compute подталкивает элемент («пузырь») до нужного места.

1 голос
/ 07 мая 2020

Во-первых, classi c определение пузырьковой сортировки включает замену соседних элементов, если они вышли из строя. Здесь не происходит подкачки, поэтому на самом деле это не похоже на настоящую пузырьковую сортировку.

Метод compute() правильнее называть insert(), потому что это то, что он делает. Он вставляет элемент data в уже отсортированный dataSet. Тривиальный случай - это когда элемент data находится во главе (или только в элементе) dataSet. Если это не так, тогда он откладывает заголовок текущего dataSet в сторону (в стеке вызовов) и выполняет рекурсию до тех пор, пока data не может быть помещено в начало, тогда стек вызовов разматывается. , перестроение dataSet с использованием последнего элемента data.

Метод sort() немного проще. Он просто отрывает голову от текущего list и помещает его в стек вызовов до тех пор, пока list не станет пустым, и, таким образом, не будет отсортирован. Затем он разворачивается, передавая каждый элемент compute() вместе с отсортированным результатом, возвращенным из предыдущего вызова.

...