Why is the length usually calculated this way for BubbleSort algorithm?

Question

So I'm just trying to understand how bubblesort (it may help me with other algorithms when I see this kind of stuff as well) works with the nested for loop.

I noticed that most people will do the loops like so:

public static void BubbleSort(int[] arr, int arr_size)
{
    int i, j, temp;
    bool swapped;
    for (i = 0; i < arr_size - 1; i++)
    {
        swapped = false;
        for (j = 0; j < arr_size - i -1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (swapped == false)
        {
            break;
        }
    }            
}

I have done it like this (only slightly different; note the nested loop size check:

public static void BubbleSort(int[] arr, int arr_size)
{
    int i, j, temp;
    bool swapped;
    for (i = 0; i < arr_size - 1; i++)
    {
        swapped = false;
        for (j = 0; j < arr_size - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (swapped == false)
        {
            break;
        }
    }            
}

And it seems to work with every check I've done so far.

I guess to sum it up, I am wondering why the first loop would be the size - 1 (I know this is because of the whitespace at the end) and the nested loop will be the size - i - 1 (at least I have seen this a lot). Thanks for any feedback !

Answer 1

The effect of the inner loop:

for (j = 0; j < arr_size - i - 1; j++)
{
    if (arr[j] > arr[j + 1])
    {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swapped = true;
    }
}

is finding the maximum element in the array and placing it to the last position. Hence, for i == 0 (the index from the outer loop), it moves it to the last array position. For i == 1, the array's overall maximum element is already at the last array position, and hence it does not need to be processed again. For i == 2 etc. the situation is the same. In other words, the array is being sorted from 'backward' by 'bubbling' (hence the algorithm's name) the maximum elements up each iteration.

There is a nice step-by-step example on Wikipedia.

In your second example, by omitting the - i in the for loop clause, you are just unnecessarily checking array elements that are already in place from previous (outer loop) iterations and hence cannot change anymore.