pset3 help with find, bubble-sort and search

Question

I've been struggling for over a week with this and can't figure out how to get my program to pass check50. I'm getting very interesting mixed results from check50:

:) helpers.c exists.

:) helpers.c compiles.

:( sorts {5,4,3,2,1} expected "3", not "\n"

:( sorts {5,3,1,2,4,6} expected "2", not "\n6\n4\n"

:) finds 28 in {28,29,30}

:( finds 28 in {27,28,29} expected exit code 0, not 1

:) finds 28 in {26,27,28}

:( finds 28 in {27,28,29,30} expected exit code 0, not 1

:( finds 28 in {26,27,28,29} expected exit code 0, not 1

:) finds 28 in {25,26,27,28}

:) doesn't find 28 in {25,26,27}

:) doesn't find 28 in {25,26,27,29}

:) doesn't find 28 in {29,30,31,32}

:) doesn't find 28 in {29, 30, 31}

:( finds 28 in {30,27,28,26} expected exit code 0, not 1

Here's my helpers code:

#include <cs50.h>

#include "helpers.h"

/**
 * Returns true if value is in array of n values, else false.
 */
bool search(int value, int values[], int n)
{
while (n < 0)//return 1 if n is non-positive
{
    return 1;
}
//implement binary search
int low = 0;
int high = n - 1;
int mid;

while (low <= high)
{
    mid = low + (high - low) / 2;
    if (value == values[mid])
    {
        return true;
    }
    else if (value > values[mid])
    {
        low = mid + 1;
    }
    else if (value < values[mid])
    {
        high = mid - 1;
    }
}
return false;
}

/**
 * Sorts array of n values; selection sort.
 */
void sort(int values[], int n)
{
//implement a sorting algorithm: bubble
for (int i = 0; i < (n - 1); i ++)//iterate through first time
{
    for (int j = 0; j < n - i - 1; j ++)//iterate through again without final element
    {
        int swapcount = -1;//set swapcount to a non-zero value

        if (swapcount != 0)
        {
            swapcount = 0;
            int swap = values[i];
            values[i] = values[i+1];
            values[i+1] = swap;
            swapcount ++;
        }
    }
}
return;
}

I've put in a lot of hours, but I think I'm still missing something fundamental.

I don't understand the printed errors in the sort program at all. Obviously my search isn't finding '28' whenever it's in the middle (i.e. not beginning or the end), but I'm thinking that possibly fixing sort will help fix the errors in search.

Any help understanding the basic principles would be extremely appreciated!!

Answer 1

The sort code posted isn't sorting anything. It merely swaps only two values on each pass through the inner for loop.

The reason it doesn't sort is that it blindly swaps values no matter which is larger. It doesn't test whether it should (no if condition).

Additionally, the use of swapcount appears intended to halt swapping in a loop. In fact, because it is reset at the start of each pass in the loop, the swap will always execute. It should be used to determine whether a swap has occurred and, if not, stop the loop because the list is sorted, but only after a complete pass through the unsorted part of the list without executing a swap.

For debugging, you should add a for loop to the end of the sort function (before the return) to print out the sorted loop for inspection.

I haven't analyzed the check function because you deserve a chance to work on it once the sort function has been fixed. Happy programming! ;-)

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