Indexing an array

Hi, I am hoping that someone can help me with a relatively simple array sorting problem.

I have one array of 4 double elements e.g. {3, 8, 5, 2}

The position of each element in the array has meaning e.g. the value 5 belongs to "machine 3" (as the 3rd element in the array - position 0 = "machine 1")

I need to create a second array that contains the positions of the values in the array above in ascending order e.g. {3, 0, 2, 1}

I can't touch the first array - it must remain as it is.

Could someone perhaps give me some demo code?


Thank you for reading :WAVE:

I'm not sure what your "ascending order" is because I don't see an ascending order ...

If you are re-ordering based on position, you can do something like:

Code:

---

void arrayCopy( array1, array2 ) (or whatever...)
{
    while (array1 still has members you have not copied)
    {
      array2[0] = array1[3];
      array2[1] = array1[1];
      etc.;
    }
}

---

If you are sorting the actual values just use array2 = Arrays.sort( array1);

Hi nspils, thanks for your answer, I guess that my question was not sufficiently clear though - here's an attempt at a better explanation of what I'm trying to do:

I have a read-only array. Lets assume that this array contains the following {5, 2, 8, 9, 3}

What I need is a second array that contains the positions of the values in the first array. The ordering of these positions in the second array must be according to the assending values of the elements in the first. For example:

The element of value '2' in the first array is at position 1 whereas the element of value '3' is at position 4. As the value of the element at position 1 is lower than the value at position 4, the second array to be constructed would be {1, 4, ...}

Therefore, the complete array that I want to construct would read: {1, 4, 0, 2, 3}.

Could you give me a code snippet for that?

Thanks :)

Is this a course assignment? You'll learn more trying to do the coding yourself.
Not much talent required for copy and pasting.

Write out in words the steps needed to do your search/sort and then try to write the program. Then come back with questions if you are having problems.

No, it's not a course assignment. It's something that I have had a go at and not succeded with.

Here's an approach. Use the second array as the index to the first one. Initialize the second array with values from 0 to number elements - 1. Sort the first array using the contents of the second array as indexes. When swapping two elements, change the values(the indexes) in the second array instead of the values in the first array.

Create a map (you can use the TreeMap class, which will sort the keys in their natural order as you insert the pairs) - the key of each key-value pair is the value in your array1, the value of the pair is the index of that value in array1. Now create an array by extracting the new "values" into your new array ...

[Later - added by my edit]

It looks like you can use the TreeMap's values() method to return a Collection object, and you can use the toArray() method of the Collection object to create your new array, which will be in sorted order.

hi,

We can have one more approach,

Just apply the selection sort method(in ascending order) on 1st array and note down the positions while sorting the array ( Normally we note-down the element values to sort the array).
I think this will solve your problem, you need to know only how selection sort works.

thankx

Thankyou for your answers. The Map approach is one that I considered earlier but it gets very messy casting from ints and doubles to Integer and Double objects - I end up createing loads of different objects for a simple index array. Unfortunatly the suggested array-based approaches simply won't work as far as I can find. Any sort rely upon maipulation of the array being sorted (even if I use the second array as the index) breaks because the sort can't continue on the second array (in any meaningful way) because the elements that have supposadly be supported so far have remained exactly the same.

My own solution is as follows:

Code:

---

private void order() {
                for (int i = 0; i < 4; i++) {
                        double currentValue = rate[i];
                        int positionToPlace = 0;
                        for (int j = 0; j < 4; j++)
                                if (currentValue > rate[j] & (j != i))
                                        positionToPlace++;
                        order[positionToPlace] = i;
                }
        }

---

Sadly this is also broken as assuming I try to sort the following array {5, 2, 4, 5} I end up with a second array that reads: {1, 2, 3, NULL} as both of the elements of value 5 think that they belong at the same location. What I want of course is an array that reads {1,2,3,0} or {1,2,0,3} - it doesn't matter which.

Does anyone have any thoughts on this?

Are you using Java 5? The "autoboxing" feature is supposed to take care of the conversion from a base data type to an object (int to Integer, double to Double) for you ... Set the expected datatypes of your TreeMap<Double, Integer> and see what happens ... compare with TreeMap<double,int> if it will let you ...

The creation of an object from the base data type to store it in the TreeMap does not seem like such a mess to me if I were forced to doing it by hand - especially since this seems like the "best" way to conquer your challenge. Couldn't you just do:

Code:

---

TreeMap< Double, Integer > myTree = new TreeMap<Double, Integer>();
int value;
double key;
Integer V;
Double K;

for (int i = 0; i<array1.size(); i++)
{
----------------------------
for pre 1.5 ...
    value = i;
    V = new Integer( i );
    key = array1[i];
    K = new Double( key );
    myTree.put( V, K );
 ---------------------------
if autoboxing is working, just
    myTree.put( array1[i], i );
---------------------------
}

