Sorting strings in a one dimensional array

Question

What are the better solutions possible?

I have a character array with different strings. There is a max size for the strings. In case a string is smaller than max size remaining places are filled with '-'. Sorting has to be done on this.

Example:

maxStringSize = 5

totalStrings = 4

InputArray: w,a,t,e,r, c,a,t,-,-, f,i,v,e,-, b,a,l,l,-,-

outputArray: b,a,l,l,-,-, c,a,t,-,-, f,i,v,e,-, w,a,t,e,r

-

public class QuestionOne {


char[] mInput = {'w','a','t','e','r','c','a','t','-','-','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[] sort()
{

    for(int i=0; i < mTotalBlocks; i++)
    {
        for(int j=i+1; j<mTotalBlocks; j++)
        {
            for(int count = 0; count < mBlockSize; count++ )
            {
                if(mInput[i*mBlockSize+count]>mInput[j*mBlockSize+count])
                {
                    swapBlocks(i,j);
                    break;
                }
                else if(mInput[i*mBlockSize+count]<mInput[j*mBlockSize+count])
                    break;
            }
        }
    }
    return mInput;
}

private void swapBlocks(int blockOne, int blockTwo)
{
    for(int i=0; i<mBlockSize; i++)
    {
        swap(blockOne*mBlockSize+i,blockTwo*mBlockSize+i);
    }
}

private void swap(int one, int two)
{
    char temp = mInput[one];
    mInput[one] = mInput[two];
    mInput[two] = temp;
}

}

What are the better solutions possible?

Answer 1

How about the simple process of converting the chars to separate strings, sorting the Strings, then copying the results back to an array?

It would look something like:

String source = new String(input);
String[] values = new String[input.length / blocksize];
for (int i = 0; i < values.length; i++) {
    values[i] = source.substring(i * blocksize, (i + 1) * blocksize);
}
Arrays.sort(values);
char[] result = new char[values.length * blocksize];
for (int i = 0; i < values.length; i++) {
    System.arraycopy(values[i].toCharArray(), 0, result, i* blocksize, blocksize);
}
return result;

Answer 2

So let's start with the easy things, Java normally uses a modified K&R style with the opening braces on the same line:

function void test() {
    if (someVar) {
        // code
    } else {
        // code
    }
}

---

I don't need to tell you that QuestionOne is a bad class name?

---

char[] mInput = ...

Normally variables don't get prefixes with an identifier that tells you their visibility (and if I'm not mistaken m is normally used for private variables). It hinders only readability, and if you need to use such prefixes for clarity, there's something wrong with your code.

---

public void init(char[] input, int blockSize, int totalBlocks)
{
    mInput = input;
    // ...
}

public char[] sort()
{
    // ...
    return mInput;
}

First, I don't see a reason why this could not be a static helper function instead of a class.

Second, imagine the following code:

char[] input = getInput();
QuestionOne sorter = new QuestionOne();
sorter.init(input, 5, 5);
char[] output = sorter.sort();

Quick, what values do input and output hold?

If your answer was

input holds the unsorted, output the sorted array.

then your answer was wrong. Arrays are passed by reference, so input and output are in fact the same array. That's a problem when it comes to design of the API of this class. Either don't return something.

/**
 * Sorts the given array.
 */
function void sort(char[] input) { // ...

Or return a copy of the array.

/**
 * Returns a sorted copy of the given array.
 */
function char[] sort(char[] input) {
    char[] clone = input.clone(); // Also has caveats!
    return clone;
}

---

Also you could derive the block size from the length of the array and the length of each block.

Answer 3

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]);
    }