Sorting an ArrayList of mixed integers and strings while preserving relative ordering of strings and integers

Question

Consider an arraylist as given below

unsortedList = {6,"ball",3,1,"apple","cat",4} 

this needs to be sorted to

sortedList = {1,"apple",3,4,"ball","cat",6}

Sort the strings alphabetically. Sort the numbers in ascending. But note the following condition:

• Wherever an integer is there in the unsorted list, it must be an integer in the sorted list.
• Wherever a string is there in the unsorted list, it must be a string in the sorted list.

Notice that in the above example, all the integers are sorted ascending and all the strings are sorted ascending, but the relative positions of integers and strings is unchanged from before.

Answer 1

One option here is to do the following:

• Create a new list of all the integers in the original list.
• Create a new list of all the strings in the original list.
• Sort each list.
• Iterate over the original list, doing the following:
  • If the element there is an integer, write back the next unwritten integer from the sorted integer list.
  • If the element there is a string, write back the next unwritten string from the sorted string list.

This is quite efficient - you just need to do two sorts. Here's some code for it:

public void relativeOrderSort(List<Object> list) {
    /* Create a list of just the integers and just the strings
     * from the original list.
     */
    List<Integer> intList = new ArrayList<Integer>();
    List<String> strList = new ArrayList<String>();
    for (Object obj: list) {
        if (obj instanceof Integer) {
            intList.add((Integer) obj);
        } else if (obj instanceof String) {
            strList.add((String) obj);
        } else {
            throw new IllegalArgumentException("List has a non-int, non-string member.");
        }
    }

    /* Sort the lists. */
    Collections.sort(intList);
    Collections.sort(strList);

    /* Merge the lists back together. */
    int intIndex = 0, strIndex = 0;
    for (int i = 0; i < list.size(); i++) {
        if (list.get(i) instanceof Integer) {
           list.set(i, intList.get(intIndex++));
        } else {
           list.set(i, strList.get(strIndex++));
        }
    }
}

Hope this helps!

Answer 2

Pseudo code:

Create a list of the indices pointing to integers ({0,2,3,6} in your case - indxInt )
Sort the integers  ({6,3,1,4} turns into {1,3,4,6})
Put them back at the locations given by the pointers:
  sorted(indxInt(0)) = 1;
  sorted(indxInt(1)) = 3;
  sorted(3) = 4; // indxInt(2) == 3
  sorted(6) = 6; // indxInt(3) == 6
Repeat for the strings