PSET3 find having trouble. Can someone help?

Question

For some reason bubble sort is not working. Can someone help.

binary search bool search (int target, int array[],int length)
 { 
    int end =  length-1; int start = 0;

    while (array[start] <  array[end])
    {
        //   7           0          14
        //  11           8          14
        //  13          12      +   14
        //  14          14          14
        //
        //   9           10      +    8    =
        //               8       +   8
        int middle  = (start + end)/2;
        if (array[middle] ==  target)
        {
            return true;
        }   //13.5         7
            // 13.5           11
            //13.5            13

        if (  target > array[middle] )
        {    // 8      7+1
            // 12      11+1
            // 14       13+1
            start = middle+1;
            //          8             13.5
            //          12            13.5
            if (array[start] ==  target)
            {
                return true;
            }
        }       
        else if(target < array[middle])
        {


               end = middle - 1;
               if (array[end] ==  target)
               {
                  return true;
               }

        }
    }
        return false;

}

I realize bubble sort is really inefficient code. The code won't work . The parts I can identity is printf( "%d" , array[total]); and break; Will break work the way I set it up? Here is a few steps.

I just realized I don't even need this part. //reverses left and right back to correct order so right is not before left // 1 = 2 left = right; right = left + 1;

                                 r
                                     l
         // ex array[total] = {2,5,3,1,4}

                                    l       
                                r 
        // ex array[total] = {2,1,3,5,4}

The next time I run the loop array[right] and array[left] will array[total] eventually change to {1 2 3 4 5}

//bubble sort

void sort (int array[], int  total ) { // ex array[total] = {2,5,3,1,4} int  end = total - 1; int left = 0; int min = 0; int right
=  left + 1;
    while ((left <= total) || (min <= total))
    {
        if( array[left] > array[right] )
        {//switches array[left] and array[right]
        //5               3
            array[left]  =  array[right];
            //          5 [2]-[1]

            array[right] = array[left]-1;
            printf( "%d %d" ,array[left] ,array[right]);
            //reverses left and right   back to correct order so right is not before left
            // 1 =  2
            left = right;
            right = left + 1;

        }
        // maybe top block
        if (right == end)
        {
            min++;
            left = 0;
            right = left +1;
        }

        if (min == end)// does total need to be end
        {
            printf( "%d" , array[total]);
            break;
        }
        left++;
        right = left + 1;

    }

}

Did I make any other mistakes in bubble sort?

:) helpers.c exists.
:) helpers.c compiles.
:( sorts {5,4,3,2,1}
    expected "2", not "\n"
:( sorts {5,3,1,2,4,6}
    expected "3", not "\n4\n6\n"
:( finds 28 in {28,29,30}
    expected exit code 0, not 1
:( finds 28 in {27,28,29}
    expected exit code 0, not 1
:( finds 28 in {26,27,28}
    expected exit code 0, not 1
:( 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}
    expected exit code 0, not 1
:) 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

Answer 1

The

array[start] <  array[end]

is the wrong condition. You want to keep looping as long as the search interval has elements, so use

start <= end

instead (<= as you chose both start and end to be included in the interval). Then you can remove those if (array[start] == target) and if (array[end] == target) which seem to compensate for leaving the loop early (and won't work if your array for example had only one element).

In sort,

        array[left]  =  array[right];
        array[right] = array[left]-1;

won't swap two elements. The usual way is using an extra variable, like

        int temp     = array[left];
        array[left]  = array[right];
        array[right] = temp;

though there exist other schemes which don't need the extra variable but do some calculation instead (and are usually not as readable), for example

        array[left]  ^= array[right];
        array[right] ^= array[left];
        array[left]  ^= array[right];

The

        left = right;
        right = left + 1;

should not be within the if( array[left] > array[right] ) block, but below (otherwise you might skip a pair after swapping), and there should not be an extra copy of those two lines at the end of the loop. You'd have to use if (left == end) instead of if (right == end). Instead of if (left == end); you could use if (left == end - min).

You could use nested for loops instead of this complicated while loop. Those are meant to concentrate the loop control within one line, while the control of a while loop may be (and in your case is) spread over the whole body. So instead of

int end = total-1;
int left = 0;
int min = 0;
int right = 1;
while (true) // I don't think your condition will ever become false
{
    if (array[left] > array[right])
    {
        // swap left and right element
    }
    left++;
    right++;
    if (left == end - min)
    {
        min++;
        left = 0;
        right = left + 1;
    }
    if (min == end)
    {
        break;
    }
}

you could have

for (int min = 0; min < total - 1; min++)
{
    for (int left = 0, right = left + 1; right < total - min; left++, right++)
    {
        if (array[left] > array[right])
        {
            // swap left and right element
        }
    }
}

(though I would substitute every use of right with left+1, as those always move together)

Oh, and I'm not sure, your printf might confuse check50, maybe you need to remove those before submission.

Answer 2

@Blauelf

I accidentally lost the info for the previous account and how to recover it. So I typed in the code but am still getting errors I assume it is something I am doing wrong. Without the code below it works and compile. Can you help me find the error? I have tried help50 and get nothing.

clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm
/tmp/helpers-e977f1.o: In function `search':
/home/ubuntu/workspace/pset3/find/helpers.c:15: multiple definition of `search'
/tmp/find-5e19c1.o:/home/ubuntu/workspace/pset3/find/find.c:71: first defined here
/tmp/helpers-e977f1.o: In function `sort':
/home/ubuntu/workspace/pset3/find/helpers.c:24: multiple definition of `sort'
/tmp/find-5e19c1.o:/home/ubuntu/workspace/pset3/find/find.c:99: first defined here
clang: error: linker command failed with exit code 1 (use -v to see invocation)
make: *** [find] Error 1



//binary search
bool search (int target, int array[],int length)
{
    int end =  length-1;
    int start = 0;
    while (start <=  end)
    {
        int middle  = (start + end)/2;
        if (  target > array[middle] )
        {
            start = middle+1;
            if (array[start] ==  target)
            {
                return true;
            }
        }
            else if(target < array[middle])
            {
                end = middle - 1;
            }
    }
    return false;
}




    //bubble sort

void sort (int array[], int  total )
{
    for (int min = 0; min < total - 1; min++)
    {
        for (int left = 0, right = left + 1; right < total - min; left++, right++)
        {
            if (array[left] > array[right])
            {
                //swap left and right element
                int temp = array[left];
                array[left] = array[right];
                array[right] = temp;
            }
        }
    }
}