In-place sort for IntArray

Support
1

I’m trying to sort an IntArray based on a comparator and noticed there is no way to do this in-place (no “sortWith” function). Am I missing something obvious here?

Edit: I don’t the numbers to be sorted directly, but based on some weight-lookup:

If the IntArray contains 1, 2, 3 and

weight[1] = 10
weight[2] = 42
weight[3] = 5

the sorted array should contain 2, 1, 3.

Thanks! :slightly_smiling_face:

2

do you mean something like:

inline fun printIntArrayContent(lamb : () -> IntArray){
    println(lamb().contentToString())
}
fun main() = printIntArrayContent{
//sampleStart
    arrayOf(1,2,3)
        .zip(arrayOf(10, 42, 5))
        .sortedByDescending { it.second }
        .map { it.first }
        .toIntArray()
//sampleEnd
}

But with better performance?

3

Yes, with much better performance. :stuck_out_tongue:
Something like:

var numbers: IntArray = intArrayOf(1, 2, 3)
numbers.sortWith(Comparator { a: Int, b: Int -> weight[b] - weight[a] } )
5

Maybe, but this can also cause ArrayIndexOutOfBoundsException :wink:

My proposition is this:

fun main() {
	val sortedSet = sortedSetOf(
		compareByDescending { it.second },
		1 to 10,
		2 to 42,
		3 to 5
	)
	println(sortedSet.map { it.first }) // [2, 1, 3]
}
6

JDK implements in-place sorting via DualPivotQuicksort

There is no such version available for custom comparator.

I guess you can use a 3rd-party like fastutil quickSort

7

Simple solution. It can be used with a Comparator, or you can create the same function with a comparison function (Int, Int) -> Int.

fun main() {
   val indices = intArrayOf(1, 2, 3)
   val weight = IntArray(4)
   weight[1] = 10
   weight[2] = 42
   weight[3] = 5
   indices.sortWith(Comparator<Int> { a, b -> weight[b] - weight[a] })
   println(indices.contentToString())
}

fun IntArray.sortWith(comparator: Comparator<Int>) {
   // Code from https://en.wikipedia.org/wiki/Quicksort
   fun partition(array: IntArray, lo: Int, hi: Int): Int {
      val pivot = array[(lo + hi) / 2]
      var i = lo - 1
      var j = hi + 1
      while (true) {
            do {
               i = i + 1
            } while (comparator.compare(array[i], pivot) < 0)
            do {
               j = j - 1
            } while (comparator.compare(array[j], pivot) > 0)
            if (i >= j) {
               return j
            }
            val tmp = array[j]
            array[j] = array[i]
            array[i] = tmp
      }
   }
   
   fun quicksort(array: IntArray, lo: Int, hi: Int) {
      if (lo < hi) {
            val p = partition(array, lo, hi)
            quicksort(array, lo, p)
            quicksort(array, p + 1, hi)
      }
   }
    
   quicksort(this, 0, this.size - 1)
}
8

Here is your request: https://youtrack.jetbrains.com/issue/KT-37860

Btw, do you care about guaranteed O(n log n) performance for your use-case or an average O(n log n) performance (as with quick sort) is fine?

9

Thanks for creating the feature request!

For my use-case (development of 2-player board games) an average O(n log n) would be perfectly fine.

But if what Ilya Gorbunov has commented in the issue (“memory inefficient as it would require to box the elements being compared each time”), that would be a reason in my opinion to not implement this feature - at least not as long as the JVM requires this.

10

You don’t need boxing if you create a specific interface like IntComparator in the fastutil library. But I don’t know if a comparison function like (Int, Int) → Int will box the values or not.