Sort multiple arrays simultaneously "in place"

Question

I have the following 3 arrays:

int[] indexes = new int[]{0,2,8,5};
String[] sources = new String[]{"how", "are", "today", "you"};
String[] targets = new String[]{"I", "am", "thanks", "fine"};

I want to sort the three arrays based on the indexes:

indexes -> {0,2,5,8}
sources -> {"how", "are", "you", "today"}
targets -> {"I", "am",  "fine",  "thanks"}

I can create a new class myClass with all three elements:

class myClass {
    int x;
    String source;
    String target;
}

Reassign everything to myClass, then sort myClass using x. However, this would required additional spaces. I am wondering if it is possible to do in place sorting? Thanks!

Answer 1

Three ways of doing this

1. Using Comparator (Need Java 8 plus)

import java.io.*;
import java.util.*;

class Test {

public static String[] sortWithIndex (String[] strArr, int[] intIndex )
    {
     if (! isSorted(intIndex)){
        final List<String> stringList = Arrays.asList(strArr);
        Collections.sort(stringList, Comparator.comparing(s -> intIndex[stringList.indexOf(s)]));
        return stringList.toArray(new String[stringList.size()]);
       }
     else
        return strArr;
    }

public static boolean isSorted(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        if (arr[i + 1] < arr[i]) {
            return false;
        };
    }
    return true;
}       


// Driver program to test function.
    public static void main(String args[])
    {
        int[] indexes = new int[]{0,2,8,5};
        String[] sources = new String[]{"how", "are", "today", "you"};
        String[] targets = new String[]{"I", "am", "thanks", "fine"};   
        String[] sortedSources = sortWithIndex(sources,indexes);
        String[] sortedTargets = sortWithIndex(targets,indexes);
        Arrays.sort(indexes);
        System.out.println("Sorted Sources " + Arrays.toString(sortedSources) + " Sorted Targets " + Arrays.toString(sortedTargets)  + " Sorted Indexes " + Arrays.toString(indexes));
    }
}

Output

Sorted Sources [how, are, you, today] Sorted Targets [I, am, fine, thanks] Sorted Indexes [0, 2, 5, 8]

2. Using Lambda (Need Java 8 plus)

import java.io.*;
import java.util.*;

public class Test {

public static String[] sortWithIndex (String[] strArr, int[] intIndex )
    {

  if (! isSorted(intIndex)) {
        final List<String> stringList = Arrays.asList(strArr);
        Collections.sort(stringList, (left, right) -> intIndex[stringList.indexOf(left)] - intIndex[stringList.indexOf(right)]);
        return stringList.toArray(new String[stringList.size()]);
  }
  else 
    return strArr;
    }

public static boolean isSorted(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        if (arr[i + 1] < arr[i]) {
            return false;
        };
    }
    return true;
}  

// Driver program to test function.
public static void main(String args[])
{
    int[] indexes = new int[]{0,2,5,8};
    String[] sources = new String[]{"how", "are", "today", "you"};
    String[] targets = new String[]{"I", "am", "thanks", "fine"};   
    String[] sortedSources = sortWithIndex(sources,indexes);
    String[] sortedTargets = sortWithIndex(targets,indexes);
    Arrays.sort(indexes);
    System.out.println("Sorted Sources " + Arrays.toString(sortedSources) + " Sorted Targets " + Arrays.toString(sortedTargets)  + " Sorted Indexes " + Arrays.toString(indexes));
}

}

3. Using Lists and Maps and avoiding multiple calls (as in second solution above) to the method to sort individual arrays

import java.util.*;
import java.lang.*;
import java.io.*;

public class Test{

