Skip to content

@literatibr /quicksort_imperative_scala.scala
Last active

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Quicksort imperativo em Scala. Implementação de Kernighan/Pike em "The Practice of Programming" pgs 37-40
/*
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(", "))
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.