I have this function code to bubble sort an array using pointers.
However, I do not understand the second for loop (the inner one):
Why did they do p < a + n - i - 1?
void bubble_sort(int* a, int n) {
for (int i = 0; i < n; i++) {
for (int* p = a; p < a + n - i - 1; p++) { // bubble
if (*p > *(p+1)) {
int t = *p;
*p = *(p+1);
*(p+1) = t;
}
}
}
}
The comparison
p < a + n - i - 1
Is used to bound the edited portion of the array to the unsorted sub array of the array. The last i elements are excluded from being edited because these slots will consist of the i greatest elements of the array in sorted order; therefore, there is no need to check them and doing so is avoided to prevent the function from wasting time.
1 is subtracted to prevent the accessing of elements outside of the sorted portion of the array when i > 0 or to prevent the accessing of memory outside of the array when i = 0 by the line
if (*p > *(p+1)) {
If 1 was not subtracted, this would risk a SegFault when p + 1 is dereferenced.
Because you compare p and p+1 in the next line:
if (*p > *(p+1)) {
So if you have n elements, a+n points after the last element. a+n-i points after the last element in the sub array, but in this case you would compare the last element with the element after the last in the sub array. So you must stop before the last element thus: a+n-i-1
0 n-i n
array: [a-------------------------|------]
last inner: p=a+n-i-1->||<-p+1
