
Sorting Algorithm

This is a sorting algorithm.   It may be applied to a set of data in order to sort it.    
For comparing various sorts, see compare sorts.  
For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts
Heap sort |
Merge sort |
Patience sort |
Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort


Use the quickselect algorithm on the vector

 [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]
To show the first, second, third, ... up to the tenth largest member of the vector, in order, here on this page.

 Note: Quicksort has a separate task. 


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