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);
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
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