Comment trier un tableau dans Scala?

Question

Je vois qu'il y a un objet de tri, Sorting, avec une méthode quicksort, quickSort, dessus.

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

En outre, je préférerais que l'on réponde à la «méthode Scala». Je sais que je peux juste utiliser une bibliothèque Java.

Answer 1

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

La fonction que je pense que vous regardez est

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

qui, si je lis ce droit, signifie que les objets du tableau doivent avoir le trait Ordered. Donc, votre classe doit étendre Ordered (ou doit le mélanger), et doit donc implémenter la méthode compare de ce trait.

Donc, pour arnaquer un exemple du livre:

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

donc donné un tableau [MyClass], puis Sorting.quickSort devrait fonctionner.

Answer 2

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

La matrice "par défaut" de Scala est une structure de données mutable, très proche de celle de Java. En règle générale, cela signifie qu'un "tableau" n'est pas très Scala-ish, même si les structures de données mutables vont. Cela sert un but, cependant. Si le tableau est le bon type de données pour votre besoin, alors c'est comme ça que vous le faites. Il y a d'autres méthodes de tri sur le tri des objets, d'ailleurs.

Je pense que je viens de réaliser quelle est votre question ... vous n'avez besoin de passer aucun 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 le définir ainsi:

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 a été condamnée à commencer, 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)) 

Answer 3

Si vous souhaitez simplement trier les éléments, mais que vous n'êtes pas particulièrement marié à l'objet Tri, vous pouvez utiliser la méthode de tri de List. Il faut une fonction de comparaison comme argument, vous pouvez l'utiliser sur tout type 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)) 

Listes probablement devenue « plus scalaish » que les tableaux.

De l'api scala docs:

def sort (lt: (A, A) => Boolean): Liste [A]

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

Boolean, qui devrait être vrai ssi e1 est plus petit que e2.

Answer 4

Bien que la réponse acceptée ne soit pas fausse, la méthode quicksort offre plus de flexibilité que cela. J'ai écrit cet exemple pour vous.

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 
*/ 

Cela montre comment les conversions implicites et explicites de Foo à une classe étendue Ordonné [Foo] peut être utilisé pour obtenir différents ordres de tri.

Answer 5

Avec Scala 2.8 ou plus tard, il est possible de le faire:

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

qui utilise java.util.Arrays.sort, une mise en œuvre de quicksort.

Answer 6

Aujourd'hui celui-ci fonctionne aussi:

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

Answer 7

Je préfère à l'utilisateur Tri util

Exemple:

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

scala.util.Sorting.quickSort(arr) 

s'il vous plaît lire ceci pour plus d'informations Sorting util