Сортировка выбора Общий тип реализации

Question

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

У кого-нибудь есть ссылка, код или учебное пособие о том, как это сделать, пожалуйста Я пытаюсь изменить этот конкретный код

  'def main (args:Array[String]){
    val l = List(2,4,5,6,8)
    print(quickSort(l))
  }
  def quickSort(x:List[Int]):List[Int]={
    x match{
      case xh::xt =>
        {
        val (first,pivot,second) = partition(x)
        quickSort (first):::(pivot :: quickSort(second))
    }
    case Nil => {x}
  }
  }
  def partition (x:List[Int])=
  {
   val pivot =x.head
   var first:List[Int]=List ()
   var second : List[Int]=List ()

   val fun=(i:Int)=> {
     if (i<pivot)
       first=i::first
      else
         second=i::second
   } 
     x.tail.foreach(fun)
     (first,pivot,second)
   }


    enter code here

    def main (args:Array[String]){
    val l = List(2,4,5,6,8)
    print(quickSort(l))
  }
  def quickSort(x:List[Int]):List[Int]={
    x match{
      case xh::xt =>
        {
        val (first,pivot,second) = partition(x)
        quickSort (first):::(pivot :: quickSort(second))
    }
    case Nil => {x}
  }
  }
  def partition (x:List[Int])=
  {
   val pivot =x.head
   var first:List[Int]=List ()
   var second : List[Int]=List ()

   val fun=(i:Int)=> {
     if (i<pivot)
       first=i::first
      else
         second=i::second
   } 
     x.tail.foreach(fun)
     (first,pivot,second)
   } '

Язык: СКАЛА

Answer 1

В Scala Java Comparator заменяется на Ordering (довольно похоже, но поставляется с более полезными методами).Они реализованы для нескольких типов (примитивы, строки, bigDecimals и т. Д.), И вы можете предоставить свои собственные реализации.

Затем вы можете использовать scala implicit, чтобы попросить компилятор выбрать правильный для вас:

def sort[A]( lst: List[A] )( implicit ord: Ordering[A] ) = {
  ...
}

Если вы используете предопределенный порядок, просто позвоните:

sort( myLst )

и компилятор выведет второй аргумент.Если вы хотите объявить свой собственный порядок, используйте ключевое слово implicit в объявлении.Например:

implicit val fooOrdering = new Ordering[Foo] {
  def compare( f1: Foo, f2: Foo ) = {...}
}

, и он будет неявно использоваться, если вы попытаетесь отсортировать список Foo.

Если у вас есть несколько реализаций для одного типа, вы также можете явно передать правильный объект заказа:

sort( myFooLst )( fooOrdering )

Подробнее в этом сообщении .

Answer 2

Для быстрой сортировки я изменю пример из книги " Scala By Example ", чтобы сделать его более общим.

class Quicksort[A <% Ordered[A]] {
    def sort(a:ArraySeq[A]): ArraySeq[A] =
        if (a.length < 2) a
        else {
            val pivot = a(a.length / 2)
            sort (a filter (pivot >)) ++ (a filter (pivot == )) ++
                sort (a filter(pivot <))
        }
}

Тест с Int

    scala> val quicksort = new Quicksort[Int]
    quicksort: Quicksort[Int] = Quicksort@38ceb62f

    scala> val a = ArraySeq(5, 3, 2, 2, 1, 1, 9, 39 ,219)
    a: scala.collection.mutable.ArraySeq[Int] = ArraySeq(5, 3, 2, 2, 1, 1, 9, 39, 21
    9)

    scala> quicksort.sort(a).foreach(n=> (print(n), print (" " )))
    1 1 2 2 3 5 9 39 219

Тест с пользовательским классом, реализующим Ordered

scala> case class Meh(x: Int, y:Int) extends Ordered[Meh] {
     | def compare(that: Meh) = (x + y).compare(that.x + that.y)
     | }
defined class Meh

scala> val q2 = new Quicksort[Meh]
q2: Quicksort[Meh] = Quicksort@7677ce29

scala> val a3 = ArraySeq(Meh(1,1), Meh(12,1), Meh(0,1), Meh(2,2))
a3: scala.collection.mutable.ArraySeq[Meh] = ArraySeq(Meh(1,1), Meh(12,1), Meh(0
,1), Meh(2,2))

scala> q2.sort(a3)
res7: scala.collection.mutable.ArraySeq[Meh] = ArraySeq(Meh(0,1), Meh(1,1), Meh(
2,2), Meh(12,1))

Answer 3

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

Вот мое решение:

package bitspoke.algo

import scala.math.Ordered
import scala.collection.mutable.Buffer

abstract class Sorter[T <% Ordered[T]] {

  // algorithm provided by subclasses
  def sort(buffer : Buffer[T]) : Unit

  // check if the buffer is sorted
  def sorted(buffer : Buffer[T]) = buffer.isEmpty || buffer.view.zip(buffer.tail).forall { t => t._2 > t._1 }

  // swap elements in buffer
  def swap(buffer : Buffer[T], i:Int, j:Int) {
    val temp = buffer(i)
    buffer(i) = buffer(j)
    buffer(j) = temp
  }
}


class SelectionSorter[T <% Ordered[T]] extends Sorter[T] {
  def sort(buffer : Buffer[T]) : Unit = {
    for (i <- 0 until buffer.length) {
      var min = i
      for (j <- i until buffer.length) {
        if (buffer(j) < buffer(min))
          min = j
       }
       swap(buffer, i, min)
     }
  }
}

Как видите, вместо использования java.lang.Comparable я предпочел scala.math.Ordered и Scala View Bounds, а не Upper Bounds. Это, безусловно, работает благодаря многим неявным преобразованиям Scala примитивных типов в Rich Wrappers.

Вы можете написать клиентскую программу следующим образом:

import bitspoke.algo._
import scala.collection.mutable._

val sorter = new SelectionSorter[Int]
val buffer = ArrayBuffer(3, 0, 4, 2, 1)
sorter.sort(buffer)

assert(sorter.sorted(buffer))