Given a set of objects that have 2 values. Sort the set by first value and then with second value

For instance:

{2,3},{1,2},(2,2},{3,1},{2,1} to {1,2},{2,1},{2,2},{2,3},{3,1} 

That's what I think:

Do a merge sort in the first column of values. Scroll through the set to see if there are duplicate values ​​in the first column. If there is, paste them into the list.

Combine the sorting of this list in the second column, and then combine them into the main set. Although this seems practical, it seems too complicated. This should work in O(NlogN) , so if anyone can think of a faster / same complexity algorithm, which is also easier, submit it!

Thanks!

+4
source share
3 answers

Just implement a Comparator<T> that compares any two objects of your type, first comparing the first field and then moving on to the second if the first fields are equal. Then you can copy the set into a list, call Collections.sort and provide it with a list and your comparator. You do not need to sort by yourself.

The comparator will be something like this:

 public class TwoFieldComparator implements Comparator<Foo> { public int compare(Foo first, Foo second) { // TODO: null checks int firstComparison = Integer.compare(first.x, second.x); return firstComparison != 0 ? firstComparison : Integer.compare(first.y, second.y); } } 

Alternatively, you can make your class implement Comparable<T> in the same way.

+5
source

What you need to do is perform stable sorting in the second column, and then again in the first column.

If a range of numbers can be determined, O (N) can be achieved using some linear sorting.

EDIT:

Take 'merge sort' as an example (stable for it):
1, Run the merge sort in the second column, then the pairs of numbers will be sorted according to the value of the second column.
2. Run the merge sort again in the first column, pairs of pairs will be ordered in the order of the first column value. However, since the sort method is stable, this means that if the first number is the same, the second number will also be sorted (we did this in the first sort).

So the num pair array is in order. No more action required.
The merge sort is O (NlogN), so 2 * O (NlogN) is still O (NlogN).

EDIT2:
Well, I could make this problem difficult. Even if the sorting method is necessary in order to be implemented by itself while the data structure has been determined, the most suitable way is to use the Jon Skeet comparison code in the corresponding part of the manual sorting method.

+2
source

As you mentioned in one of your suggestions, this is an interview question. John Skeet's solution shows that you don’t have to worry about having two values ​​in your element - just use the right comparator.

Assuming you are asked to do so in 2011, it would be nice to find out how your species is intended to be used. Depending on the environment in which this view will be used, you may consider parallel processing (using multiple threads). This may affect your choice of sorting algorithm.

0
source

Source: https://habr.com/ru/post/1346341/


All Articles