I am a newbie in Java. I am trying to sort array arr[] according to the values of array val[] and it should maintain the insertion order.
int arr[] = {2,3,2,4,5,12,2,3,3,3,12};
int val[] = {3,4,3,1,1,2,3,4,4,4,2};
I am using this :
ArrayList <Integer> al = new ArrayList <Integer> () ;
for(int i = 0 ; i < arr.length ; i++)
al.add(arr);
Collections.sort(al , (left , right) -> val[al.indexOf(left)] -
val[al.indexOf(right)])
My output should be
4 5 12 12 2 2 2 3 3 3 3
Your two arrays are different lengths so this fails but if you fix that problem this should work:
static <T extends Comparable<T>> List<Integer> getSortOrder(List<T> list) {
// Ints in increasing order from 0. One for each entry in the list.
List<Integer> order = IntStream.rangeClosed(0, list.size() - 1).boxed().collect(Collectors.toList());
Collections.sort(order, (o1, o2) -> {
// Comparing the contents of the list at the position of the integer.
return list.get(o1).compareTo(list.get(o2));
});
return order;
}
// Array form.
static <T extends Comparable<T>> List<Integer> getSortOrder(T[] list) {
return getSortOrder(Arrays.asList(list));
}
static <T> List<T> reorder(List<T> list, List<Integer> order) {
return order.stream().map(i -> list.get(i)).collect(Collectors.toList());
}
// Array form.
static <T> T[] reorder(T[] list, List<Integer> order) {
return reorder(Arrays.asList(list), order).toArray(list);
}
public void test(String[] args) {
Integer arr[] = {2,3,2,4,5,12,2,3,3,3,12};
Integer val[] = {3,4,3,1,1,2,2,3,4,4,4,2};
List<Integer> sortOrder = getSortOrder(val);
Integer[] reordered = reorder(arr, sortOrder);
System.out.println(Arrays.toString(reordered));
}
The val array seems to be one element longer.
int[] arr = {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12};
int[] val = {3, 4, 3, 1, 1, 2, 2, 3, 4, 4, /*4,*/ 2};
int[] sortedArr = IntStream.range(0, arr.length)
.mapToObj(i -> new int[] {arr[i], val[i]})
.sorted((lhs, rhs) -> Integer.compare(lhs[1], rhs[1]))
.mapToInt(pair -> pair[0])
.toArray();
System.out.println(Arrays.toString(sortedArr));
which results in
[4, 5, 12, 2, 12, 2, 2, 3, 3, 3, 3]
As sorting is stable, one could either do two sorts or combine them:
int[] sortedArr = IntStream.range(0, arr.length)
.mapToObj(i -> new int[] {arr[i], val[i]})
.sorted((lhs, rhs) -> Integer.compare(lhs[0], rhs[0]))
.sorted((lhs, rhs) -> Integer.compare(lhs[1], rhs[1]))
.mapToInt(pair -> pair[0])
.toArray();
and then, voila
[4, 5, 2, 12, 12, 2, 2, 3, 3, 3, 3]
.sorted(Comparator.comparing(t -> t[0]))
Just write your sorting algorithm of choice, compare values from val and sort both arr and val accordingly.
Solely for the sake of brevity, here's an example using bubble-sort:
static void sortByVal(int[] arr, int[] val) {
if (arr.length != val.length) { return; }
for (int i=0; i < val.length; i++) {
for (int j=1; j < (val.length-i); j++) {
if (val[j-1] > val[j]) {
int temp = val[j-1];
val[j-1] = val[j];
val[j] = temp;
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
}
Note however that you usually shouldn't resort to reimplementing a sorting algorithm but rather switch to appropriate datastructures.
For instance instead of using a key-array and a values-array, use an array containing key-value pairs. This array can then be sorted easily:
Collections.sort(array, (p0, p1) -> Integer.compare(p0.val, p1.val));
You should look at your logic
val[0] = arr[3] = 4
val[1] = arr[4] = 5
val[2] = arr[3] the value is 4 following your current pattern.
To get 12 the desired value you would have to remove the previously used 4,5
This pattern contradicts what was done at val[1] because 4 was not removed.
