Pregunta ¿Cómo ordeno una matriz en Scala?


Puedo ver que hay un objeto de clasificación, Sorting, con un ordenación rápida método, quickSort, en eso.

¿Cuál sería un ejemplo de código para usarlo, clasificando una matriz de objetos de tipo arbitrario? Parece que necesito pasar una implementación del Orderable rasgo, pero no estoy seguro de la sintaxis.

Además, preferiría que las respuestas hicieran esto de la 'manera Scala'. Sé que puedo usar una biblioteca Java.


73
2017-07-15 14:55


origen


Respuestas:


Sorting.quickSort declara funciones para tomar una matriz de números o cadenas, pero supongo que quiere decir que quiere ordenar una lista de objetos de sus propias clases.

La función que creo que estás viendo es

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

Lo cual, si estoy leyendo este derecho, significa que los objetos en la matriz deben tener el Ordered rasgo. Entonces tu clase debe extender Ordered (o debe mezclarlo), y por lo tanto debe implementar el compare método de ese rasgo

Así que para estafar un ejemplo del libro:

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

Entonces, dado un Array [MyClass], entonces Sorting.quickSort debería funcionar.


29
2017-07-15 15:04



Con Scala 2.8 o posterior, es posible hacer:

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

que usa java.util.Arrays.sort, una implementación de quicksort.


93
2017-08-23 20:23



Hoy en día este también funciona:

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


46
2017-11-30 22:08



Si solo desea ordenar cosas, pero no está casado con el objeto Sorting en particular, puede usar el método de ordenación de List. Toma una función de comparación como argumento, para que pueda usarla en los tipos que desee:

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

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

Las listas probablemente califican como "más scalaish" que las matrices.

De la scala api documentos:

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

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

Boolean, que debería ser verdadero iff e1   es más pequeño que e2.


19
2017-07-15 15:17



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

La matriz "predeterminada" de Scala es una estructura de datos mutable, muy cercana a la matriz de Java. En general, eso significa que una "matriz" no es muy Scala-ish, incluso si las estructuras de datos mutables van. Sin embargo, tiene un propósito. Si la matriz es el tipo de datos correcto para su necesidad, entonces así es como lo ordena. Por cierto, hay otros métodos de clasificación en la ordenación de objetos.

Creo que me acabo de dar cuenta de cuál es tu pregunta ... no necesitas pasar ningún parámetro implícito (está implícito, después de todo). Ese parámetro existe para decir que debe haber alguna forma de convertir el tipo K en una [K] ordenada. Estas definiciones ya existen para las clases de Scala, por lo que no las necesita.

Para una clase arbitraria, puede definirla de esta manera:

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

Ahora, si se ordenó a la persona para empezar, esto no sería un problema:

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

5
2017-07-15 15:03



Si bien la respuesta aceptada no es incorrecta, el método quicksort proporciona más flexibilidad que eso. Escribí este ejemplo para ti.

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

Esto muestra cómo las conversiones implícitas y explícitas de Foo a algunas clases que se extienden Ordenadas [Foo] se pueden usar para obtener diferentes órdenes de clasificación.


3
2017-07-23 14:52



Prefiero el usuario Ordenando util 

Ejemplo:

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

scala.util.Sorting.quickSort(arr)

por favor lea esto para más información Ordenando util


1
2017-12-19 23:38