Pset3 Search/Find problems

Question

I have no idea what the problems are with this code, so any help would be appreciated. The code compiles, but the output is skewed. It only sorts after a certain amount of characters, and then sorts badly. Suggested test for linear sort : ./generate 1000 50 | ./find 127 Output: Didn't find needle in haystack. Check50 : Checking....................................................................................................................... Unexpected end of input. Trying to find 3 :jharvard@appliance (~/Dropbox/pset3/find): ./find 3

haystack[0] = 1

haystack[1] = 2

haystack[2] = 3

haystack[3] = Segmentation fault (core dumped).

Thanks!

-mmoore

Here is my code:

#include <cs50.h>
#include <math.h>
#include <stdio.h>
#include "helpers.h"

/**
 * Returns true if value is in array of n values, else false.
 */
 //Recursive Search
int k = 0; 
bool binsearch(int key, int array[], int min, int max)
{
int j = 0;
int mid1 = 0;
int mid = 0;
if(max < min)
{
    printf("%i", j);
    return false;
}
else
{
    mid1 = max / 2;
    mid = round(mid1);
    if(array[mid] < key)
    {
        return binsearch(key, array, mid + 1, max);    
    }
    else if(array[mid] < key)
    {
        return binsearch(key, array, min, mid - 1);
    }
    else
    {
        k = k + 1;
        j = j + 1;
        printf("%i", j);
        return true;
    }
   }
} 

 /**
 * Returns true if value is in array of n values, else false.
 */

bool search(int value, int values[], int n)
{   
   binsearch(value, values, values[0], n);
   return k;     
}
/**
 * Sorts array of n values.
 */
void sort(int values[], int n)
{   
    int j = 0;
    int k = n;
    for(int i = 0; i < n; i++)
    {
    if(values[i] == 0)
    {

    }
else if(values[i] < j)   
{
j = values[i];
values[k] = j;
k = k - 1;
}      
}
return;
}

Answer 1

I don't want to sound cruel here, but your sort routine has serious problems. It is incomplete, it has code that appears to serve no purpose ( an if statement with no code to process if true), and doesn't compare any two elements in the list to sort (or at least not the two intended elements).

Your biggest problem (in my opinion) is that you are comparing, and maybe sometimes swapping, list elements with the value of an index variable instead of other list elements. You do that here: if(values[i] < j) When this statement is true, you actually remove the element in values[y] and replace it with the current value of j, which is definitely not part of the list initially, thus corrupting the list. Purely by chance, all the numbers on the list from ./generate are larger than j, so nothing is being swapped.

You probably wanted to do this: if(values[i] < values[j]). The swap that follows is the same type of error. Start with this fix and then work through any remaining issues. You should also consider recoding it so that it uses a second, nested FOR loop.

I also suggest adding some temporary code to print out the list after it is sorted so that you can see what's happening. You could use a for loop with a printf statement that prints the index of the array followed by the contents of that index.

Debugging this pset will be an excellent learning experience for you. You need to learn the skills to track down these issues and the code above will do quite nicely without the errors being too complex for you to sort out.

I suspect that others might want to point out every error and how to fix it, but you'll learn so much more if you get there yourself! If it's too complicated though, feel free to ask for help.

If this answers your question, please click the check mark to accept this and remove the question from the unanswered pool. Let's keep up on forum maintenance. ;-)