Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 4 of 4

Thread: Find the the original indices of the sorted aray

  1. #1
    Junior Member
    Join Date
    Aug 2017
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Find the the original indices of the sorted aray

    My unsorted array has values with indices [0 1 2 3 ... array.length]

    2 66 23 61 38 193 31 33 37 30 21 18 36 33 61 80 16 53 6 26 2 21 5 4 8 16 7 11 10 3 1 3 1 1

    After using merge sort, my sorted array is

    1 1 1 2 2 3 3 4 5 6 7 8 10 11 16 16 18 21 21 23 26 30 31 33 33 36 37 38 53 61 61 66 80 193

    My problem is I could not get the original indices of the unsorted array in the order of my sorted array.

    i.e [30 32 33 0 ... 5]

    Regarding my code, I have set a variable pos for current position in the sorted array, ptr2 which compares every value of unsorted array.
    When the value of my sorted array is equal to the value of unsorted array, the code can get the indices then break;.

    However, I do not know what to write when the values of the array has duplicates.

    With this code I am getting the list of indices of:
    30 30 30 0 0 29 29 23 22 18 26 24 28 27 16 16 11 10 10 2 19 9 6 7 7 12 8 4 17 3 3 1 15 5

    The indices should not repeat.

     
    int[]  index=new int[sortedArr.length];
     
     
    for(int pos=0;pos<sortedArr.length;pos++)
    	{			
    		for(int ptr2=0;ptr2<sortedArr.length;ptr2++)
    	     {	
    		 if(sortedArr[pos]==notSortedArr[ptr2])
    		    {
              		  index[pos]=ptr2;	  	  
    			   break;
    		     }
    	     }		
     
    	}
     
    ///print///
    	System.out.print("indices: ");
    	for(int i=0;i<sortedArr.length;i++)
    		 System.out.print(index[i]+" ");
    Last edited by slashGamer; August 5th, 2017 at 02:50 AM.

  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Find the the original indices of the sorted aray

    Can you make a small, complete program that compiles, executes and shows the problem for testing?

    Be sure to add comments to the code describing its logic.
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3

    Default Re: Find the the original indices of the sorted aray

    Before you sort the array use a map to store original indexes of your array elements as follows.

    String[] item = { "B", "C", "D", "A" };
    Map<String, Integer> map = new HashMap<String, Integer>();
    for (int i = 0; i < item.length; i++) {
    map.put(item[i], i);
    }

  4. #4
    Super Moderator pbrockway2's Avatar
    Join Date
    Jan 2012
    Posts
    987
    Thanks
    6
    Thanked 206 Times in 182 Posts

    Default Re: Find the the original indices of the sorted aray

    The problem with a map like this is that the same value can be repeated as a value in the array, but not as the key of a map.

    Attempting to find the original index positions *after* the sort has been done is a little hopeless because that information has been lost. If you didn't really care what order the three indices for the 1's at the start, for example, were reported in I guess you could cobble something together. But it wouldn't be straight forward.

    If I had to sort that original array, 2 66 23 61 38 ..., I would write the index position on the back of the pieces of paper that held the values. Then I would do the sort. Then I would turn the values over one at a time and read off their original index positions.

Similar Threads

  1. close original frame
    By e93 in forum What's Wrong With My Code?
    Replies: 5
    Last Post: April 19th, 2014, 03:07 AM
  2. aray print
    By sainisuresh101 in forum Java Native Interface
    Replies: 1
    Last Post: February 15th, 2014, 04:36 PM
  3. Insert original title here: Hello there!
    By Leetment in forum Member Introductions
    Replies: 0
    Last Post: May 9th, 2012, 02:48 PM
  4. Replies: 1
    Last Post: March 15th, 2010, 10:03 PM