Reputation: 3197
The following is a text-book quick sort implementation in Scala. When comparing the execution time of quickSortRecursive to java.util.Arrays.sort(), I found java.util.Arrays.sort to be an order of magnitude faster on large arrays. Can someone hint on the reason for this difference in performance?
def quickSortRecursive(list: Array[Int])(low: Int=0, high: Int=list.length-1): Unit = {
if (low<high) {
swap(list,Random.nextInt(high),high)
val pivot = partition(list, low, high)
quickSortRecursive(list)(low, pivot-1)
quickSortRecursive(list)(pivot+1, high)
}
}
private def partition(list: Array[Int], low: Int, high: Int): Int = {
val pivot = list(high)
var lowhigh = low
for (i <- low until high) {
if (list(i) < pivot) {
swap(list, lowhigh, i);
lowhigh += 1;
}
}
swap(list, lowhigh, high);
lowhigh
}
private def swap(list: Array[Int], i: Int, j: Int): Unit = {
val tmp = list(i)
list(i) = list(j)
list(j) = tmp
}
Upvotes: 1
Views: 445
Reputation: 10894
You comapared a highly optimized implementation of a generic sorting algorithm (java.util.Arrays.sort) to a handrolled implementation without optimization (your Scala code).
Thus it is bound to be slower.
What result are you aiming for? For a good comparison you could try comparing the different sorting algorithms provided by the Scala standard library against the ones provided by the Java standard disribution. Or you could implement your Quicksort in Java and Scala and compare the results.
Upvotes: 2