radix sort


See On Github

Data

Source Code

// Patrick Yevsukov

// 2013 CC BY-NC-SA 4.0 http://patrick.yevsukov.com

// github.com/PatrickYevsukov/Sorting-Algorithms

package PatrickYevsukov;

import java.util.ArrayList;

public class radix_sort {

    public static void RadixSort(ArrayList<Integer> list) {

        final int NUM_BASE = 10;

        int maximum = 0;

        ArrayList<ArrayList<Integer>> buckets;

        buckets = new ArrayList<ArrayList<Integer>>(NUM_BASE);

        // New buckets are added to the bucket list; one for each digit
        // in the numeral system of the data being sorted.

        for (int ii = 0; ii < NUM_BASE; ii++) {

            buckets.add(new ArrayList<Integer>());
        }

        // Identifying the list item with the most place values.

        for (int ii = 0; ii < list.size(); ii++) {

            if (list.get(ii) > maximum) {

                maximum = list.get(ii);
            }
        }

        // List items are sorted by place value. The place value is
        // multiplied by the numeric base with each pass of the loop.

        for (int power = 1; maximum / power != 0; power *= NUM_BASE) {

            for (int ii = 0; ii < list.size(); ii++) {

                // List items are added to the bucket which corresponds
                // to the place value which they are being sorted by.

                buckets.get(list.get(ii) / power % NUM_BASE).add(list.get(ii));
            }

            int index = 0;

            for (int ii = 0; ii < buckets.size(); ii++) {

                for (int jj = 0; jj < buckets.get(ii).size(); jj++) {

                    // The buckets, sorted by the current place value
                    // under consideration, have their values written
                    // back to original list, overwriting its previous
                    // contents.

                    list.set(index, buckets.get(ii).get(jj));
                    
                    index++;
                }
            }

            // At the end of each pass of the loop, the contents of the
            // buckets are dumped out.

            for (int ii = 0; ii < buckets.size(); ii++) {

                buckets.get(ii).clear();
            }
        }
    }
    
// Above is my implementation of a radix sort. I 
// wrote it to be as human readable as possible.

}
// Patrick Yevsukov

// 2013 CC BY-NC-SA 4.0 http://patrick.yevsukov.com

// github.com/PatrickYevsukov/Sorting-Algorithms

package PatrickYevsukov;

import java.util.Random;

import java.util.ArrayList;

public class radix_sort_test {
    
    private static Random random;
    
    private static final int COLUMNS = 9;

    private static final int VAL_COUNT = 10;
    
    private static final int TRUNCATE = 10000000;
    
    private static ArrayList<Integer> randomDataList;

    public static void main(String[] args) {

        TestRadixSort();
    }

    public static void TestRadixSort() {

        random = new Random();
        
        randomDataList = GenRandomArrayList();

        
        System.out.print("Unsorted List:\t");

        PrintArrayList(randomDataList);
        

        radix_sort.RadixSort(randomDataList);

        
        System.out.print("Sorted List:\t");

        PrintArrayList(randomDataList);

    }

    public static ArrayList<Integer> GenRandomArrayList() {

        ArrayList<Integer> ints = new ArrayList<Integer>(VAL_COUNT);

        for (int ii = 0; ii < VAL_COUNT; ii++) {

            ints.add(Math.abs(random.nextInt() / TRUNCATE));
        }

        return ints;
    }

    public static <T> void PrintArrayList(final ArrayList<T> ints) {

        for (int ii = 0; ii < ints.size(); ii++) {

            System.out.print(ints.get(ii) + "\t");

            if ((ii % (COLUMNS + 1)) == COLUMNS) {

                System.out.println();
            }
        }

        System.out.println();
    }
}