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

# Thread: Find the the original indices of the sorted aray

1. ## 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]+" ");```

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

3. ## 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. ## 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.