BubbleSort Complexity

[shamieh]

I'm a little confused. I know that the complexity of BubbleSort is (n(n+1))/2 , but my question is:

Suppose I have an array, I understand how passes work - but If I need to find the "theoretical search statistics" would I just count how many passes I have and then plug the # of passes into "n"?

[Peppercorn142]

#include <iostream>

using namespace std;

int main()
{
	int arrTest[] = {22, 33, 101, 12, 40};
	bool sorted = false;
	bool swapped = false;

	for (; !sorted ;)
	{
		swapped = false;
		for (int i = 0; i < 4; ++i)
		{
			if (arrTest[i] > arrTest[(i + 1)])
			{
				int buff = arrTest[i];
				arrTest[i] = arrTest[(i + 1)];
				arrTest[(i + 1)] = buff;
				swapped = true;
			}
		}
		if (!swapped) sorted = true;
	}

	for (int j = 0; j < 5; ++j)
	{
		cout << arrTest[j] << endl;
	}

	getchar();
	return 0;
}

Test this out and see, although you should try playing around, see what happens when you change things around, or add in user input for the array.

[shamieh]

Is getchar(); some kind of pre-defined library function? It's acting like it's not declared in the scope. What library should I include? By the way I am working with PuTTy

[MiiNiPaa]

std::getchar(); is in <cstdio> header

[shamieh]

I got it to work, but this algorithm isn't really helping me. See, I already understand how Bubble Sort works. I need to understand WHAT i would plug into the value of n. I also need to find out which formula to use..Worst Case,Best Case,Average Case, or its On the order notation.

[MiiNiPaa]

n is the amount of elements you are sorting.

I also need to find out which formula to use..Worst Case,Best Case,Average Case

That depend on what do you need. I believe names are self-descriptive.

O(n) notation is used when you need asymptotic complexivity or the order of magnitude of how execution time depends on number of elements when n → ∞

[shamieh]

Thank you! Well I'm not sure which I need because it just says to calculate the Theoretical sort statistics...I'm so confused.. Would that just be the general formula of Bubble Sort which would be what?

[MiiNiPaa]

I believe you will need average case: it is statistical average of multiple runs on random data.

[shamieh]

Thank you so much for your help! So I would just take the amount of elements I am sorting which I can call as "n" and then plug them in to the average case which is n^2? So, if I had 3 elements 1 3 2 , I would have actual sort stats: 3, and theoretical sort stats: 9 correct?

[MiiNiPaa]

It is asymptotical values. They are not representative on small values.

[shamieh]

So are you saying that I would not be able to find the average case if I had only 2 elements? I don't understand...what does n have to be greater than for me to use the theoritical sort stats?

[shamieh]

nvm, i figured it out.