0

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
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.

| improve this answer | |
  • For Search I don't really understand how you can get rid of the stuff you said. What happens start = 0 to end = 14 and target = 8. It will skip 8. Am I wrong? – user20243 Oct 7 '17 at 5:43
  • can you help @Blauelf – user20243 Oct 7 '17 at 5:58
  • You say initial search interval is (0, 14) and target is found at index 8, larger than array[middle]. So on next iteration you'd have (8, 14), then (8, 10), then (8, 8), at which point middle has reached 8. That case of an interval with one element is the reason why you need <= and not < in the while's condition. – Blauelf Oct 9 '17 at 8:29
0

@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;
            }
        }
    }
}
| improve this answer | |

You must log in to answer this question.

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