Specify how many times elements of array will be compared [Bubble sort]

[Snape]

Hi there,
I have to specify how many times will be compared the two array elements in Bubble sort.

Array[1,...n]

1. for i=1 to n-1
2. do for j=1 to n-i
3. do if A[j]>A[j+1]
4. then swap A[j] with A[j+1]

I wonder how I can specify that how many times if statement (in line 3)will be used.
It depends how many data we have(array length), how much it is not sorted, how big data is e.g. -1000 to 1000.Is not it?
What I have done?
I simulated this situation in Java.
1000 times I filled the array with (random.nextInt) data 0 to 9, -9 to 9, 0 to 99, -99 to 99 to 10 and 100 array length.
I simulated 10 times each situation.
Results:
array length = 10
Data Average compare
0 to 9 20
-9 to 9 21
0 to 99 22
-99 to 99 22


array length = 100
Data Average compare
0 to 9 2203
-9 to 9 2342
0 to 99 2452
-99 to 99 2461

So when the array length is 10 average=(near)length*2 but when array length is 100 average=(near)length*2,3

Should it help me or this information is worthless?

[2kaud]

There are various papers analysing bubble and other sorts available on the internet. eg
http://www.peter-eigenschink.at/blog...-bubble-quick/
http://stackoverflow.com/questions/1...ed-bubble-sort
http://cs.stackexchange.com/question...rithm-analysis

A google search for bubble sort analysis will show others.

[Snape]

Ok thank you very much. Can I ask you something? Why they write that time only depends on array length not data. I thought that numbers 5 4 8 7 will be more helpful than 1 -500-1 278 They do not explain why

[laserlight]

Can I ask you something? Why they write that time only depends on array length not data. I thought that numbers 5 4 8 7 will be more helpful than 1 -500-1 278 They do not explain why

You're looking at a version of bubble sort that has a fixed number of iterations based on the number of elements. Therefore, even if the elements are nearly sorted, the same number of iterations will be made. What would be different is that there will be fewer swaps, but there will be the same number of comparisons since you do the same number of comparisons per iteration.

If you used a version of bubble sort that terminates when it detects that no swaps have been made on the more recent iteration, then indeed the algorithm will perform better on a nearly sorted array of elements. However, compared to the algorithm you showed, it will still have the same performance in the worst case.

[Snape]

Ok thank you. Now I get it

[razzle]

So when the array length is 10 average=(near)length*2 but when array length is 100 average=(near)length*2,3

Should it help me or this information is worthless?

Your test shows that the algrithm has O(N^2) complexity indeed.

When you make the array 10 times bigger the test takes 10^2 = 100 times longer.

This trend should stick. For example if you make the array 25 times larger (array length = 250) the test will take 25^2 = 625 times longer.

Note that complexity measures are not exact, they show the overall trend. But it's a valuable hint in practice as to how your program will scale when the the input load is increased (like for example a much bigger array is used).