[shamieh]

Thank you so much! you all are so helpful!!

[Skydiver]

Why aren't the comparisons on lines 3 and 4 counted? They too are comparisons right? Or is there a magic rule when computing complexity that loop condition comparisons don't count?

[shamieh]

j - size - 1 - i is in the second condition. But I only need to count after line 4 as far as "comparisons"

[Skydiver]

Why?

So if the code were written as:

int i = 0;
int j = 0;
while (true)
{
    if (items[j] > items[j+1])
        Swap(j, j + 1);
    j++
    if (j >= j - 1 - i)       // does this comparison not count?
    {
        j = 0;
        i++
        if (i >= size - 1)    // does this comparison not count?
            break;
    }
}

[shamieh]

So if I had for example a list of these numbers : 5 6 7 8 1 2 4 10 23

AFTER i sorted them with bubble sort I would obtain these results:

New list: 1 2 4 5 6 7 8 10 23

Theoretical Sort Statistics: 45 element comparisons, 9 element movements
Actual Sort Statistics: 36 element comparisons, 12 movements

The Theoretical comparisons would be the average case time complexity of Bubble sort with n being the number of elements in the List.
Bubble Sort Avg TC = (n(n+1)) / 2

Thus: 9 elements so, (9(9+1)) / 2 = 90 / 2 = 45 element comparisons, and 9 movements because we have 9 elements.

In addition, if I used Actual Sort statistics, I would count every single comparison made, thus :
every literal comparison made would be 36 (even ones already in order) and actual movements would be literal SWAPS

This post has been edited by shamieh: 15 March 2014 - 08:54 PM

[Skydiver]

Ah, I see. You are counting "element comparisons", not just any "comparison".

Umm. As a quick aside, you do know that the code you posted is not Bubble Sort, right?

Read about The Real Bubble Sort.

[shamieh]

Wow...That is very interesting. Wait until I tell my teacher about this after spring break