---

then use the new "for-loop" to walk through the values in the TreeMap to populate your array2

In fact, you are right, this method does work. The problem occurs when it comes to trying to create an array from the TreeMap.
I tried using a vector but had to jump through all kinds of hoops to get the casts working properly. Finally, when I thought that everything was set - I found that array2 was only full of null values - somewhere in all the conversions something is going wrong :(

Just go through the code once, I wrote it in a haste, so it is not an optimized implementation.

Code:

---

import java.util.*;

public class ValSort
{
        public static void main( String s[] )
        {
                //read only input
                int input[] = {5, 2, 8, 9, 3};
                int ans[] = getAnswer( input );
               
               
                for( int count = 0; count < ans.length; count++ )
                {
                        System.out.println( ans[ count ] );
                }
        }
       
        private static int[] getAnswer( final int[] input )
        {               
                int out[] = new int[ input.length ];
                int copy[] = new int[ input.length ];
               
                for( int count = 0; count < input.length; count++ )
                {
                        copy[ count ] = input[ count ];
                }
               
                Arrays.sort( copy );
               
                //any idea why I am doing this :)
                int ignore_value = copy[ 0 ] -1;

                int counter = 0;
               
                for( int outer = 0; outer < copy.length; outer++ )
                {
                        for( int inner = 0; inner < input.length; inner++ )
                        {
                                if( copy[ outer ] == input[ inner ] )
                                {
                                        copy[ outer ] = ignore_value;
                                        out[ counter ] = inner;
                                        counter++;
                                        break;
                                }
                        }
                }
               
                return out;
        }
}

---

Regards,
Mohit

mohit,
Thanks for your example code, it is very educational but.... (I really feal that I'm being a nag now) in fact it works exactly the same as mine: e.g. it doesn't actually work as needed!

Try sorting an array with 2 identical values such as {19, 2, 7, 19}

You will find that the output is {1, 2, 0, 0} instead of the desired {1, 2, 3, 0} or {1, 2, 0, 3}.

This is the fundemental problem that I can't solve. It also seems to have foxed everyone else, perhaps the problem is not so simple as I thought?

I guess that perhaps some kind of temporary variable could watch to test if a similar value to the current element being sorted has already been encounterd. But I don't know how you could apply that to an array that had potentially multiple duplicates e.g. {19, 19, 19, 19} !

This works - just a tiny tweak needed.
Thanks to everyone who replied, you've all been great :)

Code:

---

import java.util.*;

public class ValSort {
        public static void main(String s[]) {
                // read only input
                int input[] = { 19, 2, 7, 19 };
                int ans[] = getAnswer(input);

                for (int count = 0; count < ans.length; count++) {
                        System.out.println(ans[count]);
                }
        }

        private static int[] getAnswer(final int[] input) {
                int out[] = new int[input.length];
                int sortedCopy[] = new int[input.length];
                int unsortedCopy[] = new int[input.length];

                for (int count = 0; count < input.length; count++) {
                        sortedCopy[count] = input[count];
                        unsortedCopy[count] = input[count];
                }

                Arrays.sort(sortedCopy);

                int ignore_value = sortedCopy[0] - 1;

                int counter = 0;

                for (int outer = 0; outer < sortedCopy.length; outer++) {
                        for (int inner = 0; inner < unsortedCopy.length; inner++) {
                                if (sortedCopy[outer] == unsortedCopy[inner]) {
                                        unsortedCopy[inner] = ignore_value;
                                        out[counter] = inner;
                                        counter++;
                                        break;
                                }
                        }
                }

                return out;
        }
}

---

Very small logical error, this will work perfectly

Code:

---

import java.util.*;

public class ValSort
{
        public static void main( String s[] )
        {
                //read only input
                int input[] = {5, 2, 5, 9, 3};
                int ans[] = getAnswer( input );
               
               
                for( int count = 0; count < ans.length; count++ )
                {
                        System.out.println( ans[ count ] );
                }
        }
       
        private static int[] getAnswer( final int[] input )
        {               
                int out[] = new int[ input.length ];
                int copy[] = new int[ input.length ];
               
                for( int count = 0; count < input.length; count++ )
                {
                        copy[ count ] = input[ count ];
                }
               
                Arrays.sort( copy );
               
                //any idea why I am doing this :)
                int ignore_value = copy[ 0 ] -1;

                int counter = 0;
               
                for( int outer = 0; outer < copy.length; outer++ )
                {
                        for( int inner = 0; inner < input.length; inner++ )
                        {
                                if( (copy[ outer ] == input[ inner ]) )
                                {
                                        copy[ outer ] = ignore_value;
                                        input[ inner ] = ignore_value;
                                        out[ counter ] = inner;
                                        counter++;
                                        break;
                                }
                        }
                }
               
                return out;
        }
}

---