Selection Sort

object Main extends App {
        def selectionSort(arr: Array[Int]) = { //O(n2), O(1) space
            for (i <- 0 until arr.size) {
                for (j <- i+1 until arr.size) {
                    if (arr(j) < arr(i)) {
                        val temp = arr(i)
                        arr(i) = arr(j)
                        arr(j) = temp
                    }
                }
            }
            arr
        }
        
        def selectionRecSort(arr: Array[Int], first: Int = 0, second: Int = 0): Array[Int] = { //O(n2), O(1) space
            if (first >= arr.size-1) arr
            else if (second >= arr.size-1) selectionRecSort(arr, first+1, 0)
            else {
                for (j <- first until arr.size) {
                    if (arr(j) < arr(second)) {
                        val temp = arr(second)
                        arr(second) = arr(j)
                        arr(j) = temp
                    }
                }
                selectionRecSort(arr, first, second+1)
            }
        }
        //Scala specific functional approach
        def selectionSortStrange(xs: List[Int]) = {
                def maximum(xs: List[Int]): List[Int] =
                  (List(xs.head) /: xs.tail) {
                    (ys, x) =>
                      if(x > ys.head) (x :: ys)
                      else            (ys.head :: x :: ys.tail)
                 }
                  def selectionSortHelper(xs: List[Int], accumulator: List[Int]): List[Int] =
                    if(xs.isEmpty) accumulator
                    else {
                          val ys = maximum(xs)
                          selectionSortHelper(ys.tail, ys.head :: accumulator)
                    }
                
          selectionSortHelper(xs, Nil) 
        }
        println(selectionSort(Array(1,2,3,-4,0,5,2342,3,2,1)).toList)
        println(selectionRecSort(Array(1,2,3,-4,0,5,2342,3,2,1)).toList)
        println(selectionSortStrange(List(1,2,3,-4,0,5,2342,3,2,1)).toList)
}