I've come across many different implementations of the Bubble sort algorithm in C++. I'll list a few now (just the few lines that are different of each other) so someone can tell me the difference. I've noticed some use the while loop and it's a bit different, but the lines for going through the array are still the same.
These examples of the code are the ones that go through the array using the for loop.
Example 1:
for (int i=0; i<size-1); i++)
for (int j=i+1; j<size; j++)
//swap lines
Example 2:
for (int j=0; j<(size-1); j++)
//swap lines
So what's the difference? The second one goes through the whole array each time, and the first one goes through by 1 less each time? I know the algorithm goes through the array, swaps it and there's no point of going back to the first element of the array again, so I'm guessing the first one is better.
Also, what's the best implementation of the Bubble sort in c++ (please include code if you can)?
Bubble sort is O(n^2), and so will always have the nested loops like in Example 1, or something else equivalent to it. Example 2 will be using some other construct, perhaps recursion, to achieve the same goal.
There won't be a single best implementation. Different implementations are better in different ways. Bubble sort is sometimes used to have a sort that runs quickly on lists that are close to being in sorted order. A version that exploits this property will run much faster on ordered lists, but probably run a bit slower on lists that are completely random.