To demonstrate the expressiveness and power of functional programming, we are going to ask you to implement quicksort Here's a quick definition of quicksort:
For a given list, if the list is not empty, choose one element as a pivot element. It may be easiest to pick the first element as the pivot. Partition the remainder of the elements into two lists, one that contains elements that are less than or equal to the pivote, and one that contains elements that are greater than the pivot. Recursively call quicksort on the left and right partitions; finally, concatenate the left, pivot, and right together.
The signature you should use is:
def qs[T <% Ordered[T]](list: List[T]): List[T]Example:
scala> qs(List(1, 34, 65, 3, 3, -1))
res1: List[Int] = List(-1, 1, 3, 3, 34, 65)
scala> qs(List("a", "b", "a", "abc", "bcd","c"))
res2: List[String] = List(a, a, abc, b, bcd, c)- You can use pattern matching with recursion to solve this problem very easily
- You can use for comprehensions to easily partition the list
- You can also use the
partitionmethod onListto partition the list