Нерекурсивная быстрая сортировка в Scala

Question

Я пытаюсь работать с нерекурсивной версией быстрой сортировки в scala, но всякий раз, когда я пытаюсь ее реализовать, я застреваю и в итоге использую хвостовую рекурсию. Есть ли простой способ реализовать Quicksort без использования рекурсии в Scala?

Вся помощь приветствуется. Спасибо!

РЕДАКТИРОВАТЬ: рекурсивное решение было добавлено. В этом решении метод sortingHelper является хвост-рекурсивным.

def quickSortRecursive(values: Array[Int]) {
  // Swap the elements so that they aren't impacting recursion performance.
  // This swap helps the pivot get the correct position.
  def swap(i: Int, j: Int) {
    val t = values(i);
    values(i) = values(j);
    values(j) = t
  }

  // A method that takes in lower and upper bounds then sorts them.
  def sortRange(lowerBound: Int, upperBound: Int): (Int, Int) = {
    // Establish the pivot for use in sorting the bounds
    val pivot = values((lowerBound + upperBound) / 2)
    var i = lowerBound
    var j = upperBound

    // Sort the bounds using the pivot
    while (i <= j) {
      while (values(i) < pivot) {
        i += 1
      }
      while (values(j) > pivot) {
        j -= 1
      }
      if (i <= j) {
        swap(i, j)
        i += 1
        j -= 1
      }
    }

    // After the swaps, return the segments as lower and upper bounds
    (i, j)
  }

  @tailrec
  def sortingHelper(segments: List[(Int, Int)]) {
    // Take in the tuples from sortRange and sort them using tail-recursion
    segments.head match {
      case (l, r) =>
        var newSegments = segments.tail

        sortRange(l, r) match {
          case (i, j) =>
            if (l < j) {
              newSegments = (l, j) :: newSegments
            }
            if (i < r) {
              newSegments = (i, r) :: newSegments
            }
        }
        if (newSegments.nonEmpty) {
          sortingHelper(newSegments)
        }
    }
  }

  sortingHelper(List((0, values.length - 1)))
}

Answer 1

Хотя сама реализация нуждается в огромных улучшениях, и я надеюсь, что это произойдет, когда вы улучшите ее с Scala. Я буду предполагать, что все остальное идеально, и просто сконцентрируюсь на преобразовании из хвостовой рекурсии.

Чтобы преобразовать хвостовой рекурсивный код в l oop, вам просто нужно захватить условие завершения рекурсии и сделать это условие завершения l oop,

def sortingHelper2(segments: List[(Int, Int)]): Unit = {
  var newSegments = segments
  while (newSegments.nonEmpty) {
    val (l, r) = newSegments.head
    newSegments = newSegments.tail
    sortRange(l, r) match {
      case (i, j) =>
        if (l < j) {
          newSegments = (l, j) :: newSegments
        }
        if (i < r) {
          newSegments = (i, r) :: newSegments
        }
    }
  }
}

Чтобы лучше объяснить, давайте рассмотрим одну из простейших хвостовых рекурсивных функций,

def sumUpToN(n: Int): Long = {
  @tailrec
  def _sumUpToN(acc: Long, m: Int): Long = {
    if (m > 0)
      _sumUpToN(acc + m, m - 1)
    else
      acc
  }

  _sumUpToN(0, n)
}

Чтобы преобразовать ее в al oop на основе одного, вам просто нужно переместить это условие завершения / продолжения в ваше время l oop,

def sumUpToN(n: Int): Long = {
  var acc = 0
  var m = n

  while (m > 0) {
    acc = acc + m
    m = m - 1
  }

  acc
}