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
In a bubble sort, after the first pass, you are guaranteed that the largest value will occupy the last position in the array. This is because by definition, the bubble sort swaps the highest value toward the end of the array.

This means that on the second pass, you do not need to compare the last value again, because it is guaranteed to be larger or equal to the element in the next lower index. Likewise, after pass 2, the top two elements will be the highest values and sorted relative to one another.

By extension, after `i` passes, the `i` top elements will be in their correct positions.

The first example takes this into account, by subtracting `i` from the maximum `j` iterator value. The second example unnecessarily compares the upper elements in subsequent passes. It doesn't hurt, but it is redundant, i.e. not *optimized*. It is still a bubble sort, because it is swapping adjacent values, moving the higher valued element toward the end of the array.

Does that make sense?