Sorting an array in C++ using Bubble sort

Question

Here is my bubble sort algorithm that I would like to improve in any way possible

#include<iostream>
int main(){
 int arr[6] = {5,2,3,7,2,6};
 int f = 0;
 int b = 0;
 for(int i = 1;i < 6;i++){
 if(arr[i] < arr[i-1]){
 f = arr[i];
 b = arr[i-1];
 arr[i] = b;
 arr[i-1] = f;
 i=1;
 }
 }
 for(int i = 0;i < 6;i++) std::cout << arr[i] << " ";
}

Anything is appreciated

• pacmaninbw: Please do not modify the question after it has been answered, it is against the code review rules.
• Sᴀᴍ Onᴇᴌᴀ: I rolled back your last edit. As pacmaninbw stated earlier: after getting an answer you are not allowed to change your code anymore. This is to ensure that answers do not get invalidated and have to hit a moving target. If you have changed your code you can either post it as an answer (if it would constitute a code review) or ask a new question with your changed code (linking back to this one as reference). See the section What should I not do? on What should I do when someone answers my question? for more information

Answer 1

Some notes:

• I would avoid running a loop while changing i inside, it is very unclear to the reader. I prefer using two nested loops.
• The swap can be done in one step less
• I would initialize a size variable and use it throughout the code instead of hard-coding 6.
• Printing the array to the console should be in a separate function (as well as the sorting function really).

#include<iostream>
int main(){
 const int sz = 6;
 int arr[sz] = {5,2,3,7,2,6};
 do{
 swapped = false;
 for(int i = 1;i < sz; i++){
 if(arr[i] < arr[i-1]){
 int tmp = arr[i];
 arr[i] = arr[i-1];
 arr[i-1] = tmp;
 swapped = true;
 }
 }
 } while(swapped);
 print_array(arr, sz);
}

• L. F.: How about using std::swap(arr[i], arr[i - 1])?
• gilad: @L.F. It is preferred to use std::swap, I would also prefer to use std::array or std::vector. I just followed the C-style code in original question.

Answer 2

You don't implement the obvious optimization to Bubble sort. If you run through the inner loop and no swapping is done then the array is now sorted.

This reduces the "Best Case" complexity to O(n) rather than the O(n^2) that you have implemented.

---

Your sort is based on integers. That is not very useful in C++ as arrays can be of nearly anything. So you should think of this as being able to sort a list of anything.

Sure you say I just change the type <int> to something I want and recompile.

Sure I say. But if you choose a type T that is large your code becomes very ineffecient becuase you make copies of the object in the middle of the loop.

 std::array<MyBigType> arr;
 int tmp = arr[i]; // You made a copy of the object here.
 f = arr[i]; // You made a copy of the object here. 
 b = arr[i-1]; // You made a copy of another object here.

So each time you are doing a swap you are making three copies of the object.

You can do better by using std::move() to move the object. Or you can use std::swap() or std::swap_iter() to do a more efficient job of moving large objects.

---

Your code assumes that you are sorting a C-array. In C++ we handle things differently we abstract away the container by referring to things with iterators. That way we can sort any type of container by simply providing the iterator.

Now different iterators have different properties and you can potentially optimze the algorithm by the type of the iterator you are using.

---

Most importantly the code does not work.
(削除) You only have a single loop. You need a nested loop (I assume some

You perform a sort of copy paste issue! (削除ここまで) I assumed it did not work because I did not understand the hack you did to simulate a second loop. It is still broken.

---

It is written in a way that makes it hard to read.
Code is designed to be read by humans. Write the code in a away that is easy to read.

• user228914: I didn't understand, why doesn't this code work? I am looking to sort an array of integers
• gilad: @Martin look at the sneaky i=1 at the end of the if, if a swap is detected then he reiterates the array which acts like a pseudo-nested- loop.
• Loki Astari: @AryanParekh See superb rain answer above. I assumed it was it was missing a loop, Turns out to be designed to be hard to read instead.

Answer 3

1. It's wrong. For example for input {5,9,3,7,2,6} you print 5 2 3 6 7 9.
2. It's not bubble sort. More like an inefficient insertion sort.
3. It's not O(n²) but only O(n³). For example for input int arr[100] = {99,98,97,...,2,1,0} you have 161,799 iterations of your loop (that's 100C3 + 99).

• user228914: Yes I had a small mistake, instead of i=1 It should be i=0

Answer 4

I would suggest to use the newer C++ stuff at least where it very obviously simplifies the code.

1. The

    int tmp = arr[i];
    arr[i] = arr[i-1];
    arr[i-1] = tmp;
   

can be written in one line instead of three:

 std::swap(arr[i], arr[i-1]);

2. std::array is just the same as the plain old array but knows the own size:

    std::array<int,6> arr = {5,2,3,7,2,6};
   

and then you can use arr.size() instead of hard coded 6 over the rest of the code. Unlike std::vector, std::array is a light structure without internal fields or heap allocations.

3. For printing the array the C++11 loop is very handy:

   for (auto a: arr) std::cout << a << " ";
   

I am not sure, maybe asking to use iterators would be too much but it would be possible to rewrite with iterators:

 std::array<int,6> arr = {5, 2, 3, 7, 2, 6};
 static_assert(arr.size() >= 2);
 auto current = arr.begin();
 auto prev = current++;
 while (current != arr.end()) {
 if (*current < *prev) {
 std::swap(*current, *prev);
 current = arr.begin();
 }
 prev = current++;
 }
 for (int a: arr) std::cout << a << " ";

This code would be beneficial when sorting something like std::deque where random access like arr[i] is not so efficient. This algorithm only needs immediate access to the current and previous positions. Let's make this its strong side.

static_assert that I added would fail at compilation time, not at runtime, if the array is too small. The size of this array is known for compiler.

• G. Sliepen: std::swap() is C++98, not exactly new anymore :)
• Loki Astari: Not only does std::swap() do it in one line but more importantly it will use move semantics rather than copy semantics. Thus for larger types (that have the appropriate move defined) it becomes much more efficient.