Ryan D. Ryan D. - 4 months ago 18
C Question

Bubble Sort Outer Loop and N-1

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?


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.