Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Three-way radix quicksort
import java.util.Arrays
// Three-way radix quicksort aka Multi-key quicksort
//
// Fast Algorithms for Sorting and Searching Strings
// http://www.cs.princeton.edu/~rs/strings/paper.pdf
object RadixQuicksort {
def sort(arr: Array[String]) =
sort0(arr, 0, arr.length, 0)
def sort(arr: Array[String], from: Int, to: Int) =
sort0(arr, from, to-from, 0)
def sort(arr: Array[String], from: Int, to: Int, depth: Int) =
sort0(arr, from, to-from, depth)
private def charAt(str: String, depth: Int): Int =
if (str.length == depth) -1 else str.charAt(depth)
private def sort0(arr: Array[String], base: Int, len: Int, depth: Int): Unit = {
// |---equal---|---lt---|---not yet partitioned---|---gt---|---equal---|
// aEq a b bEq
if (len <= 1)
return
var r = util.Random.nextInt(len)
swap(arr, base, base+r)
val pivot = charAt(arr(base), depth)
var aEq = base
var a = base
var b = base + len - 1
var bEq = base + len - 1
do {
while (a <= b && charAt(arr(a), depth) <= pivot) {
if (charAt(arr(a), depth) == pivot) {
swap(arr, aEq, a)
aEq += 1
}
a += 1
}
while (a <= b && charAt(arr(b), depth) >= pivot) {
if (charAt(arr(b), depth) == pivot) {
swap(arr, bEq, b)
bEq -= 1
}
b -= 1
}
if (a <= b) { // if (a > b) break
swap(arr, a, b)
a += 1
b -= 1
}
} while (a <= b)
val aEqLen = math.min(aEq-base, a-aEq)
vecswap(base, a-aEqLen, aEqLen, arr);
val bEqLen = math.min(bEq-b, base+len-bEq-1)
vecswap(a, base+len-bEqLen, bEqLen, arr);
r = a-aEq
sort0(arr, base, r, depth)
if (charAt(arr(base+r), depth) != -1) {
sort0(arr, base + r, aEq + len-bEq-1, depth+1)
}
r = bEq-b
sort0(arr, base + len-r, r, depth)
}
private def swap(arr: Array[String], a: Int, b: Int) = {
val x = arr(a)
arr(a) = arr(b)
arr(b) = x
}
private def vecswap(i: Int, j: Int, len: Int, arr: Array[String]): Unit = {
var nn = len
var ii = i
var jj = j
while (nn > 0) {
swap(arr, ii, jj)
ii += 1
jj += 1
nn -= 1
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.