C Bubble Sort Algorithm-CodePudding

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;
}

CodePudding user response：

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.

CodePudding user response：

Implementing bubble sort in its entirety is problematic. In the example code, the inner loop repeatedly iterates over the full array while disregarding the shift by 1. The inner loop iterates over the whole array in a traditional bubble sort's first iteration of the outer loop, "bubbling" the smallest/largest value to the array's end. On the subsequent iteration, the inner loop only has to iterate up to the array's second-smallest/largest point rather than the full array. The inner loop then iterates through a smaller and smaller subset of the array, making bubbles of the associated the associated value to the proper stop with each successive run in the outside loop.