How to get indices of top N values of an array in C

Question

I got the c-code from following link

How to get the indices of top N values of an array?

I have added input stimulus part to the above link code and developed the following c-model

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int main() {
  double *arr =malloc(sizeof(double)*10);
  int N=10;
  int n =5;
  int *top =malloc(sizeof(int)*10);
  arr[0] = 0.00623; 
  arr[1] = 0.745;
  arr[2] = 0.440;
  arr[3] = 0.145;
  arr[4] = 0.645;
  arr[5] = 0.741;
  arr[6] = 0.542;
  arr[7] = 0.445;
  arr[8] = 0.146;
  arr[9] = 0.095;
  top[0] = 100;
  top[1] = 100;
  top[2] = 100;
  top[3] = 100;
  top[4] = 100;
  int top_count = 0;
  int i;
  for (i=0;i<N;++i) {

    // invariant: arr[top[0]] >= arr[top[1]] >= .... >= arr[top[top_count-1]]
    // are the indices of the top_count larger values in arr[0],...,arr[i-1]
    // top_count = max(i,n);
    int k;

    for (k=top_count;k>0 && arr[i]>arr[top[k-1]];k--){

    }
    // i should be inserted in position k

    if (k>=n) continue; // element arr[i] is not in the top n
    // shift elements from k to top_count
    int j=top_count;
    if (j>n-1) { // top array is already full
      j=n-1;

    } else { // increase top array
      top_count++;
    }

    for (;j>k;j--) {
      top[j]=top[j-1];
    }
    // insert i
    top[k] = i;
    printf("top[%0d] = %0d\n",k,top[k]);


  }
  return top_count;
}

After executing the code, I am getting following output

top[0] = 0
top[0] = 1
top[1] = 2
top[2] = 3
top[1] = 4
top[1] = 5
top[3] = 6
top[4] = 7

The index is wrong for top[2]. It should be top[2] =4. I am not able to decode why it is giving problem for only top[2]?

Answer 1

This is just a matter of output...

You output your latestly inserted values right while yet sorting. You get output top[2] = 2 somewhere in your process, but later on, you shift the 2 out of the array by inserting new values before:

for (;j > k; j--)
{
    top[j] = top[j-1]; // moves the 2 out with further iterations!
}

What you have to do is output the sorted array afterwards:

} // for (i = 0; i < N; ++i)

// sorting finished now, so NOW output:

for (i = 0; i < n; ++i)
{
    printf("top[%0d] = %0d (%f)\n", i, top[i], arr[top[i]]);
}

And you'll see that your sorting actually worked as a charm...