Radix Sort In JAVA

Introduction

 

In today's article, we discuss the Radix Sort In Java.

 

Radix Sort in Java

 

A Radix Sort is a type of bucket sort. This type of sort is based on a radix. Arrays are sorted in a total of "d" passes where "d" is the number of digits of the highest number. In computer science, a Radix Sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits that share the same significant position and value. A multiple-pass distribution sort algorithm that distributes each item to a bucket according to part of the item's key beginning with the least significant part of the key. After each pass, items are collected from the buckets, keeping the items in order, then redistributed according to the next most significant part of the key.

 

For decimal number: In the first pass the array is sorted by the units digit, then in the next pass it is sorted by the tens digit and so on. This process goes on until all the digits of the highest numbers are traversed.

For words: In the first pass the array is sorted by the first letter, and in the second pass the second character is considered and so on.

 

Positional notation is required, but because integers can represent strings of characters (e.g., names or dates) and specially formatted floating-point numbers, a Radix Sort is not limited to integers.

 

Code Description

 

A Radix Sort is an algorithm that sorts a list of numbers and is in the distribution sort category. This sorting algorithm doesn't compare the numbers but distributes them, it works as follows:

1. Sorting takes place by distributing the list of number into a bucket by passing through the individual digits of a given number one-by-one.
2. Beginning with the least significant digit (1st place). Here, the number of buckets is a total of ten (0 to 9).
3. Now start by arranging the values as in the example. The least value comes first and so on in increasing order.
4. After the first pass move to next digit (10s place).
5. Arrange those values in increasing order.
6. After each pass, the numbers are collected from the buckets, keeping the numbers in order.
7. Now, recursively redistribute the numbers as in the step "1" above but with the following reconsideration: use the next most significant part of the number, that is then followed by step "2" above.

An example

 

Original, unsorted list:

155, 34, 76, 80, 502, 150, 20, 4

 

Sorting by the least significant digit (1s place) gives:

80, 150, 20, 502, 34, 4, 155, 76

 

Sorting by the next digit (10s place) gives: 

4, 502, 20, 34, 150, 155, 76, 80

 

Sorting by the most significant digit (100s place) gives a sorted array:

4, 20, 34, 76, 80, 150, 155, 502

 

It is important to realize that each of the steps above requires just a single pass over the data since each item can be placed in its correct bucket without having to be compared with other items.

 

Some LSD Radix Sort implementations allocate space for buckets by first counting the number of keys that belong in each bucket before moving keys into those buckets.

 

The number of times that each digit occurs is stored in an array.

 

Consider the previous list of keys viewed in a different way:

 

155, 034, 076, 080, 502, 150, 020, 004

 

The first counting pass starts on the least significant digit of each key, producing an array of bucket sizes:

 

3 (bucket size for digits of 0: 080, 150, 020)

1 (bucket size for digits of 2: 502)

2 (bucket size for digits of 4: 034, 004)

1 (bucket size for digits of 5: 155)

1 (bucket size for digits of 6: 076)

 

A second counting pass on the next more significant digit of each key will produce an array of bucket sizes:

 

2 (bucket size for digits of 0: 004, 502)

1 (bucket size for digits of 2: 020)

1 (bucket size for digits of 3: 034)

2 (bucket size for digits of 5: 150, 155)

1 (bucket size for digits of 7: 076)

1 (bucket size for digits of 8: 080)

 

A third and final counting pass on the most significant digit of each key will produce an array of bucket sizes:

 

5 (bucket size for digits of 0: 004, 020, ,034, 076, 080)

2 (bucket size for digits of 1: 150, 155)

1 (bucket size for digits of 5: 502)

 

At least one LSD Radix Sort implementation now counts the number of times that each digit occurs in each column for all columns in a single counting pass. (See the external links section.) Other LSD Radix Sort implementations allocate space for buckets dynamically as space is needed.

 

A Radix Sort can be particularly effective on a linked list. Rather than buckets, put items in linked lists. At the end of a pass collect the items by "sewing" the lists together; make the tail of each list point to the head of the next list.

 

Algorithm of Radix Sort

 

Every algorithm always depends on the input. Now we see that the effectiveness of algorithms depends greatly on the input. For input that is almost sorted, an Insertion Sort may be preferred instead of a Quicksort, which is generally a faster algorithm. On the other hand, a Quicksort is considered one of the best general-purpose sorting algorithms, but while it's a great algorithm when the data is randomized, it's practically as slow as a Bubble Sort when the input is almost or fully sorted.

 

Because the input is so important for an algorithm's efficiency, we may ask if there are any sorting algorithms that are faster than O(n.log(n)), which is the average-case complexity for a Merge Sort and a Quicksort. And the answer is yes there are faster, linear complexity algorithms, that can sort data faster than a Quicksort, Merge Sort and Heapsort. But there are some constraints!

 

Everything sounds great but we can't sort any particular data with linear complexity, so the question is what rules must the input follow in order to be sorted in linear time?

 

Such an algorithm that is capable of sorting data in linear O(n) time is a Radix Sort and the domain of the input is restricted; it must consist of only integers.

 

Overview

 

Let's say we have an array of integers that is unsorted. It consists only of integers and due to array key integers in programming, we can implement a Radix Sort.

 

First, for each value of the input array we put the value of "1" on the key-th place of the temporary array as explained in the following diagram:

 

 

If there are repeating values in the unsorted array then we increment the corresponding value in the temporary array. After "initializing" the temporary array with one pass (with linear complexity) we can sort the input.

 

 

Example

 

In this program, we use the "math.random" function to make the input random:

public class RadixSortEx {
    public static void main(String[] args) {
        int i;
        int[] n = new int[15];
        System.out.print("Before sorting: ");
        for (i = 0; i < n.length; i++) {
            n[i] = (int)(Math.random() * 1024);
            System.out.print(n[i] + " ");
        }
        initializeredixSort(n);
        System.out.print("\nAfter sorting: ");
        for (i = 0; i < n.length; i++)
            System.out.print(n[i] + " ");
        System.out.println(" ");
    }
}

The method body of our program in which the sorting is performed:

//This method sorts the input array in asecnding order
public static void initializeredixSort(int[] n) {
    if (n.length == 0)
        return;
    int[][] np = new int[n.length][2];
    int[] q = new int[0x100];
    int i, j, k, l, f = 0;
    for (k = 0; k < 4; k++) {
        for (i = 0; i < (np.length - 1); i++)
            np[i][1] = i + 1;
        np[i][1] = -1;
        for (i = 0; i < q.length; i++)
            q[i] = -1;
        for (f = i = 0; i < n.length; i++) {
            j = ((0xFF << (k << 3)) & n[i]) >> (k << 3);
            if (q[j] == -1)
                l = q[j] = f;
            else {
                l = q[j];
                while (np[l][1] != -1)
                    l = np[l][1];
                np[l][1] = f;
                l = np[l][1];
            }
            f = np[f][1];
            np[l][0] = n[i];
            np[l][1] = -1;
        }
        for (l = q[i = j = 0]; i < 0x100; i++)
            for (l = q[i]; l != -1; l = np[l][1])
                n[j++] = np[l][0];
    }
}

Output

 

 

Note: Each time when you run this program you get a different output value (as we are using a random function in our program).