Category talk:Wren-sort: Difference between revisions
→Source code: Added Find.quick method plus a few other minor changes.
m (→Source code: Tweak.) |
(→Source code: Added Find.quick method plus a few other minor changes.) |
||
Line 1:
===Source code===
<lang ecmascript>/* Module "
import "/trait" for Comparable
Line 91:
if (cmp == true) cmp = Cmp.defaultDesc(a[0])
if (!cmp) cmp = Cmp.default(a[0])
quick_(a, s, e, cmp)
}
Line 112 ⟶ 111:
}
}
quick_(a, s, r, cmp)
quick_(a, l, e, cmp)
Line 412 ⟶ 410:
}
return [max, iMax.count, iMax]
}
// Private helper function for 'quick' method.
static partition_(a, left, right, pivotIndex, cmp) {
var pivotValue = a[pivotIndex]
a[pivotIndex] = a[right]
a[right] = pivotValue
var storeIndex = left
var i = left
while (i < right) {
if (cmp.call(a[i], pivotValue) < 0) {
var t = a[storeIndex]
a[storeIndex] = a[i]
a[i] = t
storeIndex = storeIndex + 1
}
i = i + 1
}
var temp = a[right]
a[right] = a[storeIndex]
a[storeIndex] = temp
return storeIndex
}
// Finds the 'k'th smallest element of an unsorted list according to 'cmp'
// using the 'quickselect' algorithm. 'k' is zero based.
static quick(a, k, cmp) {
Sort.isList_(a)
if (k.type != Num || !k.isInteger || k < 0) {
Fiber.abort("'k' must be a non-negative integer")
}
var count = a.count
if (count <= k) Fiber.abort("The list is too small.")
if (count == 1) return a[0]
if (cmp == true) cmp = Cmp.defaultDesc(a[0])
if (!cmp) cmp = Cmp.default(a[0])
var left = 0
var right = count - 1
while (true) {
if (left == right) return a[left]
var pivotIndex = ((left + right)/2).floor
pivotIndex = partition_(a, left, right, pivotIndex, cmp)
if (k == pivotIndex) {
return a[k]
} else if (k < pivotIndex) {
right = pivotIndex - 1
} else {
left = pivotIndex + 1
}
}
}
Line 420 ⟶ 468:
static lowest(a) { lowest(a, false) }
static highest(a) { highest(a, false) }
static quick(a, k) { quick(a, k, false) }
// Finds the median element(s) of a sorted list.
| |||