0

I'm working on pset3, and I think I've finished helpers.c. It sorts correctly, and I can't find any mistakes, but it does something really weird. If I enter the values 1, 2, 3, 4, 5 into find.c as hay, it sorts it, except it ends up as 0 ,1, 2, 3, 4. There's always a number missing and a 0 to replace it.

I use this code to sort:

void sort(int values[], int n)
{
   // TODO: implement an O(n^2) sorting algorithm
   int track = n;
   int check = 1;
   int hold;
   while (check != 0)
   {
      check = 0;
      for (int i = 0; i < track; i++)
      {
         if (values[i] > values[i + 1])
         {
            check++;
            hold = values[i];
            values[i] = values[i + 1];
            values[i + 1] = hold;
         }   
      }  
      track--;
   }

And I use this code to search:

bool search(int value, int values[], int n)
{
   // TODO: implement a searching algorithm
   int min = 0;
   int max = n;
   int x;
   while (max - min > 1)
   {
      x = round((max + min) / 2);
      if (values[x] < value)
         min = x;
      else if (values[x] > value)
         max = x;
      else
         return  true; 
   }
   return false;   
}

Can anyone please help me figure out what's wrong?

  • I can't understand why you used a while loop in your sort function. You want to use bubble sort right? Could you explain me the use of variables track and check? – PanosVl Jul 26 '14 at 9:42
  • @Panos I couldn't think of another way to keep checking the array until it's sorted. So check is supposed to keep track of whether or not any changes were made so that it should stop when 0 changes are being made. And after running the bubble sort once, the largest number should bee in place, so I made track because I can't change n, the length. – Munchigum Jul 28 '14 at 18:45
  • But now you've figured out the way, right? – PanosVl Jul 30 '14 at 14:57
1

Initially, track is equal to n. Think about the situation when i is equal to track - 1 which is n - 1 and you try to access the value in values[i + 1]. Now, that's an invalid read because i + 1 in this case is equal to track and n and this index is beyond the array boundaries.

Also, usually, when we know the number of iterations beforehand (as we do in this case), we use for loops. On the other hand, while loops are used when we don't know the number of iterations (e.g., when we use a sentinel value to exit the loop).

For the search() function, your loop shouldn't be exiting even if max is equal to min (the difference is 0). So you're probably exiting a little bit early.

And since you're working with ints, no need to use round() as the digits after the decimal point are truncated anyway before even the call to round() is executed.

Lastly,

if values[x] < value 
    min should be x + 1 not x because values[x] was already tested
else if values[x] > value
    max should be x - 1 not x because, again, values[x] was already tested

Hope that helps! :)

| improve this answer | |
  • Thanks, changing track to n -1 fixed the 0 problem, and your other suggestions helped too. But when I got rid of the round(), the search function stopped working. – Munchigum Jul 26 '14 at 21:28
  • @Munchigum well, I see no role to round() at all. As your expression is first evaluated to (max + min) / 2 before the call to round(). And I guess round does nothing at all. Could you please tell me how search() stopped working exactly? – Kareem Jul 26 '14 at 22:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .