How do I sort an array in Scala?

Question

I can see there's a Sorting object with a quickSort method on it.

Can someone provide a code example of using it, sorting an array of object of arbitrary type? It looks like I need to pass in an impl of the Orderable trait, but I am unsure of the syntax.

Also, I would prefer answers doing this the 'scala way'. I know I can just use a Java library.

Answer 1

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

Scala's "default" array is a mutable data structure, very close to Java's Array. Generally speaking, that means an "array" is not very Scala-ish, even as mutable data structures go. It serves a purpose, though. If array is the right data type for your need, then that is how you sort it. There are other sorting methods on object Sorting, by the way.

I think I just realized what your question is... you don't need to pass any implicit parameter (it's implicit, after all). That parameter exists to say that there must be some way to convert the type K into an Ordered[K]. These definitions already exist for Scala's classes, so you don't need them.

For an arbitrary class you can define it this way:

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

Now, if Person was Ordered to begin with, this wouldn't be a problem:

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 2

Sorting.quickSort declares functions for taking an Array of numbers or Strings, but I'm assuming you mean you want to sort a list of objects of your own classes?

The function I think you're looking at is

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

Which, if I'm reading this right, means that the objects in the Array must have the Ordered trait. So your class must extend Ordered (or must mix it in), and therefore must implement the compare method of that trait.

So to rip off an example from the book:

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

So given an Array[MyClass], then Sorting.quickSort should work.

Answer 3

If you just want to sort things, but aren't married to the Sorting object in particular, you can use the sort method of List. It takes a comparison function as an argument, so you can use it on whatever types you'd like:

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

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

Lists probably qualify as "more scalaish" than arrays.

From the scala api docs:

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

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

Boolean, which should be true iff e1 is smaller than e2.

Answer 4

While the accepted answer isn't wrong, the quicksort method provides more flexibility than that. I wrote this example for you.

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

This shows how implicit and explicit conversions from Foo to some class extending Ordered[Foo] can be used to get different sort orders.