0

I've tried to write an implementation of bubble sort.

I deliberately created it in a separate file outside of helpers.c, just to make sure it works, before incorporating into helpers.c

It doesn't work! I don't understand why not. I've worked through what I think should be happening with a pen and paper. So, I'm stuck.

My code is below. I've left in my commentary, so you can understand my logic a bit. Also, please forgive me if I haven't managed to input the code properly - I'm assuming I can just copy and paste from the ide.

Many thanks in advance for your help.

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

void sort(int values[], int n)
{
    for(int i = 0; i < n-1; i++) // Note: "i < n-1" because we are checking pair-wise; therefore only need to get to penultimate place in array
    {
        bool noswap = 0; // Introducing variable that tests whether we swapped any pairs of numbers on any run-through the "inner" loop
        for(int j = 0; j < (n - 1 - i); j++)
        {
            if(values[j] > values[(j+1)])
            {
                int temp  = values[j];
                values[j] = values[(j+1)];
                values[j] = temp; 
                noswap = 1;
            }
        }
        if (noswap == 0) // If no pairs of numbers were swapped, we can break, without having to back through the outer loop again - improving efficiency
        {
            break;
        }
    }
    return;    
}

// This is a short programme that uses the "sort" function written above, to test whether it works

int main()
{
    int arr[] = {9, 4, 2, 3, 1};
    sort(arr, 5);
    for(int i = 0; i < 5; i++)
    {
        printf("arr position %d = %d\n", i, arr[i]);
    }
}

And here is the output:

enter image description here

Improve this question
1

In your swap part, you assign to values[j] twice, second should be values[j+1]

Improve this answer
1
  • omg - thank you so much! That was what I meant to do - just a silly typo. Too blind to see it! Still, I guess I learned a lot about de-bugging by going through the whole algorithm by hand - or rather, going through what I'd meant to write, rather than what I actually wrote. Good lesson to learn! I even built a simulation in MS excel - which worked! Now I can move on to the second part of Pset3. Thanks once again.
    – Matt Friend
    Jan 25 '17 at 18:40

You must log in to answer this question.

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