3

So I just stared programming in C a few days ago and I have this program which takes an unsorted file full of integers, sorts it using quicksort 1st algorithm

Any suggestions on what I have done wrong in this?

14
  • 2
    If you are sorting the list, can you not just return the element at index 0.9*numberOfNumbers ? Commented Nov 14, 2013 at 16:24
  • No, because I might have duplicates in the file, so I need to jump over them so to say. I do take them into account when calculating the % but when I find one I simply go to the next one to check if it's not the same as the previous one. Commented Nov 14, 2013 at 16:26
  • 2
    why not delete the repeated numbers when you read the file and after delete use the formula? Commented Nov 14, 2013 at 16:29
  • 1
    What would you expect from a list like "1 1 1 1 1 ... 1"? Does 1 "exceed at least 90% of the numbers", even though it is both the largest and the smallest number in the list? I think that the question as stated leaves enough corner cases that a fully correct answer might be hard to produce... And in fact, depending on the exact specification, some of those corner cases may not even have solutions... Commented Nov 14, 2013 at 16:34
  • 1
    The break fixed my algorithm. That is what I was missing. Commented Nov 14, 2013 at 20:16

3 Answers 3

5

From what you have described, it sounds like you are almost there. You are attempting to get the first element of a collection that has a value equal to (or just greather than) 90% of all the other members of the collection. You have already done the sort. The rest should be simply following these steps (if I have understood your question):

1) sort collection into an into array (you've already done this I think)
2) count numbers in collection, store in float n; //number of elements in collection
3) index through sorted array to the 0.9*n th element, (pick first one beyond that point not a duplicate of previous)
4) display results

Here is an implementation (sort of, I did not store n) of what I have described: (ignore the random number generator, et al., it is just a fast way to get an array)

#include <ansi_c.h>
#include <windows.h>
int randomGenerator(int min, int max);
int NotUsedRecently (int number);
int cmpfunc (const void * a, const void * b);

int main(void)
{
    int array[1000];
    int i;

    for(i=0;i<1000;i++)
    {
        array[i]=randomGenerator(1, 1000);
        Sleep(1);
    }

    //sort array
    qsort(array, 1000, sizeof(int), cmpfunc);

    //pick the first non repeat 90th percent and print
    for(i=900;i<999;i++)
    {
        if(array[i+1] != array[i])
        {
            printf("this is the first number meeting criteria: %d", array[i+1]);
            break;
        }
    }
    getchar();  

    return 0;
}






int cmpfunc (const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}


int randomGenerator(int min, int max)
{
    int random=0, trying=0;

    trying = 1;         
    srand(clock());
    while(trying)
    {

        random = (rand()/32767.0)*(max+1);
        (random >= min) ? (trying = 0) : (trying = 1);
    }

    return random;
}

And here is the output for my first randomly generated array (centering around the 90th percentile), compared against what the algorithm selected: Column on left is the element number, on the right is the sorted list of randomly generated integers. (notice it skips the repeats to ensure smallest value past 90%)

enter image description here enter image description here

In summary: As I said, I think you are already, almost there. Notice how similar this section of my code is to yours:

enter image description here

You have something already, very similar. Just modify it to start looking at 90% index of the array (whatever that is), then just pick the first value that is not equal to the previous.

Sign up to request clarification or add additional context in comments.

Comments

1

One issue in your code is that you need a break case for your second algorithm, once you find the output. Also, you cannot declare variables in your for loop, except under certain conditions. I'm not sure how you got it to compile.

8 Comments

Also, you can't declare variables in your for loop. I'm not sure how you got it to compile I disagree. You CAN declare variables in a for loop, or just about any other block. Your statement is incorrect. If you fix that, or provide some rational that is accurate, I will undo my downvote. Also, your assertion that a break case is necessary is questionable. The loop will exit when the condition (array[x] == array[x + 1]) is not longer true.
@ryyker Here you go. Also, my statement referred to an earlier version of the code above. If you scroll back through the edits, you can see what I'm talking about.
Thanks. will retract the down vote. I also took a look at the OP code, break will work where you suggested. I would suggest though being specific on C specification (eg. C99, C11, et al.) if you can when pointing out some feature that is provided (or is missing) such as not being able to create a variable within a loop. I do that all the time :) ( Just discovered my vote is locked in (time limit) If you can make a small edit to your post, then I will come back later and give you an up vote. Thanks )
Alright. This is my first semester doing C, and I wasn't aware there different conditions where a compiler would accept a declaration in a for loop. I'll have to look more into that option.
You can always declare variables in for loops, except if you are using an archaic compiler which doesn't support the 14 years old C99 standard. Even visual studio 2013 supports that.
|
1

According this part:

int output = array[(int)(floor(0.9*count)) + 1];
int x = (floor(0.9*count) + 1);

while (array[x] == array[x + 1])
{
    x = x + 1;
}
printf(" %d ", output);  

In while you do not check if x has exceeded count... (What if all the top 10% numbers are equal?) You set output in first line and print it in last, but do not do antything with it in meantime. (So all those lines in between do nothing).

You definitely are on the right track.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.