3
\$\begingroup\$

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);
}
```
\$\endgroup\$
5
  • \$\begingroup\$ linked: Sorting an array in C++ using bubble sort \$\endgroup\$ – Parekh Sep 4 '20 at 21:19
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – jamesqf Sep 5 '20 at 18:03
  • 2
    \$\begingroup\$ @jamesqf std::sort would be much better since the compiler knows the input type and can optimize accordingly \$\endgroup\$ – phuclv Sep 5 '20 at 23:51
  • \$\begingroup\$ @phuclv: Same principle. qsort is much simpler to use, IMHO. \$\endgroup\$ – jamesqf Sep 6 '20 at 19:18
  • \$\begingroup\$ @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. \$\endgroup\$ – Martin York Sep 9 '20 at 20:46
9
\$\begingroup\$

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 , do not use -style array. Use std::vector. Use std::swap. Currently, it is plain old . Nothing wrong with it, except the tag.


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

\$\endgroup\$
6
  • \$\begingroup\$ Just to clarify, another review says that this isn't bubble sort? \$\endgroup\$ – Parekh Sep 4 '20 at 21:32
  • 1
    \$\begingroup\$ Indeed. From that answer: Bubble sort swaps neighbors. \$\endgroup\$ – L. F. Sep 5 '20 at 11:18
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – jamesqf Sep 5 '20 at 21:40
  • \$\begingroup\$ @jamesqf "Why not use arrays in C++?" See C++ Super FAQ isocpp.org/wiki/faq/containers#arrays-are-evil \$\endgroup\$ – stefan Sep 5 '20 at 22:08
  • \$\begingroup\$ @jamesqf If performance is an issue, std::array will have the exact same performance as a c style array without the numerous pitfalls. \$\endgroup\$ – Rasmus Damgaard Nielsen Sep 6 '20 at 8:02
5
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Rasmus Damgaard Nielsen Sep 6 '20 at 8:03
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Rasmus Damgaard Nielsen Sep 6 '20 at 8:11
  • 1
    \$\begingroup\$ 6. Use iterators instead of direct indices (and the type of the indices is std::size_t anyway) \$\endgroup\$ – Erbureth says Reinstate Monica Sep 6 '20 at 9:37
  • \$\begingroup\$ New code that needs reviewing means a new question. \$\endgroup\$ – Martin York Sep 9 '20 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.