public
Last active

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

  • Download Gist
quicksort_imperative_scala.scala
Scala
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
/*
 
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(", "))
}
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.