0

I can't seem to see the problem with my code for Selection Sort. I'm passing all the checks for check50 except the one with an unsorted array so I'm guessing that the problem lies with my Selection Sort rather than my Binary Search code.

My Selection Sort:

void sort(int values[], int n)
{
if (n < 2) 
{
    return;
}
for (int i=0; i<(n-1); i++)
    {
        int min;
        min = values[i];
        for (int j=i+1; j<(n-1); j++)
        {
            if ((values[j]) < min)
            min = values[j];
        }
        if (min != (values[i]))
        {
            int temp= values[i];
            values[i] = min;
            min = temp;
        }
    }
return;
}

My Binary Search:

bool search(int value, int values[], int n)
{
if (n>0)
{
    int mid = round(n/2);
    if ((values[mid]) == value)
        return true;
    else
    {
        do
        {
            if (value < (values[mid]))
            {
                mid = round(mid/2);
                if ((values[mid]) == value)
                {
                    return true;
                    break;
                }
            }
            else if (value > (values[mid]))
            {  
                int half = round((n-mid)/2);
                mid = mid + half;
                if ((values[mid]) == value)
                {
                    return true;
                    break;
                }
            }
        }
        while ((!mid == 0) && (!mid == (n-1)));
    }
    return false;
}
else return false;
}

My Check50 Result:

:) helpers.c exists
:) helpers.c compiles
:) finds 42 in {42,43,44}
:) finds 42 in {41,42,43}
:) finds 42 in {40,41,42}
:) finds 42 in {41,42,43,44}
:) finds 42 in {40,41,42,43}
:) finds 42 in {39,40,41,42}
:) doesn't find 42 in {39,40,41}
:) doesn't find 42 in {39,40,41,43}
:( finds 42 in {42,40,39,41}
\ expected an exit code of 0, not 1

Any help is appreciated thank you.

0

Your selection sort would have to track the actual index of the minimal element, as after min = temp; the value of min is never used again, you essentially doubled the minimum element and lost the value that was at index i.

Also, inner loop should go to <n, not <n-1

I'd suggest something like

        int min;
        min = i; // always track the index, maybe also cache the minimal value
        for (int j=i+1; j<n; j++)
        {
            if (values[j] < values[min])
                min = j;
        }
        if (min != i)
        {
            int temp = values[i];
            values[i] = values[min];
            values[min] = temp;
        }

[edit] Your search function is also not correct, please review the binary search algorithm.

You must log in to answer this question.

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