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(", "))

}