98 lines
2.9 KiB
Plaintext
98 lines
2.9 KiB
Plaintext
/* NetRexx */
|
|
options replace format comments java crossref symbols nobinary
|
|
/** @see <a href="http://en.wikipedia.org/wiki/Quickselect">http://en.wikipedia.org/wiki/Quickselect</a> */
|
|
|
|
runSample(arg)
|
|
return
|
|
|
|
-- ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
|
|
method qpartition(list, ileft, iright, pivotIndex) private static
|
|
pivotValue = list[pivotIndex]
|
|
list = swap(list, pivotIndex, iright) -- Move pivot to end
|
|
storeIndex = ileft
|
|
loop i_ = ileft to iright - 1
|
|
if list[i_] <= pivotValue then do
|
|
list = swap(list, storeIndex, i_)
|
|
storeIndex = storeIndex + 1
|
|
end
|
|
end i_
|
|
list = swap(list, iright, storeIndex) -- Move pivot to its final place
|
|
return storeIndex
|
|
|
|
-- ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
|
|
method qselectInPlace(list, k_, ileft = -1, iright = -1) public static
|
|
if ileft = -1 then ileft = 1
|
|
if iright = -1 then iright = list[0]
|
|
|
|
loop label inplace forever
|
|
pivotIndex = Random().nextInt(iright - ileft + 1) + ileft -- select pivotIndex between left and right
|
|
pivotNewIndex = qpartition(list, ileft, iright, pivotIndex)
|
|
pivotDist = pivotNewIndex - ileft + 1
|
|
select
|
|
when pivotDist = k_ then do
|
|
returnVal = list[pivotNewIndex]
|
|
leave inplace
|
|
end
|
|
when k_ < pivotDist then
|
|
iright = pivotNewIndex - 1
|
|
otherwise do
|
|
k_ = k_ - pivotDist
|
|
ileft = pivotNewIndex + 1
|
|
end
|
|
end
|
|
end inplace
|
|
return returnVal
|
|
|
|
-- ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
|
|
method swap(list, i1, i2) private static
|
|
if i1 \= i2 then do
|
|
t1 = list[i1]
|
|
list[i1] = list[i2]
|
|
list[i2] = t1
|
|
end
|
|
return list
|
|
|
|
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
|
|
method runSample(arg) private static
|
|
parse arg samplelist
|
|
if samplelist = '' | samplelist = '.' then samplelist = 9 8 7 6 5 0 1 2 3 4
|
|
items = samplelist.words
|
|
say 'Input:'
|
|
say ' 'samplelist.space(1, ',').changestr(',', ', ')
|
|
say
|
|
|
|
say 'Using in-place version of the algorithm:'
|
|
iv = ''
|
|
loop k_ = 1 to items
|
|
iv = iv qselectInPlace(buildIndexedString(samplelist), k_)
|
|
end k_
|
|
say ' 'iv.space(1, ',').changestr(',', ', ')
|
|
say
|
|
|
|
say 'Find the 4 smallest:'
|
|
iv = ''
|
|
loop k_ = 1 to 4
|
|
iv = iv qselectInPlace(buildIndexedString(samplelist), k_)
|
|
end k_
|
|
say ' 'iv.space(1, ',').changestr(',', ', ')
|
|
say
|
|
|
|
say 'Find the 3 largest:'
|
|
iv = ''
|
|
loop k_ = items - 2 to items
|
|
iv = iv qselectInPlace(buildIndexedString(samplelist), k_)
|
|
end k_
|
|
say ' 'iv.space(1, ',').changestr(',', ', ')
|
|
say
|
|
|
|
return
|
|
|
|
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
|
|
method buildIndexedString(samplelist) private static
|
|
list = 0
|
|
list[0] = samplelist.words()
|
|
loop k_ = 1 to list[0]
|
|
list[k_] = samplelist.word(k_)
|
|
end k_
|
|
return list
|