/* 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