Quicksort imperativo em Scala. Implementação de Kernighan/Pike em "The Practice of Programming" pgs 37-40

quicksort_imperative_scala.scala

/*

Implementação de QuickSort de Kernighan/Pike.
Adaptado para Scala, demonstrando o idioma imperativo.
Autor: Jose Fonseca (jfonseca@literati.com.br)
Projeto Literati.com.br - Letrados em TI

*/

import scala.collection.mutable.ArrayBuffer
import scala.util.Random

trait Comparador[A] {
	def compara(a1: A, a2: A): Int
}

class ComparadorDeInteiros extends Comparador[Int] {
	def compara(a1: Int, a2: Int): scala.Int = {
		val mo: scala.Int = -1
		if (a1 < a2)  mo
		else if (a1 == a2) 0
		else 1
	}
}

class ComparadorDeStrings extends Comparador[String] {
	def compara(a1: String, a2: String): Int = {
		a1.compareTo(a2)
	}
}

class ComparadorDeStringsIgnorandoMaiusculas extends Comparador[String] {
	def compara(a1: String, a2: String): Int = {
		a1.compareToIgnoreCase(a2)
	}
}


object QuicksortImperativo {

val rnd = new Random()                            

def rand(left: Int, right: Int): Int = left + Math.abs(rnd.nextInt()) % (right - left + 1)
                                                 
def troca[A](v: ArrayBuffer[A], i: Int, j: Int): Unit = {
	var tmp: A = v(i)
	v(i) = v(j)
	v(j) = tmp
}                                                 

def quicksort[A](v: ArrayBuffer[A], left: Int, right: Int, cmp: Comparador[A]): Unit = {
	var i: Int = 0
	var ultimo: Int = 0
	if (left >= right) return;
	// move o elemento pivo para v[left]
	troca(v, left, rand(left, right));
	ultimo = left
	for {i <- left + 1 to right} {
		if (cmp.compara(v(i), v(left)) < 0) {
			ultimo = ultimo + 1
			troca(v, ultimo, i)
		}
	}
	troca(v, left, ultimo)
	quicksort(v, left, ultimo - 1, cmp)
	quicksort(v, ultimo + 1, right, cmp)
}                                                 
                                                  

def main(args: Array[String]) = {
  
  val arr = ArrayBuffer[String]("Amelia","Zorro","Bethesda","Uranio","Telefone","livro","Ronaldinho")

  QuicksortImperativo.quicksort[String](arr, 0, arr.length - 1, new ComparadorDeStrings())
  println("Nomes ordenados considerando maiusculas: " + arr.mkString(", "))

  QuicksortImperativo.quicksort[String](arr, 0, arr.length - 1, new ComparadorDeStringsIgnorandoMaiusculas())
  println("Nomes ordenados ignorando maiusculas: " + arr.mkString(", "))

  val inteiros = ArrayBuffer[Int](101,34,67,11,0,99,1001,777,663,32)

  QuicksortImperativo.quicksort[Int](inteiros, 0, inteiros.length - 1, new ComparadorDeInteiros())
  println("Inteiros ordenados : " + inteiros.mkString(", "))
  
  
 }            
}