In ML --- Must use pattern matching in function definition Problem: Write a quic

Question

In ML --- Must use pattern matching in function definition

Problem: Write a quicksort function of type int list -> int list. The lists are split according to a pivot element. Here is a review of the quicksort algorithm: First pick an element on the input list and call it the pivot (the first element of the list is usually a good choice). Partition the rest of the list into two sublists: one with all the elements less than the pivot and one with all the elements not less than the pivot. Recursively sort the sublists. Combine the sorted sublists and the pivot into the final sorted list.

Explanation / Answer

def quickSorting: List[Int] => List[Int] = {
case Nil => Nil
case pivot :: tail =>
val (smaller, rest) = tail.partition(_ < pivot)
quickSorting(smaller) ::: pivot :: quickSorting(rest)
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.