How to sort multiple arrays in java

Question

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!

Answer 1

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)).

Answer 2

Since Record, Color and Clothes seem to belong together, I would suggest moving them together in a custom Object, eg

public class ClothesItem {
    int record;
    String color;
    String clothes;
}  

Then you can make different Comparators to do the different variants of sorting.

If you need to preserve your current structure with multiple arrays, @Jherico has a sorting solution here that gets an array of the sorted indexes, which should make it trivial to get to your wanted result.

Answer 3

Alright, here's what it looks like in final form.

// ColorClothes.java

import java.util.*;


public class ColorClothes
{
public int record;
public String color;
public String clothes;

public static void main(String[] args)
{
    Initialize();
}

public ColorClothes(int record, String color, String clothes)
{
    this.record = record;
    this.color = color;
    this.clothes = clothes;
}

public static void Initialize()
{
    List<ColorClothes> list = new ArrayList();
    list = CreateList();

    Sort(list, "Unsorted", 1);
    Sort(list, "\nSortedByColor", 2);
    Sort(list, "\nSortedByClothes", 3);
    Sort(list, "\nSortedByRecord", 4);
}


public static List<ColorClothes> CreateList()
{
    List<ColorClothes> list = new ArrayList();
    list.add(new ColorClothes(1, "blue  ", "shoes"));
    list.add(new ColorClothes(0, "yellow", "pants"));
    list.add(new ColorClothes(3, "red   ", "boots"));
    list.add(new ColorClothes(2, "black ", "coat"));

    return list;
}

public static void Print(List<ColorClothes> list)
{
    for (ColorClothes item : list)
    {
        System.out.println(item.record + "    " + item.color + "   " + item.clothes);
    }
}

public static void Sort(List<ColorClothes> list, String string, int choice)
{
    System.out.println(string + "\n");

    switch (choice)
    {
    case 1:
        break;
    case 2:
        Collections.sort(list, new ColorComparator());
        break;
    case 3:
        Collections.sort(list, new ClothesComparator());
        break;
    case 4:
        Collections.sort(list, new RecordComparator());
        break;
    }

    Print(list);
}

} // End class.

---

// ColorComparator.java

import java.util.Comparator;

 class ColorComparator implements Comparator
 {
public int compare(Object str1, Object str2)
{
    String str1Color = ((ColorClothes)str1).color;
    String str2Color = ((ColorClothes)str2).color;

    return str1Color.compareTo(str2Color);

}
}// End class.

---

// ClothesComparator.java

import java.util.Comparator;


class ClothesComparator implements Comparator
{
public int compare(Object str1, Object str2)
{
    String str1Clothes = ((ColorClothes)str1).clothes;
    String str2Clothes = ((ColorClothes)str2).clothes;

    return str1Clothes.compareTo(str2Clothes);

}
} // End class.

---

// RecordComparator.java

import java.util.Comparator;


public class RecordComparator implements Comparator 
{
public int compare(Object rec1, Object rec2)
{
    int rec1Rec = ((ColorClothes)rec1).record;
    int rec2Rec = ((ColorClothes)rec2).record;

    if(rec1Rec > rec2Rec)
    {
        return 1;
    }
    else if(rec1Rec < rec2Rec)
    {
        return -1;
    }
    else
    {
        return 0;
    }
}
}// End class.

Console Output

Unsorted

1    blue     shoes
0    yellow   pants
3    red      boots
2    black    coat

SortedByColor

2    black    coat
1    blue     shoes
3    red      boots
0    yellow   pants

SortedByClothes

3    red      boots
2    black    coat
0    yellow   pants
1    blue     shoes

SortedByRecord

0    yellow   pants
1    blue     shoes
2    black    coat
3    red      boots

Answer 4

I am not sure about sorting multiple arrays at once; looking at the use case used by you this looks like a contender where all 3 attributes can be combined into an object and then the array of objects can be sorted in multiple ways.

Are you sure that you need to have 3 arrays?

Does an array of ColoredCloth would work for you like:

class ColoredCloth implements Comparable<ColoredCloth>{
    int id;
    String color;
    String cloth;
}

and define a couple of Comparators to sort by color and cloth.

Answer 5

Sort the arrays in-directly. Index all your arrays and sort only the index-array of the desired array. Take a look at the solution in this SO post. This will keep your arrays consistent. I'm not sure if it's easy to extrapolate this to sorting N-arrays in sync though, but it should give you an idea of how to approach the problem in case you want to stick with having your data distributed in multiple arrays. As several people already pointed out, grouping the data in a single object is a good approach.

