I found two bubble algorithms but I not sure which one is right...

First example:

```
for (int i = 1; i < input.Length-1; i++)
    for (int j = 0; j < input.Length - 1 - i; j++)
        if (input[j] > input[j + 1])
            swap(input, j, j + 1);

```

Second example:

```
for (int i = 1; i < input.Length-1; i++)
    for (int j = 0; j < input.Length - 1; j++)
        if (input[j] > input[j + 1])
            swap(input, j, j + 1);

```

[**Wikipedia Example**](http://en.wikipedia.org/wiki/Bubble_sort)
-----------------------------------------------------------------

For input: 5 1 4 2 8

First example: 6 comparisons

Second example: 12 comparisons

> 
> **First Pass:**
> 
> 
> ( **5 1** 4 2 8 ) --> ( **1 5** 4 2 8 ), Swap since 5 > 1
> 
> 
> ( 1 **5 4** 2 8 ) --> ( 1 **4 5** 2 8 ), Swap since 5 > 4
> 
> 
> ( 1 4 **5 2** 8 ) --> ( 1 4 **2 5** 8 ), Swap since 5 > 2
> 
> 
> ( 1 4 2 **5 8** ) --> ( 1 4 2 **5 8** )
> 
> 
> **Second Pass:**
> 
> 
> ( **1 4** 2 5 8 ) --> ( **1 4** 2 5 8 )
> 
> 
> ( 1 **4 2** 5 8 ) --> ( 1 **2 4** 5 8 ), Swap since 4 > 2 **<-- Example 1 stop here**
> 
> 
> ( 1 2 **4 5** 8 ) --> ( 1 2 **4 5** 8 )
> 
> 
> ( 1 2 4 **5 8** ) --> ( 1 2 4 **5 8** )
> 
> 
> **Third Pass**
> 
> 
> ( **1 2** 4 5 8 ) --> ( **1 2** 4 5 8 )
> 
> 
> ( 1 **2 4** 5 8 ) --> ( 1 **2 4** 5 8 )
> 
> 
> ( 1 2 **4 5** 8 ) --> ( 1 2 **4 5** 8 )
> 
> 
> ( 1 2 4 **5 8** ) --> ( 1 2 4 **5 8** ) **<-- Example 2 stop here**
> 
> 
> 

Edit: when I say which one is right I mean which one is the original bubble sort
['https://Stackoverflow.com/questions/13630967', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/1424127/']
First algorithm is incorrect.
It will fail if last element in the array is not the greatest.

Specifically, iteration on 'j':

```
for (int j = 0; j < input.Length - 1 - i; j++)

```

seems to skip last element. 
If your input is {0, 2, 2, 1}
Then your input.Length = 4

for loop above will have condition j < 4 - 1 - i, where i = 1 so j < 4 - 1 - 1, so j < 2
so last j used will be j = 1, last comparison will be input[1] > input[2] -> input[3] is never compared.

you can fix it by changing for loop to j <= input.Length - 1 - i
without doing too much thinking, It looks like they're both correct, but the first one seems to do less redundant operations, and therefore takes less time to execute

The first seems to depend on the fact that your last i blocks are correct, therefore it doesn't even bother with them.