I have an exercise that asks: "Given an array, get a new one ordered descending (from highest to lowest), but through its indices"; that is, if I have the array [2, 5, 1]
, the function should return an array with the values [1, 0, 2]
. That would correspond to the order in which I must access the indexes of the first array to do it in descending order.
The idea that has occurred to me is to order a copy of the array and store the index that I have ordered in a new array, which will be the one returned, but it does not work. I've tried several other things, but I don't quite understand how it could be done.
import java.util.Arrays;
public class Main
{
public static void main(String[] args) {
final int[] nums = {8, 7, 1, 8};
final int[] sortedIndexes = seleccion(nums);
System.out.println(Arrays.toString(sortedIndexes));
}
public static int[] seleccion(int[] v) {
final int[] array = Arrays.copyOf(v, v.length);
final int[] sortedIndexes = new int[v.length];
Arrays.fill(sortedIndexes, v.length - 1);
int n = v.length;
int posmax;
for (int i = 0; i < n - 1; i++) {
posmax = i;
for (int j = i + 1; j < n; j++) {
if (array[j] > array[posmax]) {
posmax = j;
}
}
permuta(array, sortedIndexes, i, posmax);
}
return sortedIndexes;
}
public static void permuta(int[] array, int[] arrayIndex, int index, int posmax) {
final int tempValue = array[index];
array[index] = array[posmax];
array[posmax] = tempValue;
arrayIndex[posmax] = index;
}
}
The biggest problem with doing the exercise is that I can't use anything other than loops, conditionals, or arrays.
You can do this by "modifying" some sorting algorithm and saving the index changes you make.
In this case I did quicksort and within the only
if
one there is not only changing the indices in the array with the values to sort, but also changing the indices in the array of indices, which is ultimately what you want.In this way, at the end the array returned by
qs(int[])
are the indices that would order the original array, and in passing the array is ordered.The code prints
The asymptotic behavior is
O(n log(n))
, although the spatial behavior becomesO(n)
because we have to save a new array of the indices.Sorry for not explaining everything in detail, you will learn more if you decipher the code by yourself. By the way, you can make the algorithm even more efficient if you use quicksort with 3 partitions (3 partitions of values less than, equal to, and greater than the pivot).
you could try something like this:
Basically there are 3 important steps:
I generate a table that is an array of objects (a dictionary), each object has its position (which would be the index in the original array) and its number (by which we are going to sort initially).
Table when created:
Then I order the objects by their number (number)
Table when sorting by number:
Finally for each object of the previously sorted table. I return its position with a map, which returns a new array with the values [1,0,2].
I hope it will serve you for what you need to do, I remain at your service.