Answer 6

Here is how I sort two or more string arrays of the same length, so that the first array is in order and the other arrays match that order:

public static void order(String[]... arrays)
{
    //Note: There aren't any checks that the arrays
    // are the same length, or even that there are
    // any arrays! So exceptions can be expected...
    final String[] first = arrays[0];

    // Create an array of indices, initially in order.
    Integer[] indices = ascendingIntegerArray(first.length);

    // Sort the indices in order of the first array's items.
    Arrays.sort(indices, new Comparator<Integer>()
        {
            public int compare(Integer i1, Integer i2)
            {
                return
                    first[i1].compareToIgnoreCase(
                    first[i2]);
            }
        });

    // Sort the input arrays in the order
    // specified by the indices array.
    for (int i = 0; i < indices.length; i++)
    {
        int thisIndex = indices[i];

        for (String[] arr : arrays)
        {
            swap(arr, i, thisIndex);
        }

        // Find the index which references the switched
        // position and update it with the new index.
        for (int j = i+1; j < indices.length; j++)
        {
            if (indices[j] == i)
            {
                indices[j] = thisIndex;
                break;
            }
        }
    }
    // Note: The indices array is now trashed.
    // The first array is now in order and all other
    // arrays match that order.
}

public static Integer[] ascendingIntegerArray(int length)
{
    Integer[] array = new Integer[length];
    for (int i = 0; i < array.length; i++)
    {
        array[i] = i;
    }
    return array;
}

public static <T> void swap(T[] array, int i1, int i2)
{
    T temp = array[i1];
    array[i1] = array[i2];
    array[i2] = temp;
}

If you want to do this with arrays of other types then you will need to refactor this somewhat. Alternatively, for an integer array to be sorted along with string arrays you could convert the integers to strings.

Answer 7

I suggest you to create a class as below

class Dress {
  public int record;
  public String color;
  public String clothes;
}

Maintain the list of dresses as below

List<Dress> dressCollection = new ArrayList<Dress>();

Implement comparator based on color and clothes.

List<Dress> resultBasedOnColor = Collections.sort(dressCollection, new Comparator<Dress>() {
   public int compareTo(Dress obj1, Dress obj2) {
     return obj1.color.compareTo(obj2.color);
 }

});

Left sorting based on clothes as exercise for question owner.

Answer 8

Put the data into a custom class like @SiB:

class ColoredClothes {
    int id;
    String color;
    String cloth;
}

Then, put each instance of this class into a TreeMap with the color as the key (or cloth name depending what you want to sort by):

TreeMap<String,ColoredClothes> sortedCloth= new TreeMap<String,ColoredClothes>();
//loop through arrays and put new ColoredClothes into Map

Then get the sorted values like so:

Collection<ColoredClothes> values = sortedCloth.values();

You can iterate through these in order by using values.iterator()

Answer 9

Thanks for the help guys.

