Loading

Algorithms: Analyzing Bubblesort

Analyzing Bubblesort

In this Algorithms video tutorial, we perform a time-complexity analysis of the bubblesort algorithm. We begin with the code below that runs a bubblesort on the array "iaArray". Specifically, the entire bubblesort is contained in the nested for-loops.

#include <iostream>

void Print(int iSize, int iaArray[]) {
    using namespace std;
    for (int i = 0; i < iSize; ++i) {
        cout << iaArray[i] << " ";
    }
     cout << endl;
}

int main()
{
    using namespace std;

    int iaArray[] = {35, 8, 24, 15, 16, 86, 3, 45, 67};

    int iN = sizeof(iaArray)/sizeof(int);
    Print(iN, iaArray);

	// The Bubblesort loops
    for (int iLast = iN - 1; iLast > 0; --iLast) {
        for (int iComp = 0; iComp < iLast; ++iComp) {
            if (iaArray[iComp] > iaArray[iComp + 1]) {
                int iTemp = iaArray[iComp];
                iaArray[iComp] = iaArray[iComp + 1];
                iaArray[iComp + 1] = iTemp;
            }
        }
    }

    Print(iN, iaArray);
    cin.get();
    return 0;
}

We want to determine how many times the code executes an operation with respect to the size of the array that we are sorting. Since the code inside the for-loops does not not depend on the size of the array, we can consider it as a single section and ask how many times it executes. When performing an anaysis, we want to know what part of the code is executed most frequently, and what code depends on input parameter, in this case the size of the array.

For the purposes of anaysis, we will call the array size "n" and ask how many times a the inner code block executes as we vary the value of "n." In keeping with the notation that we introduces, we will call the number of times the algorithm executes the code block f(n), since it is a function of "n." It is not hard to see that the inner loop executes a total of (n-1) + (n-2) + ... + 2 + 1 times. This is an arithmetic series, which sums to (n-1)n/2 = n^2/2 - n/2. So, that f(n) = n^2/2 - n/2. Since we want the to analyze f(n) in terms of a simpler function, it is natural to use g(n) = n^2. So, that we will prove that the time-complexity of the bubblesort, which is given by f(n), has a running time of big theta of n^2. This is illustrated below.

Recall the definition of big theta, which is given below. In order to show that f(n) is big theta of g(n) = n^2, we need to find positive constants c1 and c2 nad a postive integer n0 that fits the definition. It is not hard to see that any value of c1 that is greater than of equal to .5 will work. Likewise, any value of c2 that is less than .5 will work. So, we choose c1 = 1 and c2 = 1/4. Then we can find our value for n0.

Looking at a table of the first few values below, it appears that n0 = 2, will work to satisfy our definition for big theta of n^2. Since the case n = 2, satisifies our inequalities. It remains to be shown that if we assume the n = k case for k greater than or equal to 2, this implies the n = k+1 case. This will complete the induction proof and show that the bubblesort is big theta of g(n) = n^2.

Below, we give a proof of the first inequality. We begin with the left side and substitute to get (k+1)^2. Then, we expand the product, we substitute c1*g(k) for k^2. Next, we use the inequality for the kth case. For the next step, we substitute the value of f(k) and simplify. Then, we use the fact that 3k/2 + 1 > k/2, for k greater than or equal to 2. Finally, we observe that this is equal to f(k+1) to complete the proof.

The second inequality is proven below. Again, we begin with the left-side, substitute, and expand the product. For the next step, we observe that 1/4(k^2) = c2*g(k). Then we use the inequality for the kth case and substitute the value of f(k) and simplify. Next, we use the fact that 1/4 < k/2. Finally, we finsh the proof by observing that this is the value of f(k+1).

With both inequalities proven, we have shown that the bubblesort algorithm has big theta of n^2 run-time.