Come si ordina una matrice in Scala?

Question

Vedo che c'è un oggetto di ordinamento, Sorting, con un metodo quicksort, quickSort, su di esso.

Quale sarebbe un esempio di codice di utilizzo, ordinamento di una matrice di oggetto di tipo arbitrario? Sembra che ho bisogno di passare in un'implementazione del tratto Orderable, ma non sono sicuro della sintassi.

Inoltre, preferirei risposte in questo modo "Scala". So che posso usare solo una libreria Java.

Answer 1

Sorting.quickSort dichiara le funzioni per l'acquisizione di una matrice di numeri o stringhe, ma suppongo che intendi che vuoi ordinare una lista di oggetti delle tue classi?

La funzione che si Credo che stiamo guardando è

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

Il che, se sto leggendo questo diritto, significa che gli oggetti della matrice devono avere la caratteristica Ordered. Quindi la tua classe deve estendere Ordered (o deve mischiarla), e quindi deve implementare il metodo compare di quella caratteristica.

Così strappare un esempio dal libro:

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

Quindi dato un array [MyClass], quindi Sorting.quickSort dovrebbe funzionare.

Answer 2

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

L'array "predefinito" di Scala è una struttura di dati mutabile, molto vicina all'array di Java. In generale, ciò significa che un "array" non è molto Scala-ish, anche se le strutture di dati mutabili vanno. Serve comunque a uno scopo. Se l'array è il giusto tipo di dati per le tue necessità, allora è così che lo metti in ordine. A proposito, ci sono altri metodi di ordinamento sull'ordinamento degli oggetti.

Penso di aver appena capito qual è la tua domanda ... non è necessario passare alcun parametro implicito (è implicito, dopotutto). Questo parametro esiste per dire che ci deve essere un modo per convertire il tipo K in un ordinato [K]. Queste definizioni esistono già per le classi di Scala, quindi non ne hai bisogno.

per una classe arbitraria è possibile definire in questo modo:

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

Ora, se persona è stato ordinato di cominciare, questo sarebbe non essere 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)) 

Answer 3

Se si desidera solo ordinare le cose, ma in particolare non sono sposati con l'ordinamento, è possibile utilizzare il metodo di ordinamento di Elenco. Ci vuole una funzione di confronto come argomento, in modo da poter utilizzare su qualsiasi tipo vuoi:

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

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

liste probabilmente si qualificano come "più scalaish" degli array.

Dal api Scala docs:

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

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

booleano, che dovrebbe essere vera se e solo se e1 è minore di e2.

Answer 4

Mentre la risposta accettata non è errata, il metodo quicksort offre una maggiore flessibilità. Ho scritto questo esempio per te.

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

Questo dimostra come le conversioni implicite ed esplicite da Foo in una certa classe che estende ordinati [Foo] può essere utilizzato per ottenere diversi tipi di ordinamento.

Answer 5

Con Scala 2.8 o versioni successive, è possibile fare:

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

che utilizza java.util.Arrays.sort, un'implementazione di quicksort.

Answer 6

Oggi questo si lavora troppo:

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

Answer 7

preferisco utente Ordinamento util

Esempio:

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

scala.util.Sorting.quickSort(arr) 

prega di leggere questo per ulteriori informazioni Sorting util