package kapitel_03

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 3, Daten und ihre Struktur
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

object AuD_03_09_QuickSort_App extends App {

  def Quicksort(lst: List[Int]): List[Int] = lst match {
    case Nil => Nil
    case _ :: Nil => lst
    case first :: _ =>
      val pivot = first
      val l1 = lst.filter( _ < pivot)
      val l2 = lst.filter( _ == pivot)
      val l3 = lst.filter( _ > pivot)
      Quicksort(l1) ++ l2 ++ Quicksort(l3)
  }

  val lst = List(-1,5,7,7,3,4,-2,3,6,7,-7,9,3,8,5,-1,0,2,3,7,-4,6,5)

  println(Quicksort(lst).mkString(", "))
}