Sorting algorithms in Kotlin - Bubble, Insertion, Selection, Merge and Quick sort

Question

Introduction

I decided to try Kotlin because of its forgiving nature to long-time Java users. I implemented a few introductory sorting algorithms and would like to have them reviewed, not just to ensure that I'm applying Kotlin correctly, but also to improve my style and get rid of any potential bugs.

I have made use of a few extension functions to make the code more readable and all relevant source code will be posted in this question.

Note: I tagged it as Java as well, because someone familiar with Java can easily get into Kotlin if they see how easy it is to read Kotlin. Anything applicable in Java can almost always be applied directly to Kotlin code.

Project Structure

Main files

+- meta
| +- annotations
| | +- ComparisonSort
| | +- StableSort
| +- Complexity
+- sort
| +- AbstractSort
| +- BubbleSort
| +- InsertionSort
| +- MergeSort
| +- QuickSort
| +- SelectionSort
+- util
 +- ArrayHelper

Tests

+- sort
| +- AbstractSortTest
| +- BubbleSortTest
| +- InsertionSortTest
| +- MergeSortTest
| +- QuickSortTest
| +- SelectionSortTest
+- util
 +- ArrayHelperTest

My concerns

Besides being undocumented (I didn't add comments because I think the code is already readable enough), I think I might my code could be a bit better organized. If there are some test cases that I forgot to include, please bring it to my attention. General comments on any potential issues, preferences are always welcome.

The Source Code

ArrayHelper.kt

Note that all the functions here are extension functions. These methods are tacked on top of the existing ones in the Array.kt class provided in the library.

package com.github.hungrybluedev.util
import kotlin.random.Random
fun <T> Array<T>.swap(i: Int, j: Int) {
 val tmp = this[i]
 this[i] = this[j]
 this[j] = tmp
}
fun <T> Array<T>.shuffle() {
 shuffle(0, size)
}
fun <T> Array<T>.shuffle(lower: Int, upper: Int) {
 for (index in lower + 2 until upper) {
 swap(index, Random.nextInt(index))
 }
}
fun <T : Comparable<T>> Array<T>.isSorted(): Boolean {
 return isSorted(0, size)
}
fun <T : Comparable<T>> Array<T>.isSorted(
 lower: Int,
 upper: Int
): Boolean {
 for (index in lower + 1 until upper) {
 if (this[index - 1] > this[index]) {
 return false
 }
 }
 return true
}
fun <T> Array<T>.isSorted(
 comparator: Comparator<T>,
 lower: Int,
 upper: Int
): Boolean {
 for (index in lower + 1 until upper) {
 if (comparator.compare(this[index - 1], this[index]) > 0) {
 return false
 }
 }
 return true
}

AbstractSort.kt

package com.github.hungrybluedev.sort
import com.github.hungrybluedev.meta.Complexity
abstract class AbstractSort(val complexity: Complexity) {
 fun <T : Comparable<T>> sort(arr: Array<T>) {
 sort(arr, naturalOrder(), 0, arr.size)
 }
 fun <T : Comparable<T>> sort(arr: Array<T>, lower: Int, upper: Int) {
 sort(arr, naturalOrder(), lower, upper)
 }
 fun <T> sort(arr: Array<T>, comparator: Comparator<T>) {
 sort(arr, comparator, 0, arr.size)
 }
 abstract fun <T> sort(
 arr: Array<T>,
 comparator: Comparator<T>,
 lower: Int,
 upper: Int
 )
}

BubbleSort.kt

package com.github.hungrybluedev.sort
import com.github.hungrybluedev.meta.Complexity
import com.github.hungrybluedev.meta.annotatioins.ComparisonSort
import com.github.hungrybluedev.meta.annotatioins.StableSort
import com.github.hungrybluedev.util.swap
@ComparisonSort
@StableSort
class BubbleSort : AbstractSort(Complexity.QUADRATIC) {
 override fun <T> sort(
 arr: Array<T>,
 comparator: Comparator<T>,
 lower: Int,
 upper: Int
 ) {
 var sorted = 0
 do {
 var swapped = false
 for (i in lower until upper - 1 - sorted) {
 if (comparator.compare(arr[i], arr[i + 1]) > 0) {
 arr.swap(i, i + 1)
 swapped = true
 }
 }
 sorted++
 } while (swapped)
 }
}

InsertionSort.kt

package com.github.hungrybluedev.sort
import com.github.hungrybluedev.meta.Complexity
import com.github.hungrybluedev.meta.annotatioins.ComparisonSort
import com.github.hungrybluedev.meta.annotatioins.StableSort
@StableSort
@ComparisonSort
class InsertionSort : AbstractSort(Complexity.QUADRATIC) {
 override fun <T> sort(
 arr: Array<T>,
 comparator: Comparator<T>,
 lower: Int,
 upper: Int
 ) {
 for (j in lower + 1 until upper) {
 val key = arr[j]
 var i = j - 1
 while (i >= lower && comparator.compare(key, arr[i]) < 0) {
 arr[i + 1] = arr[i--]
 }
 arr[i + 1] = key
 }
 }
}

MergeSort.kt

package com.github.hungrybluedev.sort
import com.github.hungrybluedev.meta.Complexity
import com.github.hungrybluedev.meta.annotatioins.ComparisonSort
import com.github.hungrybluedev.meta.annotatioins.StableSort
@StableSort
@ComparisonSort
class MergeSort : AbstractSort(Complexity.LINEARITHMIC) {
 private fun <T> merge(
 from: Array<T>,
 to: Array<T>,
 p: Int,
 q: Int,
 r: Int,
 comparator: Comparator<T>
 ) {
 var i = p
 var j = p
 var k = q
 while (i < q && k < r) {
 to[j++] = if (comparator.compare(from[i], from[k]) < 0)
 from[i++]
 else
 from[k++]
 }
 while (i < q) {
 to[j++] = from[i++]
 }
 while (k < r) {
 to[j++] = from[k++]
 }
 }
 private fun <T> internalSort(
 arrA: Array<T>,
 arrB: Array<T>,
 comparator: Comparator<T>,
 p: Int,
 r: Int
 ) {
 if (r - p <= 1) {
 return
 }
 val q = p + ((r - p) shr 1)
 internalSort(arrB, arrA, comparator, p, q)
 internalSort(arrB, arrA, comparator, q, r)
 merge(arrB, arrA, p, q, r, comparator)
 }
 override fun <T> sort(
 arr: Array<T>,
 comparator: Comparator<T>,
 lower: Int,
 upper: Int
 ) {
 val copy = arr.clone()
 internalSort(arr, copy, comparator, lower, upper)
 }
}

QuickSort.kt

package com.github.hungrybluedev.sort
import com.github.hungrybluedev.meta.Complexity
import com.github.hungrybluedev.meta.annotatioins.ComparisonSort
import com.github.hungrybluedev.util.swap
import kotlin.random.Random
@ComparisonSort
class QuickSort : AbstractSort(Complexity.LINEARITHMIC) {
 private fun <T> partition(
 arr: Array<T>,
 lower: Int,
 upper: Int,
 comparator: Comparator<T>
 ): Int {
 val pivot = arr[lower + Random.nextInt(upper - lower + 1)]
 var p = lower - 1
 var q = upper + 1
 while (true) {
 while (comparator.compare(arr[++p], pivot) < 0);
 while (comparator.compare(arr[--q], pivot) > 0);
 if (p >= q) {
 return q
 }
 arr.swap(p, q)
 }
 }
 private fun <T> internalSort(
 arr: Array<T>,
 comparator: Comparator<T>,
 lower: Int,
 upper: Int
 ) {
 if (lower >= upper) {
 return
 }
 val pivot = partition(arr, lower, upper, comparator)
 internalSort(arr, comparator, lower, pivot)
 internalSort(arr, comparator, pivot + 1, upper)
 }
 override fun <T> sort(
 arr: Array<T>,
 comparator: Comparator<T>,
 lower: Int,
 upper: Int
 ) {
 internalSort(arr, comparator, lower, upper - 1)
 }
}

Complexity.kt

package com.github.hungrybluedev.meta
enum class Complexity {
 LOGARITHMIC,
 LINEAR,
 LINEARITHMIC,
 QUADRATIC,
 CUBIC
}

ComparisonSort.kt

package com.github.hungrybluedev.meta.annotatioins
annotation class ComparisonSort

StableSortSort.kt

package com.github.hungrybluedev.meta.annotatioins
annotation class StableSort

Tests

AbstractSortTest.kt

package com.github.hungrybluedev.sort
import com.github.hungrybluedev.meta.Complexity
import com.github.hungrybluedev.util.isSorted
import com.github.hungrybluedev.util.shuffle
import org.junit.jupiter.api.Assertions.assertArrayEquals
import org.junit.jupiter.api.Assertions.assertTrue
import org.junit.jupiter.api.Test
import kotlin.random.Random
abstract class AbstractSortTest<out T : AbstractSort>(private val sorter: T) {
 private val size = when (sorter.complexity) {
 Complexity.QUADRATIC -> 20_000
 Complexity.LINEARITHMIC -> 1_000_000
 else -> 10_000
 }
 @Test
 internal fun emptyTest() {
 val arr = arrayOf<Int>()
 sorter.sort(arr)
 assertArrayEquals(arrayOf<Int>(), arr)
 }
 @Test
 internal fun singleElementTest() {
 val arr = arrayOf(1)
 sorter.sort(arr)
 assertArrayEquals(arrayOf(1), arr)
 }
 @Test
 internal fun sortedElementsTest() {
 val arr = arrayOf(1, 2, 5, 7)
 sorter.sort(arr)
 assertArrayEquals(arrayOf(1, 2, 5, 7), arr)
 }
 @Test
 internal fun unsortedElementsTest() {
 val arr = arrayOf(7, 2, 5, 1)
 sorter.sort(arr)
 assertArrayEquals(arrayOf(1, 2, 5, 7), arr)
 }
 @Test
 internal fun reverseOrderTest() {
 val arr = arrayOf(9, 8, 7, 6, 5, 4, 3, 2, 1, 0)
 sorter.sort(arr)
 assertArrayEquals(arrayOf(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), arr)
 }
 @Test
 internal fun partialSortTest() {
 val arr = arrayOf(9, 8, 7, 6, 5, 4, 3, 2, 1, 0)
 sorter.sort(arr, 4, 9)
 assertArrayEquals(arrayOf(9, 8, 7, 6, 1, 2, 3, 4, 5, 0), arr)
 }
 @Test
 internal fun comparatorDescendingTest() {
 val arr = arrayOf(9, 3, 4, 6, 2, 1, 0, 5, 7, 8)
 sorter.sort(arr, reverseOrder())
 assertArrayEquals(arrayOf(9, 8, 7, 6, 5, 4, 3, 2, 1, 0), arr)
 }
 @Test
 internal fun comparatorPartialDescendingTest() {
 val arr = arrayOf(3, 0, 1, 2, 4, 8, 5, 9, 7, 6)
 sorter.sort(arr, 0, 5)
 sorter.sort(arr, reverseOrder(), 5, 10)
 assertArrayEquals(arrayOf(0, 1, 2, 3, 4, 9, 8, 7, 6, 5), arr)
 }
 @Test
 internal fun repeatedElementsTest() {
 val arr = arrayOf(0, 0, 1, 2, 3, 3, 4, 4, 4, 4, 4, 5, 6, 7, 8, 8, 9, 9, 9, 9)
 val cpy = arr.clone()
 cpy.shuffle()
 sorter.sort(cpy)
 assertArrayEquals(arr, cpy)
 }
 @Test
 internal fun randomDistinctArrayTest() {
 val arr = Array(size) { x -> x }
 sorter.sort(arr)
 assertTrue(arr.isSorted())
 }
 @Test
 internal fun randomRepeatedTest() {
 val arr = Array(size) { Random.nextInt(size) }
 sorter.sort(arr)
 assertTrue(arr.isSorted())
 }
 @Test
 internal fun descendingTest() {
 val arr = Array(size) { x -> size - x }
 sorter.sort(arr)
 assertTrue(arr.isSorted())
 }
}

BubbleSortTest.kt

package com.github.hungrybluedev.sort
internal class BubbleSortTest : AbstractSortTest<BubbleSort>(BubbleSort())

InsertionSortTest.kt

package com.github.hungrybluedev.sort
internal class InsertionSortTest : AbstractSortTest<InsertionSort>(InsertionSort())

MergeSortTest.kt

package com.github.hungrybluedev.sort
internal class MergeSortTest : AbstractSortTest<MergeSort>(MergeSort())

QuickSortTest.kt

package com.github.hungrybluedev.sort
internal class QuickSortTest : AbstractSortTest<QuickSort>(QuickSort())

SelectionSortTest.kt

package com.github.hungrybluedev.sort
internal class SelectionSortTest : AbstractSortTest<SelectionSort>(SelectionSort())

ArrayHelperTest.kt

package com.github.hungrybluedev.util
import org.junit.jupiter.api.Assertions.assertFalse
import org.junit.jupiter.api.Assertions.assertTrue
import org.junit.jupiter.api.Test
internal class ArrayHelperTest {
 @Test
 internal fun smallAscendingTest() {
 val arr = arrayOf(1, 2, 3, 4, 5)
 assertTrue(arr.isSorted())
 assertTrue(arr.isSorted(0, arr.size))
 assertTrue(arr.isSorted(naturalOrder(), 0, arr.size))
 }
 @Test
 internal fun smallDescendingTest() {
 val arr = arrayOf(9, 7, 6, 4, 3, 2)
 assertFalse(arr.isSorted())
 assertFalse(arr.isSorted(0, arr.size))
 assertTrue(arr.isSorted(reverseOrder(), 0, arr.size))
 }
}

Answer 1

Few typical problems:

• if (comparator.compare(from[i], from[k]) < 0) causes merge sort to lose stability. If the elements compare equal, the value from the right subarray is merged first.

• Insertion sort implementation is suboptimal: at each iteration of

   while (i >= lower && comparator.compare(key, arr[i]) < 0) {
  

  two conditions are tested. It is possible to test only one. In pseudocode:

   if key <= array[lower]
   // Don't bother to compare values. We are guaranteed
   // that everything is not less than the key. Just shift.
   while i >= lower
   arr[i + 1] = arr[i--]
   else
   // Don't bother to check indices. We are guaranteed
   // to not fall off: the first element is less than the key,
   // and naturally guard the insertion.
   while key < arr[i]
   arr[i + 1] = arr[i--]
   arr[i + 1] = key;
  

  It doesn't change the quadratic nature of the insertion, but improves the bottomline. After all, not everything is about big-oh. In the rare cases we resort to insertion sort, this may give a crucial performance boost.

• Quick sort implementation is equally suboptimal. Standard ways to improve performance are

  • Do not recur into small partitions; the call becomes too expensive. Define a threshold, say k, and if the partition is smaller than k return immediately. Once the initial invocation of internalSort returns, run an insertion sort. It will complete in \$O(nk)\$ (do you see why?). BTW, it is one of the rare occasions where resorting to insertion sort is beneficial.

  • Eliminate the tail recursive call. Java doesn't do tail recursion elimination, and I am sure Kotlin doesn't either. Keep in mind that you want to recur into a smaller partition, and handle the larger one in the loop.

  • I am not sure that the random pivot selection strategy is sound.

• I don't see the benefits of enum class Complexity.

• Hungry Blue Dev: Really great insights! Can you please provide links to some resources so that I can learn more about such optimizations?
• vnp: @HungryBlueDev Give the praise where it belongs. Here are the insights from a master; what the entire course. He uses C++, but you'll see soon that the language doesn't matter.