Algorithm that finds the first 20 closest numbers to 23

I'm trying to figure out how to find the first 20 numbers that are closest to 23 in an int array of 200 between numbers 1 - 100. I tried to break it into steps:

-subtract each number in the array by 23
-get the absolute value of that number
-use selection sort to get the smallest numbers

...and thats where I'm stuck. I can't just add 23 back to those numbers, because some were negative. Right now I'm getting a segmentation fault. Any help?

Code:

---

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

#define ARRAY_SIZE 200
#define NUM_TO_FIND 20

int main(int argc, char *argv[]) {
  int numbers[ARRAY_SIZE];
  int top[NUM_TO_FIND];
  int idx;
  int i;
  int j;
  int k;
  int hold;

  srand(time(NULL));
  memset(&top[0], 0, sizeof(int) * NUM_TO_FIND);

  for (idx = 0; idx < ARRAY_SIZE; idx++){
      numbers[idx] = rand() % 99 + 1;   

 }

//here
      for (k = 0; k < ARRAY_SIZE; k++){
        top[k] = numbers[k] - 23;
        top[k] = top[k]<0?0-top[k]:top[k];     
      }

      for(i = 0; i < ARRAY_SIZE; i++){
        for(j = 0; j < ARRAY_SIZE; j++){
            if(top[i] < top[j]){
                    hold = top[i];
                top[i] = top[j];
                top[j] = hold;
            }
        }
      }
//here
     
  puts("Original Array:");
  for (idx = 0; idx < ARRAY_SIZE; idx++)
      printf("%d ", numbers[idx]);

  puts("\nTop 20:");
  for (idx = 0; idx < NUM_TO_FIND; idx++)
      printf("%d ", top[idx]);

  return 0;
}

---

"Incorrect strategy, Number One." :p

Have an int array of 101 elements. (This is what is sometimes called "Counting Sort", and it ROCKS like you wouldn't believe.) Go through the data one time, with this logic, in a loop:

Code:

---

for each number
  data[number]++;

---

Note that it is difficult or impossible to use Counting Sort, if the numbers have a huge range, or negative values - but here, they don't.

Now one more loop. As i is incremented, you'll count up all the counting values in the data[] array, at 23+i, AND in the same loop, at the same time, you'll count up all the data[] array values that are 23-i.

That will create a circle with 23 as the bull's eye, and the nearest variable being updated from both above it, and below it, in the same iteration of the loop.

Like this:

Code:

---

for(i=0,nearest=0;i<77;i++) { //77 is 100 minus 23, the upper range.
    nearest += data[23+i ];
    if(23-i > -1)
        nearest+= data[23-i];
    if(nearest > 19)
        break;
};

---

Don't take the above as working code, because this is very much just here to give you something close to what I'm explaining.

Line 28 is a clear bug. You're indexing two different arrays of different sizes using the same variable.

Instead of changing the numbers to abs(number - 23), just subtract 23 form the number where it is, but compare the absolute values when comparing them. I.e. in pseudocode do: if (abs(num1) < abs (num2))
Then you can add 23 back to them just fine afterwards. In fact you need only do that to the first 20 items in the array and ignore the rest which were further away from 23. You don't even need a second array.

You really should make 23 a constant in your program too btw.

another approach to the abs problem would be instead of having an array of ints, have an array of structs that have a field for the original value and the absolute value. sort by absolute value then output the original value.

And another way to do it would be to just use this for the comparison when sorting, and the array need not be modified at all:

Code:

---

if (abs(num1 - TARGET_VAL) < abs(num2 - TARGET_VAL))

---