Quicksort out of bounds (Kotlin)

Question

I'm trying to implement quicksort in Kotlin.

I keep getting outofboundserror, but I just can't figure out why.

Below is my code:

fun quicksort(arr: MutableList<Int>) {
    quicksortHelper(arr, 0, arr.size + 1)
}

fun quicksortHelper(arr: MutableList<Int>, low: Int, high: Int) {
    if (low < high) {
        val partitionIdx = partition(arr, low, high)
        quicksortHelper(arr, low, partitionIdx)
        quicksortHelper(arr, partitionIdx + 1, high)
    }
}

fun partition (arr: MutableList<Int>, low: Int, high: Int): Int {
    val pivot = arr[low]
    var i= low
    var j = high
    while (i < j) {
        do {
            i++
        } while (arr[i] <= pivot)
        do {
            j--
        } while (arr[j] > pivot)
        if (i < j) {
            val temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
        }
    }
    val temp = arr[low]
    arr[low] = arr[j]
    arr[j] = temp

    return j
}

Answer 1

In quicksort, you likely want to start with a high of arr.size - 1. That is:

fun quicksort(arr: MutableList<Int>) {
    quicksortHelper(arr, 0, arr.size - 1)
}

Other than that, it looks like you have some issues with your pivoting method and some inconsistencies in your indexing. You want to start with i = low - 1 and j = high + 1 or else you would be skipping the first and last elements of your array. Adding the following changes to your partition function in addition to the change above should fix your issue:

fun partition (arr: MutableList<Int>, low: Int, high: Int): Int {
    val pivot = arr[(high + low) / 2] // pivot at the middle element instead of `low`
    var i = low - 1
    var j = high + 1
    while (i < j) {
        do {
            i++
        } while (arr[i] < pivot)
        do {
            j--
        } while (arr[j] > pivot)
        if (i < j) {
            val temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
        }
    }
    val temp = arr[low]
    arr[low] = arr[j]
    arr[j] = temp

    return j
}

For more details, see the 'Hoarse Partition Scheme' pseudocode on the wikipedia quicksort page.