Bubble Sort Outer Loop and N-1

Question

I've read multiple posts on Bubble Sort, but still have difficulty verbalizing why my code works, particularly with respect to the outer loop.

for (int i = 0; i < (n - 1); i++)
{
    for (int j = 0; j < (n - i - 1); j++)
    {
        if (array[j] > array[j + 1])
        {
            int temp = array[j];
            array[j] = array[j + 1];
            array[j + 1] = temp;
         }
     }
 }

For any array of length n, at most n-1 pairwise comparisons are possible. That said, if we stop at i < n-1, we never see the final element. If, in the worst case, the array's elements (I'm thinking ints here) are in reverse order, we cannot assume that it is in its proper place. So, if we never examine the final array element in the outer loop, how can this possibly work?

Answer 1

Array indexing is done as 0 to n-1. If there are 10 elements in array, indexing will be n-1. So in first, iteration of inner loop (n-1) comparison will take place. First pass of bubble sort will bubble up the largest number to its position.

In the next iteration (n-1-1) iteration will take place and it will bubble up the second largest value to its place and so on until the whole array is sorted.

Answer 2

In this line you are accessing 1 element ahead of current position of j

 array[j + 1];

In first iteration of the loop you run j from 0 to j<(n-0-1), so last index of array which you can get is j less than n, as you accessing array[j+1]. So if you declare you array as array[n], this will get the last element for your array.