UVa 120004, Bubble Sort

Restructuring The Problem, More Conveniently

Before tackling a solution, We need to reformulate the given problem. You might consider this a reduction to a form which is more convenient to solve. The problem states We are given an array of size n whose elements are {1, 2, .., n} and are distinct. That concludes the given array a is a permutation of {1, 2, .., n}. If we listed all these permuations and computed bubbleCounts on each, Then taken their average, That would be the answer to UVa’s problem. Running findSwaps() infinitely is just a fancy way of describing our

Definition: Average bubble counts of all permutations.

Observations

On n = 2,

average = $\frac{0+1}{2}$ = $\frac{1}{2}$

On n = 3,

average = $\frac{0+1+1+2+2+6}{6}$ = 2

On n = 4,

average = $\frac{0+1+1+2+2+3+1+2+2+3+3+4+2+3+3+4+4+5+3+4+4+5+5+6}{24}$ = 3

Symmetry

Consider the case of $n=3$. Notice that the least bubbleCount is the first one accounting for zero, and the greatest bubbleCount is the last one accounting for 3. You could see that for each permutation of bubbleCount 1, There is a corresponding permutation of bubbleCount 2. The sum of 1 and 2 is also 3 !

Note also that the corresponding permutation is exactly like the other one but inversed. For instance permutation <3, 1, 2> is the inversed in order of <2, 1, 3>.

So, we could divide our list of permutations into two halves such that a pair’s sum equals $min(bubbleCount) + max(bubbleCount)$. Clearly, There are a total of $n!$ permutations. The number of those pairs is half of total permutations. Hence, total sum of bubble counts is $\frac{n!}{2} \times (min(bubbleCount) + max(bubbleCount))$. Now we divide that total sum on total number of permutations to get the average of all bubbleCounts. So, The formula is now $\frac{(min(bubbleCount) + max(bubbleCount))}{2}$. Clearly, least bubbleCount is always zero, As we have the permutation which is already sorted. What about the greatest one? The worst case is the permutation sorted inversely. In such case, The first iteration, i.e outer loop, accounts for $(n-1)$ bubbles. The second itertaion accounts for $(n-2)$, and so on untill an iteration accounts for exactly one bubble. So, $max(bubbleCount)$ = (n-1) + (n-2) + .. + 1 = $\frac{n \times (n-1)}{2}$. Hence, Our conjectured formula is

$$\frac{0 + \frac{n(n-1)}{2} }{2} = \frac{n(n-1)}{4}$$

Check this for more information about gaussian’s famous equation.

More Justification on Symmetry

We have shown that least bubbleCount and greatest bubbleCount among all permutations are equal to zero and (n-1) + (n-2) + .. + 1, respectively. Let’s take a deeper and more general look on why we could divide our permutations list into two halfs whereby each pair’s sum is equal to greatest bubbleCount. That pair’s permutations are also inverse of each other.

For the case of $n=3$, Pick up two permutations which are inverse of each other and try to run bubbleSort algorithm on both of them. You shall find for a permutation, The bubble counted on some pair of numbers, is not counted in the other corresponding permutation. For instance, permutation <1, 3, 2> needs one bubble swap in <3, 2> pair. For the permutation’s inverse <2, 3, 1>, There’s no need to bubble swap <2, 3> pair. That saves us one bubble swap out of three which is the maximum bubbleCount. 3 - 1 = 2, The bubbleCount of <2, 3, 1>. The same applies for any two pairs of permutations which are inverse of each other.

Accepted Source Code on UVa

#include <cstdio>

#define ll long long
#define ull unsigned ll

using namespace std;

bool checkIthBit (int n, int i) {
  if( n & (1 << i) )
    return true;
  return false;
}


int main() {
  int t, cou = 1;

  scanf("%d", &t);

  while (cou <= t) {
    int n;
    ull numerator; int denominator;

    scanf("%d", &n);

    numerator = ((ull)n*(ull)(n-1));
    denominator = 4;

    // check if nume is div by 2, and simplify rational form
    for (int i=0; i<2; ++i) {
      if (!checkIthBit(numerator, 0)) {
	numerator = numerator/2;
	denominator = denominator/2;
      }
    }

    if (denominator == 1) printf("Case %d: %llu\n", cou, numerator);
    else printf("Case %d: %llu/%d\n", cou, numerator, denominator);

    cou++;
  }
  return 0;
}

Many of those who do not appreciate math, think of it as a routine where you just follow a systematic order of operations on numbers. If you are one those, I hope this article changed, at least doubted, how you perceive it. There are a whole deep and elegant adventures still awaiting you if you delved more deeply.