Как рассчитать количество инверсий, используя сортировку слиянием для списка Int в Scala?

Question

def mergeSort(xs: List[Int]): List[Int] = {
    val n = xs.length / 2
    if (n == 0) xs
    else {
        def merge(xs: List[Int], ys: List[Int]): List[Int] =
            (xs, ys) match {
            case(Nil, ys) => ys
            case(xs, Nil) => xs
            case(x :: xs1, y :: ys1) =>
                if (x < y) {
                    x :: merge(xs1, ys)
                }
                else {
                    y :: merge(xs, ys1)
                }
            }
        val (left, right) = xs splitAt(n)
        merge(mergeSort(left), mergeSort(right))
    }
}

Число инверсий для массива указывает - как далеко (или близко) массив от сортировки.Если массив уже отсортирован, то счетчик инверсий равен 0. Если массив отсортирован в обратном порядке, то счетчик инверсий является максимальным.Формально говоря, два элемента a [i] и a [j] образуют инверсию, если a [i]> a [j] и i

Пример: последовательность 2, 4, 1, 3, 5имеет три инверсии (2, 1), (4, 1), (4, 3).

Так что, если этот список (2, 4, 1, 3, 5) передается функции, инверсияколичество должно быть 3.

Как добавить переменную, чтобы получить число?

Answer 1

Может быть что-то вроде поможет

def mergeSort(xs: List[Int], cnt: Int): (List[Int], Int) = {
  val n = xs.length / 2
  if (n == 0) (xs, cnt)
  else {
    def merge(xs: List[Int], ys: List[Int], cnt: Int): (List[Int], Int) =
      (xs, ys) match {
        case(Nil, ys) => (ys, cnt)
        case(xs, Nil) => (xs, cnt)
        case(x :: xs1, y :: ys1) =>
          if (x <= y) {
            val t = merge(xs1, ys, cnt)
            (x :: t._1, t._2)
          }
          else {
            val t = merge(xs, ys1, cnt + xs.size)
            (y :: t._1, t._2)
          }
      }
    val (left, right) = xs splitAt(n)
    val leftMergeSort = mergeSort(left, cnt)
    val rightMergeSort = mergeSort(right, cnt)
    merge(leftMergeSort._1, rightMergeSort._1, leftMergeSort._2 + rightMergeSort._2)
  }
}

Я передаю кортеж по всем вызовам функций, вот и все.

Я увеличиваю значение cnt, когда мы находим этот первый элементодного списка меньше, чем первый элемент второго списка.В этом сценарии мы добавляем list.length в cnt.Посмотрите на код, чтобы получить более четкое представление.

Надеюсь, это поможет!