Как вы пишете идиоматическую функцию Scala Quicksort?

Недавно я ответил на вопрос, пытаясь написать функцию быстрой сортировки в Scala, я видел что-то вроде приведенного ниже кода.

def qsort(l: List[Int]): List[Int] = {
  l match {
    case Nil         => Nil
    case pivot::tail => qsort(tail.filter(_ < pivot)) ::: pivot :: qsort(tail.filter(_ >= pivot))
  }
}

Мой ответ получил некоторую конструктивную критику, указав, что List был плохим выбором для быстрой сортировки и, во-вторых, что вышеописанное не было хвостовой рекурсией.

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

Источник

5 ответов

Решение

Несколько лет назад я потратил некоторое время, пытаясь оптимизировать функциональную быструю сортировку, насколько мог. Вот то, что я придумал для ванили List[A]:

def qsort[A : Ordering](ls: List[A]) = {
  import Ordered._

  def sort(ls: List[A])(parent: List[A]): List[A] = {
    if (ls.size <= 1) ls ::: parent else {
      val pivot = ls.head

      val (less, equal, greater) = ls.foldLeft((List[A](), List[A](), List[A]())) {
        case ((less, equal, greater), e) => {
          if (e < pivot)
            (e :: less, equal, greater)
          else if (e == pivot)
            (less, e :: equal, greater)
          else
            (less, equal, e :: greater)
        }
      }

      sort(less)(equal ::: sort(greater)(parent))
    }
  }
  sort(ls)(Nil)
}

Я смог сделать еще лучше с обычаем List состав. Эта пользовательская структура в основном отслеживала идеальную (или почти идеальную) опорную точку для списка. Таким образом, я мог бы получить гораздо лучшую точку поворота в постоянное время, просто используя этот специальный список свойств. На практике это получилось немного лучше, чем стандартный функциональный подход выбора головы.

Как это, выше все еще довольно быстро. Это "половинный" хвост, рекурсивный (вы не можете сделать хвостовую рекурсивную быструю сортировку, не становясь действительно уродливой). Что еще более важно, он сначала перестраивается из хвостовой части, что приводит к существенно меньшему количеству промежуточных списков, чем при традиционном подходе.

Важно отметить, что это не самый элегантный или идиоматичный способ выполнения быстрой сортировки в Scala, просто он работает очень хорошо. Вероятно, у вас будет больше успеха при написании сортировки слиянием, которая обычно является гораздо более быстрым алгоритмом при реализации на функциональных языках (не говоря уже о том, что он намного чище).

Источник

Я думаю, это зависит от того, что вы подразумеваете под "идиоматическим". Основным преимуществом быстрой сортировки является очень быстрый алгоритм сортировки на месте. Так что, если вы не можете сортировать на месте, вы теряете все его преимущества - но вы все еще застряли с его преимуществами.

Итак, вот код, который я написал для Rosetta Code на эту тему. Это все еще не сортирует на месте, но, с другой стороны, это сортирует любую из новых коллекций:

import scala.collection.TraversableLike
import scala.collection.generic.CanBuildFrom
def quicksort
  [T, CC[X] <: Traversable[X] with TraversableLike[X, CC[X]]]      // My type parameters -- which are expected to be inferred
  (coll: CC[T])                                                    // My explicit parameter -- the one users will actually see
  (implicit ord: Ordering[T], cbf: CanBuildFrom[CC[T], T, CC[T]])  // My implicit parameters -- which will hopefully be implicitly available
  : CC[T] =                                                        // My return type -- which is the very same type of the collection received
  if (coll.isEmpty) {
    coll
  } else {
    val (smaller, bigger) = coll.tail partition (ord.lt(_, coll.head))
    quicksort(smaller) ++ coll.companion(coll.head) ++ quicksort(bigger)
  }
Источник

Как это случилось, я пытался решить эту проблему в последнее время. Я хотел, чтобы классический алгоритм (т. Е. Тот, который выполняет сортировку на месте) был преобразован в хвостовую рекурсивную форму.

Если вы все еще заинтересованы, вы можете увидеть мое рекомендуемое решение здесь:

Quicksort переписан в хвостовой рекурсивной форме - пример в Scala

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

Источник

Мое решение на Scala 3.

      import scala.language.postfixOps
import scala.util.Random

val randomArray: Array[Int] = (for(_ <- 1 to 1000) yield Random.nextInt(1000)).toArray
    def quickSort(inputArray: Array[Int]): Array[Int] =
        inputArray.length match
            case 0 => inputArray
            case 1 => inputArray
            case _ => Array.concat(
                quickSort(inputArray.filter(inputArray(inputArray.length / 2)
                inputArray.filter(inputArray(inputArray.length / 2) ==),
                quickSort(inputArray.filter(inputArray(inputArray.length / 2)
    print(quickSort(randomArray).mkString("Sorted array: (", ", ", ")"))
Источник

Я провел несколько экспериментов, пытаясь написать Quicksort в чисто функциональном стиле. Вот что я получил ( Quicksort.scala):

def quicksort[A <% Ordered[A]](list: List[A]): List[A] = {
  def sort(t: (List[A], A, List[A])): List[A] = t match {
    case (Nil, p, Nil) => List(p)
    case (l, p, g) =>  partitionAndSort(l) ::: (p :: partitionAndSort(g))
  }

  def partition(as: List[A]): (List[A], A, List[A]) = {
    def loop(p: A, as: List[A], l: List[A], g: List[A]): (List[A], A, List[A]) = 
      as match {
        case h :: t => if (h < p) loop(p, t, h :: l, g) else loop(p, t, l, h :: g)
        case Nil => (l, p, g)
      }

    loop(as.head, as.tail, Nil, Nil)
  }

  def partitionAndSort(as: List[A]): List[A] = 
    if (as.isEmpty) Nil
    else sort(partition(as))

  partitionAndSort(list)
}
Источник
Другие вопросы по тегам