Expected Values From Bubble Sort

Bubble sort is a sorting algorithm that can sort an array of numbers in increasing order. In each of its iterations, it starts at the first element of the array and compares it with the adjacent element. If two adjacent elements are not in increasing order, they get swapped. The iteration continues from the first element to the second last element. The iteration ends when the last element is reached. A new iteration begins only if there was at least one swapping in the last iteration. The pseudocode is as follows:


This is a companion discussion topic for the original entry at https://toph.co/p/expected-values-from-bubble-sort