Comment trier un tableau en Scala ?

Question

Je peux voir qu'il y a un objet de tri, Sorting avec un quicksort méthode, quickSort sur elle.

Quel serait un exemple de code pour l'utiliser, en triant un tableau d'objets de type arbitraire ? Il semble que je doive passer dans une implémentation de la fonction Orderable mais je ne suis pas sûr de la syntaxe.

En outre, je préférerais que les réponses soient faites à la "manière Scala". Je sais que je peux simplement utiliser une bibliothèque Java.

Answer 1

Avec Scala 2.8 ou plus, c'est possible :

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

qui utilise java.util.Arrays.sort une implémentation de quicksort.

Answer 2

Aujourd'hui, celle-ci fonctionne aussi :

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

Answer 3

Sorting.quickSort déclare des fonctions pour prendre un tableau de nombres ou de chaînes de caractères, mais je suppose que vous voulez dire que vous voulez trier une liste d'objets de vos propres classes ?

Je pense que la fonction que vous cherchez est

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

Ce qui, si je lis bien, signifie que les objets du tableau doivent avoir la valeur Ordered trait. Votre classe doit donc étendre Ordered (ou doit le mélanger), et doit donc mettre en œuvre la fonction compare de ce trait.

Donc, pour reprendre un exemple du livre :

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

Donc, étant donné un tableau [MyClass], Sorting.quickSort devrait fonctionner.

Answer 4

Si vous voulez simplement trier des choses, mais que vous n'êtes pas attaché à l'objet Sorting en particulier, vous pouvez utiliser la méthode sort de List. Elle prend une fonction de comparaison en argument, ce qui vous permet de l'utiliser sur tous les types que vous souhaitez :

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

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

Les listes sont probablement plus "scalaisiennes" que les tableaux.

Depuis l'api scala docs :

def sort(lt : (A, A) => Booléen) : Liste[A]

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

Booléen, qui devrait être vrai si e1 est plus petit que e2.

Answer 5

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

Le tableau "par défaut" de Scala est une structure de données mutable, très proche du tableau de Java. D'une manière générale, cela signifie qu'un "tableau" n'est pas très Scala, même s'il s'agit de structures de données mutables. Il sert cependant un objectif. Si le tableau est le type de données qui convient à votre besoin, c'est ainsi que vous le triez. Il existe d'autres méthodes de tri sur le tri des objets, d'ailleurs.

Je pense que je viens de comprendre la nature de votre question... vous n'avez pas besoin de passer un paramètre implicite (c'est implicite, après tout). Ce paramètre existe pour dire qu'il doit y avoir un moyen de convertir le type K en un Ordered[K]. Ces définitions existent déjà pour les classes de Scala, donc vous n'en avez pas besoin.

Pour une classe arbitraire, vous pouvez la définir de cette façon :

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))

Maintenant, si la personne était ordonnée au départ, ce ne serait pas un problème :

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))