Bubble sort function stops working halfway through array

Question

For my assignment, I need to generate a random array and sort it in order from smallest to largest using bubble sorting as well as search for certain numbers in the array. I have gotten through most of the assignment but I realized about halfway through the array my bubble sort has stopped working as in the numbers fall out of order. So the first few numbers could be 44, 50, 50, 56, 65 and then about 10-11 numbers through the 20 number array it starts getting random. This is my first time using bubble sort so it could be a small mistake I don't recognize.

The search function is also not shown because the order is displaying wrong before reaching that point in the program and that function also works fine.

int const MAX = 20;
int bubbleSort(int arr[], int length, int arrSelect);
void search(bool found, int arrayCheck[], int x1);
void swap(int *swap1, int *swap2);

int main()
{
    //Variables

    int original[MAX];
    int sorted[MAX];
    int quantity = 0;
    int sum = 0;
    int x = 0;
    bool find = false;
    double avg = 0;
    bool found = false;
    srand(time(NULL));

    for(int i = 0; i < MAX;)
    {
        original[i] = ((rand() % 89) + 10);

        sorted[i] = original[i];

        sum += original[i];

        i++;
    }

    for (int k = 0; k < MAX;)
    {
        sorted[k] = bubbleSort(sorted, MAX, k);
        cout << sorted[k] << endl;
        k++;
    }
    search(find, sorted, x);



}

int bubbleSort(int arr[], int length, int arraySelect)
{
    int r = 0;
    int c = 0;
    for(r = 0; r <= MAX - 1; r++)
    {
        for (c = 0; c <= MAX - r - 1; c++) 
        {
            if (arr[c] > arr[r])
            {
                swap(&arr[c], &arr[r]);
            }

        }
    }

    return arr[arraySelect];
}

void swap(int *swap1, int *swap2)
{
    int temp = *swap1;
    *swap1 = *swap2;
    *swap2 = temp;
}

Answer 1

Source: Algorithms: Explained and Animated

As you can see in the above simulation that in a single pass of the array, bubble sort compares each pair of consecutive indexes and swaps them if one is greater than the other. This way in each pass either the minimum or maximum value (depending on your swap condition) bubbles to one end of the array.

In your code specifically this one

 if (arr[c] > arr[r])
 {
     swap(&arr[c], &arr[r]);
 }

the value of r remains same for each complete iteration of the inner loop. That means you are not comparing two consecutive indexes as seen in above simulation but rather comparing one index to the rest of array one by one which is not how bubble sort works. You should have compared arr[c] with arr[c+1]

Even though your code logic is a bit flawed but running your code gives correct output once you change

for (c = 0; c <= MAX - r - 1; c++)

with

for (c = 0; c <= MAX - 1; c++)

as Fab already highlighted in his answer. The reason is that the way you are iterating and comparing c and r requires you that the inner loop always runs full length of the array for the output to be correct. In a proper bubble sort algorithm, this modification is not necessary as you will see below in the correct solution.

Well even after all this your code is still not bubble sort and the worst part is that if given an already sorted array your code will rearrange it (swaps some indexes) and then sort it back which clearly should not happen.

Here is an example. Lets say I have an array [1 , 2 , 3] and sort it using your logic. This is what will happen in both cases.

Case 1 for (c = 0; c <= MAX - r - 1; c++)

1 2 3 (initial array)
-----
3 1 2 (1st pass)
1 3 2 (2nd pass)
1 3 2 (3rd pass / final output)

Case 2 for (c = 0; c <= MAX - 1; c++)

1 2 3 (initial array) 
-----
3 1 2 (1st pass)
1 3 2 (2nd pass)
1 2 3 (3rd pass / final output)

As you can see in both cases a well sorted array is still being swapped and resorted which is clearly not necessary and we definitely don't want this.

Here is the correct version of your bubbleSort method

int bubbleSort(int arr[], int length, int arraySelect)
{
    int r = 0;
    int c = 0;
    for(r = 0; r < MAX - 1; r++)
    {
        for (c = 0; c < MAX - r - 1; c++) 
        {
            if (arr[c] > arr[c+1])
            {
                swap(&arr[c], &arr[c+1]);
            }

        }
    }

    return arr[arraySelect];
}

All I did was replace arr[r] with arr[c+1] so now it compares consecutive indexes and replaced <= with just < because since we are comparing consecutive indexes we don't want arr[c+1] to go out of bounds. That is why we always stay one index behind the final index.

Hope this helps. Good luck.

Answer 2

Try this

int bubbleSort(int arr[], int length, int arraySelect)
{
       int r = 0;
            int c = 0;
            for(r = 0; r <= MAX - 1; r++)
            {
                for (c = 0; c <= MAX - 1; c++) // note how I changed MAX - r - 1
                {
                    if (arr[c] > arr[r])
                    {
                        swap(&arr[c], &arr[r]);
                    }

                }
            }
        return arr[arraySelect];
    }