    public static <T extends Comparable<T>> void sortWithIndex( final List<T> key, List<?>... lists){
        // input validation
        if(key == null || lists == null)
            throw new NullPointerException("Key cannot be null.");

        for(List<?> list : lists)
            if(list.size() != key.size())
                throw new IllegalArgumentException("All lists should be of the same size");

        // Lists are size 0 or 1, nothing to sort
        if(key.size() < 2)
            return;

        // Create a List of indices
        List<Integer> indices = new ArrayList<Integer>();
        for(int i = 0; i < key.size(); i++)
            indices.add(i);

        // Sort the indices list based on the key
        Collections.sort(indices, new Comparator<Integer>(){
            @Override public int compare(Integer i, Integer j) {
                return key.get(i).compareTo(key.get(j));
            }
        });

        Map<Integer, Integer> swapMap = new HashMap<Integer, Integer>(indices.size());
        List<Integer> swapFrom = new ArrayList<Integer>(indices.size()),
                      swapTo   = new ArrayList<Integer>(indices.size());

        // create a mapping that allows sorting of the List by N swaps.
        for(int i = 0; i < key.size(); i++){
            int k = indices.get(i);
            while(i != k && swapMap.containsKey(k))
                k = swapMap.get(k);

            swapFrom.add(i);
            swapTo.add(k);
            swapMap.put(i, k);
        }

        // use the swap order to sort each list by swapping elements
        for(List<?> list : lists)
            for(int i = 0; i < list.size(); i++)
                Collections.swap(list, swapFrom.get(i), swapTo.get(i));
    }

    public static void main (String[] args) throws java.lang.Exception{

      List<Integer> index = Arrays.asList(0,2,8,5);
      List<String> sources = Arrays.asList("how", "are", "today", "you");
      // List Types do not need to be the same
      List<String> targets  = Arrays.asList("I", "am", "thanks", "fine");

      sortWithIndex(index, index, sources, targets);

      System.out.println("Sorted Sources " + sources + " Sorted Targets " + targets  + " Sorted Indexes " + index);


    }
}

Output

Sorted Sources [how, are, you, today] Sorted Targets [I, am, fine, thanks] Sorted Indexes [0, 2, 5, 8]

Answer 2

It is possible although it is not that easy than it looks like. There are two options:

1. write your own sort algorithm where the swap function for two elements also swaps the elements in the other arrays.

   AFAIK there is no way to extend the standard Array.sort in a way that it swaps additional arrays.

2. Use a helper array with the sort order.

   • First of all you need to initialize the helper array with the range {0, 1 ... indexes.Length-1}.

   • Now you sort the helper array using a Comparator that compares indexes[a] with indexes[b] rather than a to b. The result is an helper array where each element has the index of the element of the source array where its content should come from, i.e. the sort sequence.

   • The last step is the most tricky one. You need to swap the elements in your source arrays according to the sort sequence above.
     To operate strictly in place set your current index cur to 0.
     Then take the cur-th element from your helper array. Let's call it from. This is the element index that should be placed at index cur after completion.
     Now you need to make space at index cur to place the elements from index from there. Copy them to a temporary location tmp.
     Now move the elements from index from to index cur. Index from is now free to be overridden.
     Set the element in the helper array at index cur to some invalid value, e.g. -1.
     Set your current index cur to from proceed from above until you reach an element in the helper array which already has an invalid index value, i.e. your starting point. In this case store the content of tmp at the last index. You now have found a closed loop of rotated indices.
     Unfortunately there may exist an arbitrary number of such loops each of arbitrary size. So you need to seek in the helper array for the next non-invalid index value and again continue from above until all elements of the helper array are processed. Since you will end at the starting point after each loop it is sufficient to increment cur unless you find an non-invalid entry. So the algorithm is still O(n) while processing the helper array. All entries before cur are necessarily invalid after a loop completed.
     If curincrements beyond the size of the helper array you are done.

3. There is an easier variation of option 2 when you are allowed to create new target arrays.
   In this case you simply allocate the new target arrays and fill their content according to the indices in your helper array.
   The drawback is that the allocations might be quite expensive if the arrays are really large. And of course, it is no longer in place.

---

Some further notes.

• Normally the custom sort algorithm performs better as it avoids the allocation of the temporary array. But in some cases the situation changes. The processing of the cyclic element rotation loops uses a minimum move operations. This is O(n) rather than O(n log n) of common sort algorithms. So when the number of arrays to sort and or the size of the arrays grows the method #2 has an advantage because it uses less swap operations.

• A data model requiring a sort algorithm like this is mostly broken by design. Of course, like always there are a few cases where you can't avoid this.