I was so fixed on using arrays and sorting those arrays (since that's what was required of me), that I didn't even think about creating objects instead.

With this simple program, it'll allow you to create an object and sort the fields within the object. The colors and clothes were just an example I was using.

Here's my completed code below:

// ColorClothes.java

import java.util.*;


public class ColorClothes
{
public int record;
public String color;
public String clothes;

public static void main(String[] args)
{
    Initialize();
}

public static void Initialize()
{
    ColorClothes item[] = new ColorClothes[4];

    item[0] = new ColorClothes();
    item[0].record = 0;
    item[0].color = "blue";
    item[0].clothes = "shoes";

    item[1] = new ColorClothes();
    item[1].record = 1;
    item[1].color = "yellow";
    item[1].clothes = "pants";

    item[2] = new ColorClothes();
    item[2].record = 2;
    item[2].color = "red";
    item[2].clothes = "boots";

    item[3] = new ColorClothes();
    item[3].record = 3;
    item[3].color = "black";
    item[3].clothes = "coat";

    System.out.println("Unsorted");

    for(int i = 0; i < item.length; i++)
    {
        System.out.println(item[i].record + "     " + item[i].color + "     " + item[i].clothes);
    }

    System.out.println("\nSorted By Color\n");

    Arrays.sort(item, new ColorComparator());

    for(int i = 0; i < item.length; i++)
    {
        System.out.println(item[i].record + "     " + item[i].color + "     " + item[i].clothes);
    }

    System.out.println("\nSorted By Clothes\n");

    Arrays.sort(item, new ClothesComparator());

    for(int i = 0; i < item.length; i++)
    {
        System.out.println(item[i].record + "     " + item[i].color + "     " + item[i].clothes);
    }

}

}// End class.

// ColorComparator.java

import java.util.Comparator;

class ColorComparator implements Comparator
{
public int compare(Object str1, Object str2)
{
    String str1Color = ((ColorClothes)str1).color;
    String str2Color = ((ColorClothes)str2).color;

    return str1Color.compareTo(str2Color);

}
}// End class.

// ClothesComparator.java

import java.util.Comparator;


class ClothesComparator implements Comparator
{
public int compare(Object str1, Object str2)
{
    String str1Clothes = ((ColorClothes)str1).clothes;
    String str2Clothes = ((ColorClothes)str2).clothes;

    return str1Clothes.compareTo(str2Clothes);

}
} // End class.

Console Output

Unsorted
0     blue     shoes
1     yellow     pants
2     red     boots
3     black     coat

Sorted By Color

3     black     coat
0     blue     shoes
2     red     boots
1     yellow     pants

Sorted By Clothes

2     red     boots
3     black     coat
1     yellow     pants
0     blue     shoes

I'll add another Comparator to allow sorting by record/integers later. I'll also condense the code more so it's not one big block, but I'm almost done with work for the day.

Answer 10

As others suggested, easier would be to sort collection of objects instead of sorting three arrays synchronously.

If, for whatever reason you have to stick to sorting multiple arrays, following approach could be used - idea is to implement own variant of arrays list, which is backed by three arrays instead of one.

import java.util.AbstractList;
import java.util.Collections;

public class SortMultipleArrays extends AbstractList {

    //object representing tuple from three arrays
    private static class ClothesItem implements Comparable<ClothesItem> {
        int record;
        String color;
        String clothes;

        public ClothesItem(int record, String color, String clothes) {
            this.record = record;
            this.color = color;
            this.clothes = clothes;
        }

        @Override
        public int compareTo(ClothesItem o) {
            return this.color.compareTo(o.color); //sorting by COLOR
        }
    }

    private int[] records;
    private String[] colors;
    private String[] clothes;

    public SortMultipleArrays(int[] records, String[] colors, String[] clothes) {
        this.records = records;
        this.colors = colors;
        this.clothes = clothes;
    }

    @Override
    public Object get(int index) {
        return new ClothesItem(records[index], colors[index], clothes[index]);
    }

    @Override
    public int size() {
        return records.length;
    }

    @Override
    public Object set(int index, Object element) {
        ClothesItem item = (ClothesItem) element;
        ClothesItem old = (ClothesItem) get(index);

        records[index] = item.record;
        colors[index] = item.color;
        clothes[index] = item.clothes;

        return old;
    }

    public static void main(String[] args) {
        int[] record = {0,1,2,3};
        String[] colors = {"blue", "yellow", "red", "black"};
        String[] clothes = {"shoes", "pants", "boots", "coat"};

        final SortMultipleArrays multipleArrays = new SortMultipleArrays(record, colors, clothes);
        Collections.sort(multipleArrays);

        System.out.println("Record  Color   Clothes");
        for (int i = 0; i < record.length; i++) {
            System.out.println(String.format("%8s %8s %8s", record[i], colors[i], clothes[i]));
        }
    }
}

This implementation is based on AbstractList which makes it easier to implement List interface needed for Collections.sort(...).

Note that there may be inefficiency hidden in this implementation: both get(...) and set(...) methods are creating instance of wrapper object which may cause too many object created when sorting bigger arrays.

Answer 11

Liked @bcorso's idea of creating swapping lists to sort any other List. Here's a bit more optimized version, that uses only 2 arrays instead of a Map and 3 ListArrays, and only swaps indexes that need swapping:

public static <T extends Comparable<T>> void syncedSort(final List<T> key, List<?>... lists) {
    // Create an array of indices
    Integer[] indices = new Integer[key.size()];
    for (int i = 0; i < indices.length; i++)
        indices[i] = i;

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

    // Scan the new indices array and swap items to their new locations,
    // while remembering where original items stored.
    // Only swaps can be used since we do not know the type of the lists
    int[] prevSwaps = new int[indices.length];
    for (int i = 0; i < indices.length; i++) {
        int k = indices[i];
        while (i > k)
            k = prevSwaps[k];
        if (i != k) {
            prevSwaps[i] = k;
            for (List<?> list : lists)
                Collections.swap(list, i, k);
        }
    }
}

Answer 12

import java.util.Arrays;

Arrays.sort (int [])
Arrays.sort (String [])

this will sort array of Strings.