package kapitel_04

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 4, Listen: Immer einer nach dem anderen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

import scala.collection.immutable.ArraySeq

object AuD_04_04_QuickSortFunctional_App extends App {

  def Quicksorta(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)
      Quicksorta(l1) ++ l2 ++ Quicksorta(l3)
  }

  def Quicksortb(seq: Seq[Int]): Seq[Int] =
    if (seq.length <= 1) seq
    else {
      val pivot = seq(0)
      val l1 = seq.filter( _ < pivot)
      val l2 = seq.filter( _ == pivot)
      val l3 = seq.filter( _ > pivot)
      Quicksortb(l1) ++ l2 ++ Quicksortb(l3)
    }

  def Quicksort(seq: Seq[Int]): Seq[Int] =
    if (seq.length <= 1) seq
    else {
      val pivot = seq(0)
      val l1 = for (x <- seq; if x < pivot) yield x
      val l2 = for (x <- seq; if x == pivot) yield x
      val l3 = for (x <- seq; if x > pivot) yield x
      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(", "))

  val a = Array[Int](-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(ArraySeq.unsafeWrapArray(a)).mkString(", "))

}