Can you store multiple integers at one array index?

Question

I'm trying to do a radix sort and some algorithms I've seen have a buckets[ ] array that's supposed to hold multiple integers into one index of the bucket array, here is the algorithm I'm referring to:

Is it really possible to have multiple integers in one index? And how so?
Or is there a simpler radix sort algorithm out there?

Answer 1

Yes, it is possible to add multiple int to an array, but you would need to have an array where each item is an Object rather than an int.

For example...

// the items to store in the array, which contain 3 ints
public class Bucket {
    int number1 = -1;
    int number2 = -1;
    int number3 = -1;

    public void addInt(int number){
        if (number1 == -1){
            number1 = number;
        }
        else if (number2 == -1){
            number2 = number;
        }
        else if (number3 == -1){
            number3 = number;
        }
    }
}

// the array, as used in other classes
Bucket[] bArray = new Bucket[6]; // 6 items in the array, where each item is a Bucket that contains 3 ints

// assigning ints into the array
bArray[2].addInt(56); // add the int '56' to the bucket at index '2' of the array

// You could also use other Array-like structures
ArrayList<Bucket> bList = new ArrayList<Bucket>();

Of course, if you don't always have <=3 items in a bucket, you could just change the Bucket class to use an array or a List as its variable rather than separate ints.

You could also use multi-dimensional arrays...

// creating the buckets
int[][] buckets = new int[6][3];

// assigning ints into the array
bArray[2][0] = 56; // add the int '56' to the bucket at index '2' of the array, position '0'

It would get a little messy, however, if you start playing around with different-sized buckets, and you'd need to do more error-checking to ensure that...

1. The items in the bucket aren't empty when you try to access them
2. When you're adding a number to a bucket, you need to detect the next position in the second dimension that is empty, so you don't overwrite the ints that are already in there.

If is for these reasons why I would recommend using an Object-based array over a multi-dimensional array.

Answer 2

Two cases create buckets

• the numbers aren't unique
• radix sort sorts on each digit position (ones, tens, hundreds in the decimal case) before going on to the next one - so 003 and 019 if sorting on the first digit will match.

The first case is really just a degenerate case of the second.

Note that there are a couple of radix sort variants depending on which order you sort the digits in.

Too answer the data structure part of the question - no you can't and wouldn't store multiple values at each index. Instead, each bucket is typically represented as a sub-sequence of the array. Each bucket is then represented by the offset of its start (the end can be implicit).

Answer 3

a bucket would be an int[] (or List or anything that can store multiple items) itself.

You can't put more that one thing into 1 index.

int[] array = new array[6];
int value = array[5];

would no longer work if there was more than one int.

The easiest is probably to use an int[][] array. Now each index in the left box refers to a whole array. Those arrays can be different length too:

Java Jagged Array

Answer 4

In addition to the possibility of representing a bucket as a List or array, it is possible to use an array slice. In this case, the destination array is the same total size as the input array. For the example, you have 2 elements in bucket 0, 2 in bucket 1, 3 in bucket 2, 1 in bucket 3, and 2 in bucket 5.

Bucket 0 : d[0], d[1]
Bucket 1 : d[2], d[3]
Bucket 2 : d[4], d[5], d[6]
Bucket 3 : d[7]
Bucket 5 : d[8], d[9]

Doing it this way, the sort has to track the next index for each bucket.

Answer 5

Wow, array's and lists are not the way to implement a radix sort. Yes lists work, but it slows it down, when I did that, it was slower than a merge sort. Best way is to implement a frequency array as part of a counting sort per each byte. I posted my code here, only in reference to parallel sorting. Hope it helps.