Use three-way quicksort. Fix the pivot value before moving any entries, and group equal entries together so that none needs a recursive call. These helpers and the sorter belong inside an enclosing scope containing The array partitioning loop invariant iswith unclassified. Swaps preserve the segment's array multiset and leave all entries outside it unchanged. The loop variant decreases in every branch. When swapping an entry from the right into
a.def swap(i: Int, j: Int): Unit = {
val t = a(i); a(i) = a(j); a(j) = t
}
def split(l: Int, r: Int): (Int, Int) = {
// Pre: 0 <= l < r <= a.length.
val p = a(l)
var lt = l
var i = l
var gt = r
while (i < gt) {
if (a(i) < p) {
swap(lt, i)
lt += 1
i += 1
} else if (a(i) > p) {
gt -= 1
swap(i, gt)
} else {
i += 1
}
}
(lt, gt)
}
def quicksort(l: Int, r: Int): Unit = {
require(0 <= l && l <= r && r <= a.length)
if (r - l > 1) {
val (lt, gt) = split(l, r)
quicksort(l, lt)
quicksort(gt, r)
}
}
// Sort the whole array with quicksort(0, a.length).i, do not increment i, since the incoming entry still needs classification. At termination,Here the middle segment is nonempty because the original pivot occurs somewhere in the preserved array multiset. Both recursive segments therefore have length strictly smaller than . Mathematical induction on segment length proves that the two recursive calls sort their segments, and their ordering relative to the middle segment proves the complete sorting postcondition.There is no additional array. The call stack and returned boundary pairs still use auxiliary space. An all-equal input takes one linear scan and no nontrivial recursive calls, so its time complexity is for . Balanced partitions give time complexity; a fixed first pivot can still give on adversarial distinct inputs. The worst-case call stack has entries.
Articles by others on the same topic
There are currently no matching articles.