c++algorithmbubble-sort

C++ Bubble Sort Algorithm


I have the following code written in c++ and the algorithm works when in this scenario. I am knew to c++ and don't understand what I did wrong in my 2nd test.

#include <iostream>

using namespace std;

void bubbleSort(int numbers[], int size) {
    for (int i = 0; i<size;i++) {
        for (int j=0; j<size;j++) {
            if (numbers[j] > numbers[j+1]) {
                swap(numbers[j], numbers[j+1]);
            }
        }
    }
}

int main() {
    int numbers[] = {7,5,6,4};
    bubbleSort(numbers,4);
    
    for (int print = 0; print < 4; print++) {
        cout << numbers[print] << endl;
    }
    
    
    return 0;
}

But, fails when I try to put in numbers that are already sorted:

#include <iostream>

using namespace std;

void bubbleSort(int numbers[], int size) {
    for (int i = 0; i<size;i++) {
        for (int j=0; j<size;j++) {
            if (numbers[j] > numbers[j+1]) {
                swap(numbers[j], numbers[j+1]);
            }
        }
    }
}



int main() {
    int numbers[] = {1,2,3};
    bubbleSort(numbers,3);
    
    for (int print = 0; print < 3; print++) {
        cout << numbers[print] << endl;
    }
    
    
    return 0;
}

Solution

  • for (int j=0; j<size;j++) {
    

    If size is 3, if the array has three values, for example, this loop iterates with values of j of 0, 1, and 2.

    if (numbers[j] > numbers[j+1]) {
    

    When j is 2 this compares numbers[2] with numbers[3].

    There is no numbers[3]. This is undefined behavior. The loop is off by 1 value.

    Additionally, the overall bubble sort implementation is flawed. In the shown code the inner loop iterates over the entire array (ignoring the off-by-1 bug), every time. In a classical bubble sort the first pass (the first iteration of the outer loop) results in the inner loop iterating over the entire array and "bubbling" the smallest/largest value to the end of the array. On the next pass the inner loop does not need to iterate over the entire array, but only up until the 2nd smallest/largest position of the array. And so on, each pass (the outer loop) results in the inner loop iterating over a smaller, and smaller subset of the array, "bubbling" the corresponding value to the appropriate stop.

    In addition to fixing the off-by-1 bug you'll also need to adjust the overall logic of this bubble sort, if you wish to get a perfect grade for your homework assignment.