2
\$\begingroup\$

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))
    }
}
Improve this question
\$\endgroup\$

1 Answer 1

Reset to default
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Really great insights! Can you please provide links to some resources so that I can learn more about such optimizations? \$\endgroup\$
    – Hungry Blue Dev
    Jan 16, 2019 at 3:53
  • 2
    \$\begingroup\$ @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. \$\endgroup\$
    – vnp
    Jan 16, 2019 at 5:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.