Sort ArrayList mixed integers and strings while maintaining relative ordering of strings and integers

Question

Consider the below arraylist

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

it needs to be sorted by

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

Sort strings alphabetically. Sort numbers in ascending order. But pay attention to the following condition:

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

Note that in the above example, all integers are sorted in ascending order, and all strings are sorted in ascending order, but the relative positions of integers and strings are not changed earlier.

Answer 1

One option is as follows:

• Create a new list of all integers in the source list.
• Create a new list of all the lines in the source list.
• Sort each list.
• Go to the source list by following these steps:
  • If the element has an integer, write the next unwritten integer from the list of sorted integers.
  • If the item has a row, write the next unwritten row from the list of sorted rows.

This is quite effective - you just need to do two kinds. Here is the 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

Pseudocode:

 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