Selection Sort
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849
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)
}
Scala
INFO