
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




Task

Sort an integer array with the   radix sort algorithm.

The primary purpose is to complete the characterization of sort algorithms task.




/* NetRexx */
options replace format comments java crossref symbols nobinary
 
runSample(arg)
return
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method radixSort(tlist = Rexx[]) public static returns Rexx[]
 
  -- scale the array to start at zero to allow handling of -ve values
  parse getLimits(tlist) maxn minn maxl .
  tlist = rescale(tlist, minn)
 
  loop px = maxl to 1 by -1
    bukits = ''
    loop ix = 0 to tlist.length - 1
      cval = tlist[ix].right(maxl, 0)
      parse cval . =(px) digit +1 .
      bukits[digit] = bukits[digit] (cval + 0) -- simulates a stack
      end ix
    intermediates = ''
    loop bi = 0 to 9
      intermediates = intermediates bukits[bi] -- sumulates unstack
      end bi
    -- reload array
    loop iw = 1 to intermediates.words()
      tlist[iw - 1] = intermediates.word(iw)
      end iw
    end px
 
  -- restore the array to original scale
  tlist = rescale(tlist, -minn)
  return tlist
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method rescale(arry = Rexx[], newbase) private static returns Rexx[]
  loop ix = 0 to arry.length - 1
    arry[ix] = arry[ix] - newbase
    end ix
  return arry
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method getLimits(arry = Rexx[]) private static returns Rexx
  maxn = 0
  minn = 0
  maxl = 0
  loop i_ = 0 to arry.length - 1
    maxn = maxn.max(arry[i_])
    minn = minn.min(arry[i_])
    end i_
  maxl = (maxn - minn).length()
  return maxn minn maxl
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method runSample(arg) private static
  lists = [-
    [2, 24, 45, 0, 66, 75, 170, -802, -90, 1066, 666], -
    [170, 45, 75, 90, 2, 24, 802, 66], -
    [10, 9, 8, 7, 8, 5, 4, 3, 2, 1, 0], -
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10], -
    [-10, -9, -8, -7, -8, -5, -4, -3, -2, -1, -0], -
    [-0, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10], -
    [-10, -19, -18, -17, -18, -15, -14, -13, -12, -11, -100], -
    [10, 9, 8, 7, 8, 5, 4, 3, 2, 1, 0, -0, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10], -
    [-10, -9, -8, -7, -8, -5, -4, -3, -2, -1, -0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] -
  ]
 
  loop il = 0 to lists.length - 1
    tlist = lists[il]
    say ' Input:' Arrays.asList(tlist)
    say 'Output:' Arrays.asList(radixSort(tlist))
    say
    end il
  return
 