Indirect sorting using index vector

Question

Hello, I’m having trouble solving my workout and would like a help. I thought to do with max heap but it didn’t work out.

That is the statement:

"Indirect sorting problem". ) Write an algorithm that takes an integer number n and a constant vector of integers A[1..n] and returns a vector B[1..n] vector index A in such a way that A[B[1]] ≤ A[B[2]] ≤ . . . ≤ A[B[n]]. Values stored in a constant vector cannot be changed. If A is a constant vector and A[1] = 5, then A[1] = 5 forever.

Ex.: Suppose an entry A = [3, 6, 1, 8]. Your algorithm must return B = [3, 1, 2, 4], for, A[B[1]] = A[3] = 1 ≤ A[B[2]] = A[1] = 3 ≤ A[B[3]] = A[2] = 6 ≤ A[B[4]] = A[4] = 8.

Here’s what I’ve tried:

#include <stdio.h>
#include <stdlib.h>

void ordena(int v1[], int v2[], int v3[]);
void imprime(int v[]);

int main()
{
   int v1[4];
   int v2[4];
   int v3[4];
   /*
   printf("Digite 4 valores)");
   scanf("%d", v[0]);
   scanf("%d", v[1]);
   scanf("%d", v[2]);
   scanf("%d", v[3]);
  */
   v1[0] = 3;
   v1[1] = 6;
   v1[2] = 1;
   v1[3] = 8;

   v2[0] = 3;
   v2[1] = 1;
   v2[2] = 2;
   v2[3] = 4;


   ordena(v1, v2, v3);

   imprime(v3);


   return 0;
}

void ordena(int v1[], int v2[] , int v3[]){
    int aux, i, j;
    int k;
    k=0;
        for(i=0;i<4;i++){
                for(j=0;j<4;j++){
                    if(v1[v2[i]] > v1[j]){
                        v3[k] = v1[v2[i]];
                        k++;
                    }

                }
        }

}
void imprime(int v[])
{
   int i;
   for(i = 0; i < 4; i++)
   {
      printf("\nElemento %d.... %d\n", i, v[i]);
   }
}

Answer 1

The trick is to create a copy of the original array (since it cannot be changed). The array B is initialized with [1, 2, 3, 4]. Each time you change two place elements in the copy of A, you make the exchange with the same positions in B. When the copy of A is ordered, the vector B will be ready.

Here is the resulting code:

#include <stdio.h>

void ordena(int tamanho, const int *a, int *b) {
    int *copia = (int *) malloc(tamanho * sizeof(int));
    int i;
    for (i = 0; i < tamanho; i++) {
        copia[i] = a[i];
        b[i] = i + 1;
    }

    int achou_inversao;
    do {
        achou_inversao = 0;
        for (i = 0; i < tamanho - 1; i++) {
            if (copia[i] > copia[i + 1]) {
                int aux = copia[i];
                copia[i] = copia[i + 1];
                copia[i + 1] = aux;
                aux = b[i];
                b[i] = b[i + 1];
                b[i + 1] = aux;
                achou_inversao = 1;
            }
        }
    } while (achou_inversao);
    free(copia);
}

int main(void) {
    int a[] = {3, 6, 1, 8};
    int b[] = {0, 0, 0, 0};
    ordena(4, a, b);
    printf("%d %d %d %d", b[0], b[1], b[2], b[3]);
    return 0;
}

Here’s the way out:

3 1 2 4

See working on IDE one.