Selection Sort Generic type implementation

I worked my way implementing a recursive version of selection and quick sort,i am trying to modify the code in a way that it can sort a list of any generic type , i want to assume that the generic type supplied can be converted to Comparable at runtime.

Does anyone have a link ,code or tutorial on how to do this please I am trying to modify this particular code

  'def main (args:Array[String]){
    val l = List(2,4,5,6,8)
    print(quickSort(l))
  }
  def quickSort(x:List[Int]):List[Int]={
    x match{
      case xh::xt =>
        {
        val (first,pivot,second) = partition(x)
        quickSort (first):::(pivot :: quickSort(second))
    }
    case Nil => {x}
  }
  }
  def partition (x:List[Int])=
  {
   val pivot =x.head
   var first:List[Int]=List ()
   var second : List[Int]=List ()

   val fun=(i:Int)=> {
     if (i<pivot)
       first=i::first
      else
         second=i::second
   } 
     x.tail.foreach(fun)
     (first,pivot,second)
   }


    enter code here

    def main (args:Array[String]){
    val l = List(2,4,5,6,8)
    print(quickSort(l))
  }
  def quickSort(x:List[Int]):List[Int]={
    x match{
      case xh::xt =>
        {
        val (first,pivot,second) = partition(x)
        quickSort (first):::(pivot :: quickSort(second))
    }
    case Nil => {x}
  }
  }
  def partition (x:List[Int])=
  {
   val pivot =x.head
   var f开发者_如何学运维irst:List[Int]=List ()
   var second : List[Int]=List ()

   val fun=(i:Int)=> {
     if (i<pivot)
       first=i::first
      else
         second=i::second
   } 
     x.tail.foreach(fun)
     (first,pivot,second)
   } '

Language: SCALA

In Scala, Java Comparator is replaced by Ordering (quite similar but comes with more useful methods). They are implemented for several types (primitives, strings, bigDecimals, etc.) and you can provide your own implementations.

You can then use scala implicit to ask the compiler to pick the correct one for you:

def sort[A]( lst: List[A] )( implicit ord: Ordering[A] ) = {
  ...
}

If you are using a predefined ordering, just call:

sort( myLst )

and the compiler will infer the second argument. If you want to declare your own ordering, use the keyword implicit in the declaration. For instance:

implicit val fooOrdering = new Ordering[Foo] {
  def compare( f1: Foo, f2: Foo ) = {...}
}

and it will be implicitly use if you try to sort a List of Foo.

If you have several implementations for the same type, you can also explicitly pass the correct ordering object:

sort( myFooLst )( fooOrdering )

More info in this post.

For Quicksort, I'll modify an example from the "Scala By Example" book to make it more generic.

class Quicksort[A <% Ordered[A]] {
    def sort(a:ArraySeq[A]): ArraySeq[A] =
        if (a.length < 2) a
        else {
            val pivot = a(a.length / 2)
            sort (a filter (pivot >)) ++ (a filter (pivot == )) ++
                sort (a filter(pivot <))
        }
}

Test with Int

    scala> val quicksort = new Quicksort[Int]
    quicksort: Quicksort[Int] = Quicksort@38ceb62f

    scala> val a = ArraySeq(5, 3, 2, 2, 1, 1, 9, 39 ,219)
    a: scala.collection.mutable.ArraySeq[Int] = ArraySeq(5, 3, 2, 2, 1, 1, 9, 39, 21
    9)

    scala> quicksort.sort(a).foreach(n=> (print(n), print (" " )))
    1 1 2 2 3 5 9 39 219

Test with a custom class implementing Ordered

scala> case class Meh(x: Int, y:Int) extends Ordered[Meh] {
     | def compare(that: Meh) = (x + y).compare(that.x + that.y)
     | }
defined class Meh

scala> val q2 = new Quicksort[Meh]
q2: Quicksort[Meh] = Quicksort@7677ce29

scala> val a3 = ArraySeq(Meh(1,1), Meh(12,1), Meh(0,1), Meh(2,2))
a3: scala.collection.mutable.ArraySeq[Meh] = ArraySeq(Meh(1,1), Meh(12,1), Meh(0
,1), Meh(2,2))

scala> q2.sort(a3)
res7: scala.collection.mutable.ArraySeq[Meh] = ArraySeq(Meh(0,1), Meh(1,1), Meh(
2,2), Meh(12,1))

Even though, when coding Scala, I'm used to prefer functional programming style (via combinators or recursion) over imperative style (via variables and iterations), THIS TIME, for this specific problem, old school imperative nested loops result in simpler code for the reader. I don't think falling back to imperative style is a mistake for certain classes of problems (such as sorting algorithms which usually transform the input buffer (like a procedure) rather than resulting to a new sorted one

Here it is my solution:

package bitspoke.algo

import scala.math.Ordered
import scala.collection.mutable.Buffer

abstract class Sorter[T <% Ordered[T]] {

  // algorithm provided by subclasses
  def sort(buffer : Buffer[T]) : Unit

  // check if the buffer is sorted
  def sorted(buffer : Buffer[T]) = buffer.isEmpty || buffer.view.zip(buffer.tail).forall { t => t._2 > t._1 }

  // swap elements in buffer
  def swap(buffer : Buffer[T], i:Int, j:Int) {
    val temp = buffer(i)
    buffer(i) = buffer(j)
    buffer(j) = temp
  }
}


class SelectionSorter[T <% Ordered[T]] extends Sorter[T] {
  def sort(buffer : Buffer[T]) : Unit = {
    for (i <- 0 until buffer.length) {
      var min = i
      for (j <- i until buffer.length) {
        if (buffer(j) < buffer(min))
          min = j
       }
       swap(buffer, i, min)
     }
  }
}

As you can see, rather than using java.lang.Comparable, I preferred scala.math.Ordered and Scala View Bounds rather than Upper Bounds. That's certainly works thanks to many Scala Implicit Conversions of primitive types to Rich Wrappers.

You can write a client program as follows:

import bitspoke.algo._
import scala.collection.mutable._

val sorter = new SelectionSorter[Int]
val buffer = ArrayBuffer(3, 0, 4, 2, 1)
sorter.sort(buffer)

assert(sorter.sorted(buffer))