Bubble Sort

Idea

Each sweep from left to right helps bubble up the highest element to the top.
To sort the entire array it performs N-1 sweeps. Within each sweep, you will compare adjacent elements (max of N-1 elements).

Input:
Sequence of numbers $(a1, a2, .... aN)$.

Output:
A permutation reordering $( a'1, a'2, .... a'N)$ such that $a'1 <= a'2 <= .... <= a'N$

Loop Invariant

At iteration i, the sub-array A[1..i] is
sorted and any element in A[i+1..A.size] is greater or equal to any
element in A[1..i]

Pseudo code

BUBBLE_SORT (A)
    for i = 1 to A.length // Closed interval
        for j = 1 to A.length-i // Closed interval
            if A[j] > A[j+1]
                swap(A, j, j+1)
    return

~~NOTE: We are using half open intervals with pseudo code, and in all cases we exclude the end marker and include the beginning marker.
In this case, why did we do for i = 1 to A.length and why not do for i = 1 to A.length-1. Note the cases here for ~~$I, J, J+1$

Verifying Loop Invariant

Initialization

During the initial phase, the array A is the original unsorted array. This is a trivial case where the 1st part is unsorted array and 2nd part of sorted array (of zero elements).

Maintenance

During each iteration,

for i = A.size()-2 to 0
for j = 0 to i+1

Array A range of elements is from 0 to A.size()-1.

Termination

After termination when i is 1. The array A we get would have 1st part unsorted array of 1 element (trivially sorted) and 2nd part sorted array of N-1 elements.

Code

void bubble_sort_as_per_pseudo_code (int *arr, int arr_len) {
  int i, j;
  bool swapped = false;
  //Half open interval from 0 to arr_len-1.
  //Why do u use arr_len-1, because end_index is arr_len-1
  //Couldn't you have just used "i A[j+1]) {
        swap(A, j, j+1);
        swapped = true;
      }
      // Optimization
      if (swapped == false) {
        // If there's no swapping needed, return array because its sorted
        return;
      }
    }
    swapped = false;
  }
}

void bubble_sort (int *arr, int arr_len) {
  int index = 0, index_two = 0;
  for (index = 0; index < arr_len-1; index++) {
    index_two = index+1;
    while (arr[index] > arr[index_two] && index_two < arr_len) {
      swap_elements(&arr[index], &arr[index_two]);
      index_two++;
    }
  }
}

NOTE: Why introduce loop guard for A.length-1 in code instead of A.length from pseudocode. This is because if you note the value of J from the table above, it needs to loop through till a max of N. For doing this, we can restrict the value of J and/or we can restrict the value of I.

Big-O Analysis

Outer loop goes through max N elements and inner loop goes through max N elements. So the its $O(N^2)$.