Indirect sorting using index vector

Navigation
3

Hello, I have a hard time resolving my workout and would like some help. I thought about doing with max heap, but it did not work.

Here's the statement:

  

"Indirect sort problem".) Write an algorithm that receives an integer n and a constant vector of integers A[1..n] and returns a vector B[1..n] of indexes of vector A in such a way that A[B[1]] ≤ A[B[2]] ≤ . . . ≤ A[B[n]] . Values stored in a constant vector can not be changed. If A is a constant vector and A[1] = 5 , then A[1] = 5 forever.

     

Eg: Suppose a A = [3, 6, 1, 8] entry. Your algorithm should return B = [3, 1, 2, 4] , therefore, 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]);
   }
}
    
asked by anonymous 10.12.2015 / 02:11

1 answer

4

The trick is to create a copy of the original array (since it can not be changed). The B is initialized with [1, 2, 3, 4] . Each time you exchange two place elements in the copy of A , you make the exchange with the same positions in B . When the copy of A is sorted, the B vector is 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 output: 

3 1 2 4

See working in IDE one .

    
10.12.2015 / 03:16
javascript problem receiving variable with date Can I use "mysql_real_escape_string" in site "mysqli_connect"?