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_04_QuickSort_App extends App {

  def QuickSort[A](a: Array[A], l: Int, r: Int)(implicit ord: Ordering[A]) : Unit = {

    def Partition(a: Array[A], l: Int, r: Int): Int = {
      val Pivot = a(r)
      var m = l
      for (i <- l until r) {
        if ( ord.lt(a(i), Pivot) ) {
          swap(i, m)
          m = m+1
        }
      }
      swap(m, r)
      m
    }

    @inline def swap(i: Int, j: Int): Unit = {
      val t = a(i)
      a(i) = a(j)
      a(j) = t
    }

    if (l < r) {
      val m = Partition(a, l, r)
      QuickSort(a, l, m-1)
      QuickSort(a, m+1, r)
    }
  }

  val aInt = Array(13, 7, 9, 12, 3, 0, 7, 30, 2, -7, 8, 12)
  QuickSort(aInt, 0, aInt.length - 1)
  println(aInt.mkString(", "))
}