CODEWITHSUNDEEP
c++algorithm
ysyugeee
ysyugeee

Reputation: 71

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

We have an unsorted array, need to print the position of each element assuming that it gets sorted.

e.g.: we have an array.

arr[] = {3, 2, 6, 1, 4}
//index: 1  2  3  4  5  Index of elements 1-based

//Sorted {1, 2, 3, 4, 6}  List after sorting
//index:  4  2  1  5  3  Index of elements from original array

it should print

4 2 1 5 3

Upvotes: 7

Views: 5173

Answers (6)

Jarod42
Jarod42

Reputation: 217275

You may use the following:

template <typename T>
std::vector<std::size_t> compute_ordered_indices(const std::vector<T>& v)
{
    std::vector<std::size_t> indices(v.size());
    std::iota(indices.begin(), indices.end(), 0u);
    std::sort(indices.begin(), indices.end(), [&](int lhs, int rhs) {
        return v[lhs] < v[rhs];
    });
    return indices;
}

Live Demo

Upvotes: 0

Mohit Jain
Mohit Jain

Reputation: 30489

Store the data and index of array element as a pair and sort the array of pairs. Now print only the index part.

// Original array
int arr[] = {3, 2, 6, 4};
// Size of original array
const int sz = static_cast<int>(sizeof arr / sizeof arr[0]);
// Array of pair {.first = item, .second = 1-based index
std::vector< pair<int, int> > vp(sz); // std::array if size is fixed
for(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 */
// Sort the array, original array remains unchanged
std::sort(vp.begin(), vp.end());
// Print the result
for(int i = 0; i < sz; ++i) cout << ' ' << vp[i].second;

Live code

Time complexity of the code: O(N log N) where N is the number of elements in the array

From you comment as the value of N is large and all numbers are distinct, you can use the following snippet

int maxn = maximum value of a number;
int positions[maxn] = {0};  // Or choose a sparse array with constant update time
int arr[] = {3, 2, 6, 4};
const int sz = static_cast<int>(sizeof arr / sizeof arr[0]);
for(int i = 0; i < sz; ++i) {
  assert( arr[i] >= 0 );
  position[ arr[i] ] = i + 1;
}

for(int i = 0; i < maxn; ++i) {
  if(position[i]) cout << ' ' << position[i];
}

Live code

Time complexity of the code: O(N) where N is the maximum value of the number

Upvotes: 4

smttsp
smttsp

Reputation: 4191

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.

struct node{
     int value;
     int pos;
}

As I said, it will work but I doubt it is the most efficient way

Upvotes: 1

Edward Doolittle
Edward Doolittle

Reputation: 4100

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.

In case that isn't clear, here's a longer example:

5 2 1 4 3
1 2 3 4 5

2 5 1 4 3
2 1 3 4 5

2 1 5 4 3
2 3 1 4 5

2 1 4 5 3
2 3 4 1 5

2 1 4 3 5
2 3 4 5 1

2 1 3 4 5
2 3 5 4 1

1 2 3 4 5
3 2 5 4 1

I 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.

Upvotes: 6

Pavan Kumar K
Pavan Kumar K

Reputation: 1376

I don't know C++, so I cannot give you the exact code, but the below pseudo code should work.

1. Given input array
2. Take another empty array of equal length (This will be the output array of positions)
3. Fill the output array with zero (initially all values will be zero in the array)
4. while (output array does not contain zero)
    a. loop through input array and find maximum number in it.
    b. get the position of maximum number from input array and set it at the same position in output array
    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)
5. Repeat setps a,b and c until all the elements in output array becomes non zero

The complexity of this algorithm is O(n2). I did not find a better way than this. Please let me know, if you have any queries.

Upvotes: 0

Pham Trung
Pham Trung

Reputation: 11284

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

int arr[] = {3, 2, 6, 4};

int compare (const void * a, const void * b) {
    int diff = arr[*(int*)a] - arr[*(int*)b];
    return  diff;
}

int main(void) {
    int perm[4], i;

    for (i = 0 ; i != 4 ; i++) {
        perm[i] = i ;
    }
    qsort (perm, 4, sizeof(int), compare);

    for (i = 0 ; i != 4 ; i++) {
        printf("%d ", perm[i] + 1);
    }
    return 0;
}

Output:

2 1 4 3

Link http://ideone.com/wH1giv

Upvotes: 3

Related Questions