How to sort multiple arrays in java

arrays, java, sorting

Solution

In some cases it doesn't make much sense to create a new class just to do sorting.

Here, is a function that can be used to sort an any number of arbitrarily typed lists (`List<?>`) based on a key list (`List<T implements Comparable>`). Ideone Example here.

Usage

Here is an example of how you can use the function to sort multiple lists of arbitrary types:

List<Integer> ids = Arrays.asList(0, 1, 2, 3);
List<String> colors = Arrays.asList("blue", "yellow", "red", "black");
List<String> clothes = Arrays.asList("shoes", "pants", "boots", "coat");

// Sort By ID
concurrentSort(ids, ids, colors, clothes);

// Sort By Color
concurrentSort(colors, ids, colors, clothes);

// Sort By Clothes
concurrentSort(clothes, ids, colors, clothes);

Output:

// Sorted By ID:
ID:      [0, 1, 2, 3]
Colors:  [blue, yellow, red, black]
Clothes: [shoes, pants, boots, coat]

// Sorted By Color:
ID:      [3, 0, 2, 1]
Colors:  [black, blue, red, yellow]
Clothes: [coat, shoes, boots, pants]

// Sorted By Clothes:
ID:      [2, 3, 1, 0]
Colors:  [red, black, yellow, blue]
Clothes: [boots, coat, pants, shoes]

Code

An Ideone Example can be found here which includes validation of parameters and a test case.

public static <T extends Comparable<T>> void concurrentSort(
                                        final List<T> key, List<?>... lists){
    // 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));
        }
    });

    // Create a mapping that allows sorting of the List by N swaps.
    // Only swaps can be used since we do not know the type of the lists
    Map<Integer,Integer> swapMap = new HashMap<Integer, Integer>(indices.size());
    List<Integer> swapFrom = new ArrayList<Integer>(indices.size()),
                  swapTo   = new ArrayList<Integer>(indices.size());
    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));
}

NOTE: The running time is `O(mlog(m) + mN)` where `m` is the length of the list and `N` is the number of lists. Usually `m >> N` so the running time is not more significant than sorting only the key `O(mlog(m))`.

Problem

I'm trying to sort three arrays by lexicographical order. The arrays are related to each other by a common array. It's easier to explain if I demonstrate: ``` int[] record = new int[4]; String [] colors = {"blue", "yellow", "red", "black"}; String [] clothes = {"shoes", "pants", "boots", "coat"}; ``` When printed on the console, I would like them to be put in three columns similar to below: Unsorted: ``` Record Color Clothes 0 blue shoes 1 yellow pants 2 red boots 3 black coat ``` Sorted by Color: ``` Record Color Clothes 3 black coat 0 blue shoes 2 red boots 1 yellow pants ``` Sorted by Clothes: ``` Record Color Clothes 2 red boots 3 black coat 1 yellow pants 0 blue shoes ``` I found a previous answer similar to my scenario, but it compared integers instead of strings, and I'm having trouble using the `compareTo()` method and `Arrays.sort()` to arrive at my desired output. Any help would be appreciated!

Original source

Related problems