Radix sorting of natural numbers array. Automatic generation of vizualizer's logic


Main distinctive feature of this algorithm is that instead of comparing elements we divide each element to sequence of fields. Before sorting it is necessary to know two parameters: k and m, where k is quantity of digits in the longest key, and m is quantity of possible field values. In the presented vizualizer key length is four digits and, and m equals ten, because sorting is performed on decimal numbers. Let's say that elements of array A (displayed at the top row of visualizer) are k-digit decimal numbers. d(j,n) is j-th digit of number n from the right, B (displayed at the bottom row of visualizer) is additional array, that is empty in the beginning, and counter (displayed at the middle row of visualizer) is array of counters of size m, filled with zeros. For every j = 1, 2,..., k we should do the following steps:

     1. Iterate over array A, increasing value of counter with index d(j,n) at every step.
     2. Iterate over array counter, writhing into every cell a sum of all previous elements of this array. This sum equals quantity of numbers in original array that will be placed to the left of number, containing in j-th place a digit, that equals index of this counter. Therefore, we found a place for this number in the results array.
     3. Copy into array B values of elements of array A. Value of n-th element of A goes into cell with index counter[d(j,n)]. Because values of j-th digit of elements of A can repeat in array, we should increase value of corresponding counter by one each time we copy value. After array B is filled with numbers all elements from it should be copied into A. After that we should move to next value of j.


Author: Ponomarev A.I. Visualization technology: Korneev G.A. Supervisor: Shalyto A.A.

Saint-Petersburg university of information technologies, mechanics and optics.
Computer technologies department

Copyright 2003 by Anton Ponomarev