Best way to find position of element in unsorted array after it gets sorted

Sort the array {1, 2, 3, ..., N} in parallel with the given array. So in your example, {3, 2, 6, 4} would be sorted, with every swap affecting that array and the array {1, 2, 3, 4}. The final result would be {2, 3, 4, 6} for the first array and {2, 1, 4, 3} for the second; the latter array is the answer to your question.\n\nIn case that isn't clear, here's a longer example:\n\n5 2 1 4 3\n1 2 3 4 5\n\n2 5 1 4 3\n2 1 3 4 5\n\n2 1 5 4 3\n2 3 1 4 5\n\n2 1 4 5 3\n2 3 4 1 5\n\n2 1 4 3 5\n2 3 4 5 1\n\n2 1 3 4 5\n2 3 5 4 1\n\n1 2 3 4 5\n3 2 5 4 1\n\n\nI used bubble sort :-) to sort the top row, and just swapped the bottom row in parallel with the top row. But the idea should work with any sorting method: just manipulate the bottom row in parallel with the operations (swaps or whatever) you are performing on the top row.",

Store the data and index of array element as a pair and sort the array of pairs. Now print only the index part.\n\n// Original array\nint arr[] = {3, 2, 6, 4};\n// Size of original array\nconst int sz = static_cast<int>(sizeof arr / sizeof arr[0]);\n// Array of pair {.first = item, .second = 1-based index\nstd::vector< pair<int, int> > vp(sz); // std::array if size is fixed\nfor(int i = 0; i < sz; ++i) vp[i] = make_pair(arr[i], i + 1); /* Can be done in a more fancy way using std::transform + lambda */\n// Sort the array, original array remains unchanged\nstd::sort(vp.begin(), vp.end());\n// Print the result\nfor(int i = 0; i < sz; ++i) cout << ' ' << vp[i].second;\n\n\nLive code\n\nTime complexity of the code: O(N log N) where N is the number of elements in the array\n\n\n\nFrom you comment as the value of N is large and all numbers are distinct, you can use the following snippet\n\nint maxn = maximum value of a number;\nint positions[maxn] = {0}; // Or choose a sparse array with constant update time\nint arr[] = {3, 2, 6, 4};\nconst int sz = static_cast<int>(sizeof arr / sizeof arr[0]);\nfor(int i = 0; i < sz; ++i) {\n assert( arr[i] >= 0 );\n position[ arr[i] ] = i + 1;\n}\n\nfor(int i = 0; i < maxn; ++i) {\n if(position[i]) cout << ' ' << position[i];\n}\n\n\nLive code\n\nTime complexity of the code: O(N) where N is the maximum value of the number",

You can create an array perm, which hold the index of the first array arr, and sort this perm array based on the value of arr\n\nint arr[] = {3, 2, 6, 4};\n\nint compare (const void * a, const void * b) {\n int diff = arr[*(int*)a] - arr[*(int*)b];\n return diff;\n}\n\nint main(void) {\n int perm[4], i;\n\n for (i = 0 ; i != 4 ; i++) {\n perm[i] = i ;\n }\n qsort (perm, 4, sizeof(int), compare);\n\n for (i = 0 ; i != 4 ; i++) {\n printf(\"%d \", perm[i] + 1);\n }\n return 0;\n}\n\n\nOutput:\n\n2 1 4 3\n\n\nLink http://ideone.com/wH1giv",

I don't know if it is the most efficient way but I'd create an array of nodes. Each node having value and pos.Then, sort according to value from which you can retrieve the position.\n\nstruct node{\n int value;\n int pos;\n}\n\n\nAs I said, it will work but I doubt it is the most efficient way",

I don't know C++, so I cannot give you the exact code, but the below pseudo code should work.\n\n1. Given input array\n2. Take another empty array of equal length (This will be the output array of positions)\n3. Fill the output array with zero (initially all values will be zero in the array)\n4. while (output array does not contain zero)\n a. loop through input array and find maximum number in it.\n b. get the position of maximum number from input array and set it at the same position in output array\n c. ignore the element in input array ,if corresponding index in output array is not zero (if it is not zero, then it means index is already filled up)\n5. Repeat setps a,b and c until all the elements in output array becomes non zero\n\n\nThe complexity of this algorithm is O(n2). I did not find a better way than this.\nPlease let me know, if you have any queries.",