Il modo migliore per trovare la posizione dell'elemento nell'array non ordinato dopo che è stato ordinato

Question

Abbiamo una matrice non ordinata, è necessario stampare la posizione di ogni elemento assumendo che venga ordinato.

ad esempio: abbiamo un 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 

si deve stampare

Answer 1

ordinare l'array {1, 2, 3, ..., N} in parallelo con l'array data. Pertanto, nel tuo esempio, l'ordinamento {3, 2, 6, 4} verrà ordinato, con ogni scambio che interessa quella matrice e l'array {1, 2, 3, 4}. Il risultato finale sarebbe {2, 3, 4, 6} per il primo array e {2, 1, 4, 3} per il secondo; quest'ultimo array è la risposta alla tua domanda.

Nel caso in cui non è chiaro, ecco un esempio più:

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 

Ho usato bubble sort :-) per ordinare la fila superiore, e solo scambiati fila inferiore in parallelo con la fila superiore. Ma l'idea dovrebbe funzionare con qualsiasi metodo di ordinamento: basta manipolare la riga inferiore in parallelo con le operazioni (swaps o qualsiasi altra cosa) che si sta eseguendo nella riga superiore.

Answer 2

È possibile creare un array perm, che tengono l'indice del primo array arr, e ordinare questo array perm in base al valore di 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; 
} 

uscita:

2 1 4 3 

link http://ideone.com/wH1giv

Answer 3

Memorizza i dati e l'indice dell'elemento di matrice come coppia e ordina la matrice di coppie. Adesso stampa solo la parte dell'indice.

// 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

Tempo complessità del codice: O (N log N) dove N è il numero di elementi nella matrice

---

Da voi commentare come il valore di N è grande e tutti i numeri sono distinti, è possibile utilizzare il seguente 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

Tempo complessità del codice: O (N) dove N è il valore massimo del numero

Answer 4

Non so C++, quindi non posso dare il codice esatto, ma la di seguito pseudo codice dovrebbe funzionare.

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 

La complessità di questo algoritmo è O (n2). Non ho trovato un modo migliore di questo. Per favore fatemi sapere se avete domande.

Answer 5

Non so se è il modo più efficiente ma creerei un array of nodes. Ogni node con value e pos. Quindi, ordinare in base al valore dal quale è possibile recuperare la posizione.

struct node{ 
    int value; 
    int pos; 
} 

Come ho già detto, che funzionerà ma dubito che sia il modo più efficace

Answer 6

è possibile utilizzare il seguente:

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