Like Tree1Likes
  • 1 Post By iMalc

Algorithm that finds the first 20 closest numbers to 23

This is a discussion on Algorithm that finds the first 20 closest numbers to 23 within the C Programming forums, part of the General Programming Boards category; I'm trying to figure out how to find the first 20 numbers that are closest to 23 in an int ...

  1. #1
    Registered User
    Join Date
    Mar 2012
    Posts
    32

    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;
    }

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    "Incorrect strategy, Number One."

    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.
    Last edited by Adak; 08-29-2012 at 07:58 PM.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    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.
    stahta01 likes this.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Mar 2011
    Posts
    546
    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.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    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))
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. the algorithm used in c++ to generate random numbers
    By karim tarbali in forum C++ Programming
    Replies: 7
    Last Post: 02-17-2012, 07:01 AM
  2. Amicable numbers efficient algorithm?
    By Andi Rrashi in forum C Programming
    Replies: 15
    Last Post: 11-04-2011, 06:02 PM
  3. closest pair algorithm
    By modulo_crt in forum C Programming
    Replies: 11
    Last Post: 10-19-2010, 06:40 PM
  4. finding the two closest numbers in an array
    By ominub in forum C Programming
    Replies: 9
    Last Post: 10-21-2009, 03:21 AM
  5. Help With Algorithm Egyptian Numbers
    By zerlok in forum C++ Programming
    Replies: 2
    Last Post: 02-23-2009, 07:57 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21