### Sort a byte array in Java

The default algorithm used to sort a byte array is Arrays.sort(byte [] array). The algorithm used is a quicksort (complexity about =(nlog(n))). It is good for objects, but we have seen it is far better to use a countingsort algorithm.

Here is the code used:

If there is less than 45 elements we have found that creating new arrays takes to much time and that the countingsort algorithm is not good enough.

The factor (sun sort)/countingsort has been calculated for some size of arrays. With 80 elements, the couting sort is about 50% faster. At 1280 elements, the couting sort algorithm is 4 times faster.

Here is the code used:

public static void sort(byte toSort[], int offset, int length) {

//If we have less than this number of elements, we do the

//default sort else we use the countingsort algorithm

if (length < 45) {

Arrays.sort(toSort, offset, length);

return;

}

//It can go faster if we keep in memory an other array,

// but the class has to be synchronized.

//We initialize a new array

int temp [] = new int[256];

Arrays.fill(temp, 0);

//Count the number of elements

for (int i = offset; i < offset + length; i++) {

temp[toSort[i] + 128]++;

}

byte value = -128;

int ind = 0;

//Insert the bytes in the good order

for (int i = offset; i < offset + length;) {

while (temp[ind] == 0) {

ind++;

value++;

}

for (int j = 0; j < temp[ind]; j++) {

toSort[i++] = value;

}

value++;

ind++;

}

}

If there is less than 45 elements we have found that creating new arrays takes to much time and that the countingsort algorithm is not good enough.

The factor (sun sort)/countingsort has been calculated for some size of arrays. With 80 elements, the couting sort is about 50% faster. At 1280 elements, the couting sort algorithm is 4 times faster.

## 0 Comments:

Post a Comment

<< Home