quicksort

Quicksort / Quickselect?

Quicksort

- Input is a list
- choose the first element as the pivot
- split the rest of the list into things smaller than the pivot and bigger than the pivot (equals on either side)
- recursively sort the sides
- put them together

def quicksort(list: List[Int]): List[Int] = {
  if(list.length <= 1) list
  else {
    val i = (list.length/2)
    return quicksort(list.take(i)) ::: quicksort(list.drop(i))
  }
}

that actually doesn't work though

=====

def quicksort(list: List[Int]): List[Int] = {
  if(list.length <= 1) list
  else {
    val pivot = list.head
    val (smaller,bigger) = list.tail.partition(_ < pivot)
    quicksort(smaller) ::: pivot :: quicksort(bigger)
  }
}

T(n) = 2*T(n/2) + n  ==>  O(nlogn)