OK, taking in to consideration that memory footprint is a concern, then there is some scope for improvement. First, lets get through some of the basics....
Firstly, your code has a bug, It fails to sort data with duplicates:
'w','a','t','e','r','c','a','t','-','-','b','a','l','l','-','f','i','v','e','-','b','a','l','l','-','-'
Your code sorts the above as:
[b, a, l, l, -, c, a, t, -, -, f, i, v, e, -, w, a, t, e, r, b, a, l, l, -, -]
Secondly, your example data has an extra '-' at the end. Is this intentional?
Then, let's discuss the trade-offs between a few different concepts....
- Using Strings allows us to use pre-built algorithms for sorting.
Arrays.sort
uses heavily optimized code (TimSort) to get the data sorted fast, but, we will have an expensive O(n)
cost to convert the data first.
- Additionally this will have a significant memory impact (significantly more than double the memory will be required).
- an in-between solution may be possible. We can create a custom object, say
CharRange
which represents a range in the base array. We can make this CharRange class Comparable
. Then, we can create a CharRange instance for each word in the class, and sort the results. With the sorted results we can 'swap' the actual data to match the sorted results. This is more memory efficient than String, and has the advantage of using the native Collections.sort() algorithms. The drawback is that it does use memory, and the 'post-swap' algorithm will be 'fiddly'.
Taking things to the other extreme, we can sort the data in-place, and not use any additional memory overhead.... but we will have to implement our own sort.
Our sort will be slower than the native sort, but, we will not have the overhead of creating Objects....
So, I have played with your code, and wrapped it in a quick-sort algorithm.... (your mileage may vary, buyer beware, use at your own risk, etc.)....
Some notes:
- There is no apparent need for both
mBlockSize
and mTotalBlocks
. The one can be calculated without the other (assuming that there is not more than mBlockSize bytes of 'padding' at the end of the data).
- The qsort algorithm shuffles through the data in steps of mBlockSize.
- I have used my own swap-in-place method, I don't like the two-levels of method-call you added to your code.
char[] mInput = {'w','a','t','e','r','c','a','t','-','-','b','a','l','l','-','f','i','v','e','-','b','a','l','l','-','-'};
int mBlockSize = 5;
int mTotalBlocks = 4;
public void init(char[] input, int blockSize, int totalBlocks)
{
mInput = input;
mBlockSize = blockSize;
mTotalBlocks = totalBlocks;
}
public char[] qsort() {
// find the start of the right-most character block...
// this could be: qsortRecurse(0, mBlockSize * (totalBlocks - 1));
qsortRecurse(0, mBlockSize * (mInput.length / mBlockSize - 1));
return mInput;
}
public void qsortRecurse(final int lbound, final int rbound) {
final int pivot = lbound;
int left = lbound + mBlockSize;
int right = rbound;
if (right <= left) {
return;
}
while (left <= right) {
while (left <= right && compareBytes(left, pivot) <= 0) {
left += mBlockSize;
}
while (left <= right && compareBytes(pivot, right) < 0) {
right -= mBlockSize;
}
if (left < right) {
swapInPlace(left, right);
}
}
swapInPlace(pivot, right);
qsortRecurse(lbound, right - mBlockSize);
qsortRecurse(left + mBlockSize, rbound);
}
private void swapInPlace(int a, int b) {
char temp;
for (int i = 0; i < mBlockSize; i++) {
temp = mInput[a + i];
mInput[a + i] = mInput[b + i];
mInput[b + i] = temp;
}
}
private int compareBytes(final int a, final int b) {
int i = 0;
while (i < mBlockSize && mInput[a + i] == mInput[b + i]) {
i++;
}
return i == mBlockSize ? 0 : (mInput[a + i] - mInput[b + i]);
}