CODEWITHSUNDEEP
javaarrayssorting
haierophanto
haierophanto

Reputation: 51

How to build an array of indexes which represent values of different array from the highest to the lowest?

The title may be a bit confusing so here's an instance. I have two arrays:

int [] scores;
scores = new int[5];  //(5,7,10,3,6)
int [] places;
places = new int[5];  //(1,2,3,4,5)

I need to somehow sort the second array (I can't change the first one), so it represents the highness of elements in the first array. 10 is the highest so its place has to be 1st, 3 is the lowest so its place has to be 5th.

After the sorting second array should look like this:

places = {4,2,1,5,3};

Here's my code, and I need some help to make it work the way it should.

do {
    for (int i = 0; i < 5; i++) {
        for (int j = 1; j < 5; j++) {
            if (scores[i] < scores[j]) {
                temp = places[i];
                places[i] = places[j];
                places[j] = temp;
                flag = true;
            } else {
                flag = false;
            }
        }
    }
} while (flag);

Thanks in advance

Upvotes: 1

Views: 81

Answers (2)

Timor
Timor

Reputation: 579

@Korashen adviced a pretty good solution,

Another way: assume all the values of scores are different and positive, you can make a copy of the array,sort it, and by subtaction to know the indexes,

in your example:

before sorting : scores = (5,7,10,3,6)

after sorting : scores_sorted = (3,5,6,7,10)

the value of places will be by the following rule:

if(scores_sorted[i]-scores[j] == 0) places[i] = j

full example:

int[] scores = new int[]{5, 7, 10, 3, 6};
int[] scores_sorted = scores.clone();
int[] places = new int[]{0,1,2,3,4};
sort(scores_sorted);
for(int i=0;i<5;++i){
    for(int j=0;j<5;++j){
        if(scores_sorted[i]-scores[j] == 0){
             places[i] = j;
          }
     }
}

Upvotes: 4

josejuan
josejuan

Reputation: 9566

You can use any sorting algorithm over the places but, instead comparing the places, compare the scores indexed by places.

Here is the modified quickSort:

static int partition(int[] iarray, int[] varray, int begin, int end) {
    int pivot = end;

    int counter = begin;
    for (int i = begin; i < end; i++) {
        if (varray[iarray[i]] < varray[iarray[pivot]]) {
            int temp = iarray[counter];
            iarray[counter] = iarray[i];
            iarray[i] = temp;
            counter++;
        }
    }
    int temp = iarray[pivot];
    iarray[pivot] = iarray[counter];
    iarray[counter] = temp;

    return counter;
}

public static void quickSort(int[] iarray, int[] varray, int begin, int end) {
    if (end <= begin) return;
    int pivot = partition(iarray, varray, begin, end);
    quickSort(iarray, varray, begin, pivot - 1);
    quickSort(iarray, varray, pivot + 1, end);
}

The only change is add the varray argument and the comparison iarray[i] < iarray[pivot] to varray[iarray[i]] < varray[iarray[pivot]].

NOTE: places must be numbers from 0 to n - 1.

If places are keys instead indexes, you need an intermediate Map to convert the varray[iarray[i]] to varray[real_index_of.get(iarray[i])].

A running example could be:

int[] scores = new int[]{5, 7, 10, 3, 6};
int[] places = new int[]{0, 1, 2, 3, 4};
quickSort(places, scores, 0, places.length - 1);
System.out.println(Arrays.stream(scores).mapToObj(Integer::toString).collect(joining(", ")));
System.out.println(Arrays.stream(places).mapToObj(Integer::toString).collect(joining(", ")));

With output:

5, 7, 10, 3, 6
3, 0, 4, 1, 2

(your output is wrong since 5 is the second lowest value)

Upvotes: 0

Related Questions