0

this is my bubble sort program which works fine:

#include <stdio.h>
#include <stdbool.h>


/**
 * Sorts array of n values.
 */
void sort(int values[], int n)
{
    bool no_swap = false;
    int tmp, i, j;
    //  implement an O(n^2) sorting algorithm - bubble sort
    for(i = 0; i < n  && no_swap == false; i++) {
        no_swap = true;
        for(j = 0; j < n - i; j++) {
            if (values[j] > values[j + 1]) {
                tmp = values[j];
                values[j] = values[j + 1];
                values[j + 1] = tmp;
                no_swap = false;
            }
        }
    }

    return;
}

int main()
{
    int i;
    int arr[] = {9, 4, 2, 3, 1};

    sort(arr, 5);

    for(i = 0; i < 5; i++) {
        printf("%i\n", arr[i]);
    }

}

but when i place it into helper.c it always gives output of 0,1,2,3,4,5... (I've tested it by placing a for loop for printing values[i] in sort() and then running ./find 9) here's my helper.c:

/**
 * helpers.c
 *
 * Helper functions for Problem Set 3.
 */

#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)
{
    if(n <= 0)
        return false;

    int start = 0, end = n, mid;

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

    return false;
}


/**
 * Sorts array of n values.
 */
void sort(int values[], int n)
{
    bool no_swap = false;
    int tmp, i, j;


    //  implement an O(n^2) sorting algorithm - bubble sort
    for(i = 0; i < n  && no_swap == false; i++) {
        no_swap = true;
        for(j = 0; j < n - i; j++) {
            if (values[j] > values[j + 1]) {
                tmp = values[j];
                values[j] = values[j + 1];
                values[j + 1] = tmp;
                no_swap = false;
            }
        }
    }

    return;
}
1

You have two problems with the last element, or the one just behind the array.

In code

    for(i = 0; i < n  && no_swap == false; i++) {
        no_swap = true;
        for(j = 0; j < n - i; j++) {
            if (values[j] > values[j + 1]) {
                tmp = values[j];
                values[j] = values[j + 1];
                values[j + 1] = tmp;
                no_swap = false;
            }
        }
    }

what happens in the first iteration? You loop j from 0 to n-1, comparing elements at j and j+1, therefore in the last iteration elements n-1 and n, while there is no element at n. You might want to start i with 1, not 0, and there's no problem in running outer loop only n-1 times, as that's the maximum number of runs it takes.

In search, either treat end as the last element of the range and change

    int start = 0, end = n, mid;

to

    int start = 0, end = n-1, mid;

or treat it as the first element not in the range and change

    while(start <= end) {

to

    while(start < end) {

and

            end = mid - 1;

to

            end = mid;
1
  • thank you blauelf – gondu riya Feb 3 '17 at 13:29

You must log in to answer this question.

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