package kapitel_02

import scala.annotation.tailrec

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 2, Qualität von Algorithmen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */
object AuD_02_03_QuickSelect_App extends App {

  /*
   * Die Menge M im Pseudocode von QuickSelect ist nicht wörtlich als "eine Menge in der API deiner Programmiersprache"
   * zu verstehen, es ist vielmehr eine in ihrer Art nicht näher spezifizierte Kollektion an Elementen,
   * aus der einer in konstanter Zeit ausgewählt werden kann.
   * In einer Implementierung ist es besser eine Liste zu verwenden. Ein Element kann jetzt -- so wie im Algorithmus
   * angenommen -- in konstanter Zeit ausgewählt werden.
   */

  val r = scala.util.Random

  @tailrec
  def QuickSelect(M: List[Int], k: Int): Int = {
    val ri = if (M.size == 1) 0 else r.nextInt(M.size-1)
    val x: Int = M(ri)
    val M_< = M.filter( y => y < x)
    val M_> = M.filter( y => y > x)
    val count_<= = M_<.size + 1
    if (count_<= == k)
      x
    else if (k < count_<=)
      QuickSelect(M_<, k)
    else
      QuickSelect(M_>, k - count_<=)
  }

  val L = List(0,791,35,81,5,75,1,534,7,88,57,3,45,2,4)

  println(L.sorted.mkString(" "))

  val sortedByQuickselect =
    for (i <- 1 to L.size) yield QuickSelect(L, i)

  println( sortedByQuickselect.mkString(" ") )
}