package kapitel_07 /** * Beispiel aus * * - Algorithmen und Datenstrukturen für Dummies * - von Andreas Gogol-Döring und Thomas Letschert * - Verlag Wiley-VCH; Oktober 2019 * - Kapitel 7, Sortieren * * @author A. Gogol-Döring, Th. Letschert */ object AuD_07_10_BubbleGnomeInsertionSort_App extends App { def BubbleSort[A](a: Array[A], l: Int, r: Int)(implicit ord: Ordering[A]): Unit = { var sorted = true do { sorted = true for (i <- l until r) if (ord.gt(a(i), a(i+1))) { swap(i, i+1) sorted = false } } while (!sorted) @inline def swap(i: Int, j: Int): Unit = { val t = a(i) a(i) = a(j) a(j) = t } } def GnomeSort[A](a: Array[A], l: Int, r: Int)(implicit ord: Ordering[A]): Unit = { var i = l while (i <= r) { if ((i == l) || ord.lteq(a(i-1), a(i))) { i = i + 1 } else { swap(i - 1, i) i = i - 1 } } @inline def swap(i: Int, j: Int): Unit = { val t = a(i) a(i) = a(j) a(j) = t } } def InsertionSort[A](a: Array[A], l: Int, r: Int)(implicit ord: Ordering[A]): Unit = { for (i <- l+1 to r) { val x = a(i) var j = i while (j > l && ord.gt(a(j-1), x)) { a(j) = a(j-1) j = j-1 } a(j) = x } } case class ConstrWorker(name: String, weight: Int) extends Ordered[ConstrWorker] { override def compare(o: ConstrWorker): Int = this.weight - o.weight } var a = Array( ConstrWorker("Alex", 77), ConstrWorker("Bert", 72), ConstrWorker("Claus", 96), ConstrWorker("Dominik", 111), ConstrWorker("Emil", 96), ConstrWorker("Flo", 122), ConstrWorker("Gerd", 75) ) BubbleSort(a, 0, a.length-1) println(a.mkString(", ")) a = Array( ConstrWorker("Alex", 77), ConstrWorker("Bert", 72), ConstrWorker("Claus", 96), ConstrWorker("Dominik", 111), ConstrWorker("Emil", 96), ConstrWorker("Flo", 122), ConstrWorker("Gerd", 75) ) GnomeSort(a, 0, a.length-1) println(a.mkString(", ")) a = Array( ConstrWorker("Alex", 77), ConstrWorker("Bert", 72), ConstrWorker("Claus", 96), ConstrWorker("Dominik", 111), ConstrWorker("Emil", 96), ConstrWorker("Flo", 122), ConstrWorker("Gerd", 75) ) InsertionSort(a, 0, a.length-1) println(a.mkString(", ")) }