Sorting an array of integers in C++

Question

This is a follow up to my previous post as it contained a lot of errors and wasn't accurate.

I am using the Bubble sort algorithm to sort an array of integers and I would like to know whether I could optimize it in any way.

#include<iostream>
void printarr(int *arr,const int siz){
 for(int i = 0;i < siz;i++) std::cout << arr[i] << " ";
 std::cout << "\n";
}
int main(){
 const int siz = 6;
 int arr[siz] = {4,6,3,1,3,8};
 std::cout << "Before sort\n";
 printarr(arr,siz);
 for(int i = 0;i < siz;i++){
 for(int j = i+1;j < siz;j++){
 if(arr[i] > arr[j]){
 int temp = arr[i];
 arr[i] = arr[j];
 arr[j] = temp;
 }
 }
 }
 std::cout << "After sort\n";
 printarr(arr,siz);
}
```

• user228914: linked: Sorting an array in C++ using bubble sort
• jamesqf: Really, the only way to optimize a bubble sort is to use a different algorithm. Which is a principle applicable in many cases :-) Unless you're doing this as a class assignment or similar, your best option is probably to call the library qsort function.
• phuclv: @jamesqf std::sort would be much better since the compiler knows the input type and can optimize accordingly
• jamesqf: @phuclv: Same principle. qsort is much simpler to use, IMHO.
• Loki Astari: @jamesqf Not true. Bubble sort has an optimization that when it holds makes the algorithm O(n) (beating all other forms). Bubble sort also has a very very very low overhead. Making it exceptionally good for sorting small list of numbers where it regularly outperforms your more complex sorts.

Answer 1

First thing first, make it into a function, such that your main will be

int main(){
 const int siz = 6;
 int arr[siz] = {4,6,3,1,3,8};
 std::cout << "Before sort\n";
 printarr(arr,siz);
 sort(arr, siz);
 std::cout << "After sort\n";
 printarr(arr,siz);
}

---

Since you've tagged it c++, do not use c-style array. Use std::vector. Use std::swap. Currently, it is plain old c. Nothing wrong with it, except the tag.

---

Optimization wise, well, bubble sort does not deserve it.

• user228914: Just to clarify, another review says that this isn't bubble sort?
• L. F.: Indeed. From that answer: Bubble sort swaps neighbors.
• jamesqf: Why not use arrays in C++? They're a perfectly valid language feature. Just because you have something else, such as vectors, doesn't mean you have to use it, especially when it makes your code more complicated, harder to understand, and possibly less efficient.
• stefan: @jamesqf "Why not use arrays in C++?" See C++ Super FAQ isocpp.org/wiki/faq/containers#arrays-are-evil
• Rasmus Damgaard Nielsen: @jamesqf If performance is an issue, std::array will have the exact same performance as a c style array without the numerous pitfalls.

Answer 2

That's not bubble sort. More like an overly eager selection sort. Bubble sort swaps neighbors.

Answer 3

After all the suggestions I turned my old code into the following:

#include<iostream>
#include<vector>
void printvec(std::vector<int> vec){
 for(int i:vec){
 std::cout << i << ' ';
 }
 std::cout << '\n';
}
std::vector<int> sortvec(std::vector<int> &vec){
 int temp = 0;
 for(long unsigned int i = 0;i < vec.size();i++){
 for(long unsigned int j = i+1;j < vec.size();j++){
 if(vec[j] < vec[i]){
 temp = vec[i];
 vec[i] = vec[j];
 vec[j] = temp;
 }
 }
 }
 return vec;
}
int main(){
 std::vector<int> my_vec{7,2,4,6,7,2,3,6,3,2,1,4,6,9,2,3,5,8,6,4,3,2,2,4,5,7,2,8,4,6,3,3};
 my_vec = sortvec(my_vec);
 printvec(my_vec);
 return 0x1;
}

• I changed the container type from C-style array to std::vector<int>.
• I moved the sort algorithm into a separate function and then.

Both of them were suggested by @vnp

• Rasmus Damgaard Nielsen: 3 comments here: 1. You still dont use std::swap. Why? 2. (This is probably up for discussion) why use vec in the name of the functions? This is already part of the signature. 3. If you pass vec by reference and sort in place, there is no reason to return vec by value, this just creates an extra copy unnecessarily.
• Rasmus Damgaard Nielsen: Also: 4. This is still selection sort and not bubble sort. 5. If you insist on using std::swap, declare temp as close as possible to the usage, ie in the inner for loop.
• Erbureth: 6. Use iterators instead of direct indices (and the type of the indices is std::size_t anyway)
• Loki Astari: New code that needs reviewing means a new question.