Indexing an array


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 15 of 17

Thread: Indexing an array

Hybrid View

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


    Thank you for reading

  2. #2
    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. #3
    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. #4
    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. #5
    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. #6
    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. #7
    Join Date
    Oct 2005
    Posts
    1

    Smile 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. #8
    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. #9
    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. #10
    Join Date
    Oct 2005
    Posts
    40

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

  11. #11
    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. #12
    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[]) {
    		// 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;
    	}
    }

  13. #13
    Join Date
    Oct 2005
    Posts
    40

    Arrow Use this

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

  14. #14
    Join Date
    Oct 2005
    Posts
    8
    Quote 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. #15
    Join Date
    Oct 2005
    Posts
    40

    Lightbulb copy it

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

Similar Threads

  1. Replies: 2
    Last Post: 04-15-2005, 09:06 PM
  2. Replies: 3
    Last Post: 04-08-2005, 05:49 AM
  3. Accessing jagged array values
    By Jason Salas in forum ASP.NET
    Replies: 2
    Last Post: 04-20-2003, 11:39 PM
  4. SafeArrayCopy SLOWER than iterating string array!
    By Mark Alexander Bertenshaw in forum VB Classic
    Replies: 10
    Last Post: 06-16-2000, 05:34 AM
  5. SafeArrayCopy SLOWER than iterating string array!
    By Mark Alexander Bertenshaw in forum VB Classic
    Replies: 0
    Last Post: 06-12-2000, 08:15 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center