Exercise: Functional Quick Sort
There is a popular exercise in the functional programming community, to implement a simplified version of the Quick Sort algorithm. It is a recursive algorithm, so it is a good exercise to practice recursion. It is also a good exercise to practice functional programming, because it can be implemented in a functional way. The algorithm is as follows: Quick sort should take the first element (pivot), then split the rest to bigger and smaller than pivot, to finally return smaller elements sorted recursively, then pivot, and then bigger elements sorted recursively. Also, if list size is 0 or 1, it is already sorted, so you should return the list itself. The complete implementation should take just a couple of lines.
fun <T : Comparable<T>> List<T>.quickSort(): List<T> {
TODO()
}
This problem can either be solved in the below playground or you can clone kotlin-exercises project and solve it locally. In the project, you can find code template for this exercise in functional/collections/QuickSort.kt. You can find there starting code and unit tests.
Once you are done with the exercise, you can check your solution here.
import org.junit.Test
import java.util.*
import kotlin.test.assertEquals
// TODO: Quick sort should take first element (pivot), then split rest to bigger than pivot and smaller and finally return
// first smaller sorted, then pivot and finally bigger sorted
fun <T : Comparable<T>> List<T>.quickSort(): List<T> {
TODO()
}
class QuickSortTest {
@Test
fun `Empty list is sorted`() {
assertEquals(emptyList(), emptyList<Int>().quickSort())
}
@Test
fun `Single element is sorted`() {
assertEquals(listOf(1), listOf(1).quickSort())
}
@Test
fun `Simple numbers sorting`() {
assertEquals(listOf(1, 2, 3, 5, 6), listOf(3, 2, 5, 1, 6).quickSort())
}
@Test
fun `Simple String sorting`() {
assertEquals(listOf("A", "B", "C", "D"), listOf("C", "D", "A", "B").quickSort())
}
@Test
fun `Random list sorting should give the same result as when we use stdlib sorted function`() {
val rand = Random(244252)
val listOfRandomLists = (1..100).map { _ -> (1..100).map { rand.nextInt() } }
for (list: List<Int> in listOfRandomLists) {
assertEquals(list.sorted(), list.quickSort())
}
}
}
Marcin Moskala is a highly experienced developer and Kotlin instructor as the founder of Kt. Academy, an official JetBrains partner specializing in Kotlin training, Google Developers Expert, known for his significant contributions to the Kotlin community. Moskala is the author of several widely recognized books, including "Effective Kotlin," "Kotlin Coroutines," "Functional Kotlin," "Advanced Kotlin," "Kotlin Essentials," and "Android Development with Kotlin."
Beyond his literary achievements, Moskala is the author of the largest Medium publication dedicated to Kotlin. As a respected speaker, he has been invited to share his insights at numerous programming conferences, including events such as Droidcon and the prestigious Kotlin Conf, the premier conference dedicated to the Kotlin programming language.
