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

  case class QuickSort[A](a: Array[A])(implicit ord: Ordering[A]) {

    private val rand = scala.util.Random

    @inline private def Partition(l: Int, r: Int): Int = {
      val z = l + rand.nextInt(r - l)
      swap(z, r)
      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
    }

    private def quickSort(l: Int, r: Int): Unit = {
      if (l < r) {
        val m = Partition(l, r)
        quickSort(l, m - 1)
        quickSort(m + 1, r)
      }
    }

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

    def sort(): Unit = {
      quickSort(0, a.length - 1)
    }
  }

  val aInt = Array(13, 7, 9, 12, 3, 0, 7, 30, 2, -7, 8, 12)

  QuickSort(aInt).sort()

  println(aInt.mkString(", "))

}