Как отсортировать массив в Scala?

Question

Я вижу, что есть сортирующий объект, Sortingс помощью метода быстрой сортировки, quickSort, в теме.

Каков пример использования кода для сортировки массива объектов произвольного типа? Похоже, мне нужно передать в реализации Orderable черта, но я не уверен в синтаксисе.

Кроме того, я бы предпочел ответы, делающие это "по пути Скала". Я знаю, что могу просто использовать библиотеку Java.

Answer 1

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

Я думаю, что вы смотрите на функцию

quickSort [K](a : Array[K])(implicit view$1 : (K) => Ordered[K]) : Unit

Что, если я правильно читаю, означает, что объекты в массиве должны иметь Ordered черта характера. Так что ваш класс должен расширяться Ordered (или должны смешать это), и, следовательно, должны реализовать compare метод этой черты.

Итак, срывайте пример с книги:

class MyClass(n: Int) extends Ordered[MyClass] {
   ...
  def compare(that: MyClass) =
    this.n - that.n
}

Таким образом, при наличии массива [MyClass], Sorting.quickSort должен работать.

Answer 2

С Scala 2.8 или новее можно сделать:

List(3,7,5,2).sortWith(_ < _)

который использует java.util.Arrays.sort, реализацию быстрой сортировки.

Answer 3

В настоящее время этот тоже работает:

List(3,7,5,2).sorted

Answer 4

Если вы просто хотите отсортировать объекты, но не состоите в браке с объектом сортировки, в частности, вы можете использовать метод сортировки List. Она принимает функцию сравнения в качестве аргумента, поэтому вы можете использовать ее для любых типов:

List("Steve", "Tom", "John", "Bob").sort((e1, e2) => (e1 compareTo e2) < 0)

List(1, 4, 3, 2).sort((e1, e2) => (e1 < e2))

Списки, вероятно, квалифицируются как "более scalaish", чем массивы.

Из документации scala api:

def sort (lt: (A, A) => Boolean): список [A]

Sort the list according to the comparison function <(e1: a, e2: a) =>

Логическое значение, которое должно быть истинным, если e1 меньше, чем e2.

Answer 5

val array = Array((for(i <- 0 to 10) yield scala.util.Random.nextInt): _*)
scala.util.Sorting.quickSort(array)

"Стандартный" массив Scala- это изменчивая структура данных, очень близкая к массиву Java. Вообще говоря, это означает, что "массив" не очень Scala-Ish, даже если изменяемые структуры данных идут. Это служит цели, хотя. Если массив является правильным типом данных для ваших нужд, то вы его и сортируете. Кстати, есть и другие методы сортировки объектов.

Я думаю, я только что понял, что ваш вопрос... вам не нужно передавать какой-либо неявный параметр (в конце концов, это неявный). Этот параметр существует, чтобы сказать, что должен быть какой-то способ преобразовать тип K в упорядоченный [K]. Эти определения уже существуют для классов Scala, поэтому они вам не нужны.

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

scala> case class Person(name: String)
defined class Person

scala> val array = Array(Person("John"), Person("Mike"), Person("Abe"))
array: Array[Person] = Array(Person(John), Person(Mike), Person(Abe))

scala> scala.util.Sorting.quickSort(array)
<console>:11: error: no implicit argument matching parameter type (Person) => Ordered[Person] was found.
       scala.util.Sorting.quickSort(array)
                                   ^
scala> class OrderedPerson(val person: Person) extends Ordered[Person] {
     | def compare(that: Person) = person.name.compare(that.name)
     | }
defined class OrderedPerson

scala> implicit def personToOrdered(p: Person) = new OrderedPerson(p)
personToOrdered: (p: Person)OrderedPerson

scala> scala.util.Sorting.quickSort(array)

scala> array
res8: Array[Person] = Array(Person(Abe), Person(John), Person(Mike))

Так вот, если бы человеку было приказано начать, это не было бы проблемой:

scala> case class Person(name: String) extends Ordered[Person] {
     | def compare(that: Person) = name.compare(that.name)
     | }
defined class Person

scala> val array = Array(Person("John"), Person("Mike"), Person("Abe"))
array: Array[Person] = Array(Person(John), Person(Mike), Person(Abe))

scala>  scala.util.Sorting.quickSort(array)

scala> array
res10: Array[Person] = Array(Person(Abe), Person(John), Person(Mike))

Answer 6

Я предпочитаю пользователя Sorting Util

Пример:

val arr = Array(7,5,1, 9,2)

scala.util.Sorting.quickSort(arr)

Пожалуйста, прочитайте это для получения дополнительной информации Утилита сортировки

Answer 7

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

import System.out.println
import scala.util.Sorting.quickSort

class Foo(x:Int) {
def get = x
}

//a wrapper around Foo that implements Ordered[Foo]
class OrdFoo(x:Foo) extends Ordered[Foo] {
def compare(that:Foo) = x.get-that.get
}
//another wrapper around Foo that implements Ordered[Foo] in a different way
class OrdFoo2(x:Foo) extends Ordered[Foo] {
def compare(that:Foo) = that.get-x.get
}
//an implicit conversion from Foo to OrdFoo
implicit def convert(a:Foo) = new OrdFoo(a)

//an array of Foos
val arr = Array(new Foo(2),new Foo(3),new Foo(1))

//sorting using OrdFoo
scala.util.Sorting.quickSort(arr)
arr foreach (a=>println(a.get))
/*
This will print:
1
2
3
*/

//sorting using OrdFoo2
scala.util.Sorting.quickSort(arr)(new OrdFoo2(_))
arr foreach (a=>println(a.get))
/*
This will print:
3
2
1
*/

Это показывает, как неявные и явные преобразования из Foo в некоторый класс, расширяющий Ordered[Foo], могут использоваться для получения различных порядков сортировки.