java: sort array1 based on array2

Question

Thanks for the help from Zirak In my previous post i implemented the following in JavaScript:

var arr1 =[0,1,2,3];
var arr2 =["ac", "bc", "ad", "e"];
var result = arr1 .sort(function(i, j){return arr2[i].localeCompare(arr2[j])})
document.write(result );

The way to achieve this is quite compact in JavaScript, can a java implementation of this be also achieved by such simplicity? I could only think of implementing the Comparable interface like the following:

public class testCompare {
    public static String[] arr2={"ac", "bc", "ad", "e"};
    public static Obj[] arr1={new Obj(0), new Obj(1), new Obj(2), new Obj(3)};
    static class Obj implements Comparable{
            int index=0;
            public Obj(int i){
                    index=i;
            }
            @Override
            public int compareTo(Object o) {
                    return arr2[index].compareTo(arr2[((Obj)o).index]);
            }
     }
}

but if the array have X many items, then I will have to create X many Objs, is there another way that I could achieve this more simply? Another question is, if I do the above method what would be the time complexity for the sorting both in java and in JavaScript, are they all O(n^2)? Thanks a lot

JB Nizet · Accepted Answer · 2011-05-05 13:49:25Z

4

public class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer i1, Integer i2) {
        return arr2[i1.intValue()].compareTo(arr2[i2.intValue()]);
    }
}

Arrays.sort(arr1, new MyComparator());

This is the equivalent of the JavaScript sort. The Comparator object is used as the callback function is used in JavaScript.

answered May 5, 2011 at 13:49

JB Nizet

694k94 gold badges1.3k silver badges1.3k bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Haider Over a year ago

I don't understand this. Aren't i1 and i2 the values of arr1, you are treating them as indexes of arr1.

JB Nizet Over a year ago

@Haider yes, that's what the OP asked. When comparing 1 and 2, he wants to compare "bc" and "ad", because "bc" is at index 1 and "ad is at index 2.

Haider Over a year ago

@JBNizet thanks, I just realized I asked a very stupid question.

Thomas · Accepted Answer · 2011-05-05 14:02:00Z

3

Try using a TreeMap<String, Integer> (assuming you want to sort integers) which means all entries are sorted by their string key:

SortedMap<String, Integer> map = new TreeMap<String, Integer>();
map.put("ac", 0);
map.put("bc", 1);
map.put("ad", 2);
map.put("e", 3);

for( Map.Entry<String, Integer> entry : map.entrySet() )
{
  System.out.println(entry.getKey() + " - " + entry.getValue());
}

Output:

ac - 0
ad - 2
bc - 1
e - 3

To sort an array and get the new order of the previous indices you could iterate over the array and add the indices as Integer objects to the map:

String[] input = {"ab", "bc", "ad" , "e" };
SortedMap<String, Integer> map = new TreeMap<String, Integer>();
for( int i = 0; i < input.length; ++i )
{
  map.put(input[i], i); //or use values from another array, e.g. map.put(inputKeys[i], inputValues[i]);
}

If you need to sort the keys by anything else but the natural order, you can add a Comparator<String> to the TreeMap constructor.

edited May 5, 2011 at 14:02

answered May 5, 2011 at 13:53

Thomas

88.9k13 gold badges127 silver badges162 bronze badges

2 Comments

user685275 Over a year ago

Thanks for answering, appreciate it.

Ken Williams Over a year ago

One important note: if you have any duplicate entries in the original array, they will be lost in this approach, represented only by the last entry with that value.

Archit Garg · Accepted Answer · 2015-07-26 20:57:18Z

public class SortA1byA2array 
{
public static void main (String[] args) 
{
int[] arr1={2,1,2,5,7,1,9,8,3,6,8,8};       
int[] arr2={2,1,8,3};   
TreeMap hm=new TreeMap();   
int count=1;
        for(int i=0;i<arr1.length;i++){
            if(hm.containsKey(arr1[i])){
                hm.put(arr1[i], ++count);
            }
            else{
                count=1;
                hm.put(arr1[i],count);
            }
        }


        for(int i=0;i<arr2.length;i++){
            if(hm.containsKey(arr2[i])){
                for(int j=0;j<(Integer)hm.get(arr2[i]);j++){
                    System.out.println(arr2[i]);
                }
                hm.remove(arr2[i]);
            }
        }

         Iterator it = hm.entrySet().iterator();
            while (it.hasNext()) {
                Map.Entry pairs = (Map.Entry)it.next();
                System.out.println(pairs.getKey());
                it.remove(); 
            }
    }
}

dcn · Accepted Answer · 2011-05-05 13:52:49Z

0

In response to the second part of you question: Arrays.sort in Java has guaranteed O(n log n) time complexity, as specified in the API.

answered May 5, 2011 at 13:52

dcn

4,4693 gold badges32 silver badges40 bronze badges

2 Comments

Voo Over a year ago

Yep. Internally java is using a QuickSort with an insertion sort for the leaf nodes.

dcn Over a year ago

@Voo: afaik this is not true: 1) API says, the actual algorithm depends on the specific implementation, and at least on my machine it uses a version of merge sort 2) quicksort does not guarantee O(n log n), rather has a worst case running time of O(n^2)

Collectives™ on Stack Overflow

java: sort array1 based on array2

4 Answers 4

3 Comments

2 Comments

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

2 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related