DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

#### Hybrid View

1. Registered User
Join Date
Oct 2005
Posts
8

## 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?

2. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
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);
Last edited by nspils; 10-13-2005 at 03:38 PM.

3. Registered User
Join Date
Oct 2005
Posts
8
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

4. Registered User
Join Date
Jul 2005
Location
SW MO, USA
Posts
299
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.

5. Registered User
Join Date
Oct 2005
Posts
8
No, it's not a course assignment. It's something that I have had a go at and not succeded with.

6. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
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.
Last edited by nspils; 10-13-2005 at 09:34 PM.

7. Registered User
Join Date
Oct 2005
Posts
1

## One way

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

8. Registered User
Join Date
Oct 2005
Posts
8
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?
Last edited by java50031; 10-14-2005 at 11:56 AM.

9. Registered User
Join Date
Jul 2005
Location
SW MO, USA
Posts
299
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.

10. Registered User
Join Date
Oct 2005
Posts
40

## Heres the solutions

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[] )
{
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
Last edited by mohit; 10-15-2005 at 11:56 AM.

11. Registered User
Join Date
Oct 2005
Posts
8
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} !

12. Registered User
Join Date
Oct 2005
Posts
8
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[]) {
int input[] = { 19, 2, 7, 19 };

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;
}
}```

13. Registered User
Join Date
Oct 2005
Posts
40

## Use this

Very small logical error, this will work perfectly
Code:
```import java.util.*;

public class ValSort
{
public static void main( String s[] )
{
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;
}
}```

14. Registered User
Join Date
Oct 2005
Posts
8
Originally Posted by mohit
Very small logical error, this will work perfectly
It will work, but you're now writing to the read-only array! That's why I shoved a third array into my last post.

15. Registered User
Join Date
Oct 2005
Posts
40

## copy it

either pass the input by values, or copy it in another array and perform operations on it.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

 FAQ Latest Articles Java .NET XML Database Enterprise