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\$ Commented Sep 4, 2020 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\$ Commented Sep 5, 2020 at 18:03
  • 2
    \$\begingroup\$ @jamesqf std::sort would be much better since the compiler knows the input type and can optimize accordingly \$\endgroup\$ Commented Sep 5, 2020 at 23:51
  • \$\begingroup\$ @phuclv: Same principle. qsort is much simpler to use, IMHO. \$\endgroup\$ Commented Sep 6, 2020 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\$ Commented Sep 9, 2020 at 20:46

3 Answers 3

Reset to default
8
\$\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\$ Commented Sep 4, 2020 at 21:32
  • 1
    \$\begingroup\$ Indeed. From that answer: Bubble sort swaps neighbors. \$\endgroup\$ Commented Sep 5, 2020 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\$ Commented Sep 5, 2020 at 21:40
  • \$\begingroup\$ @jamesqf "Why not use arrays in C++?" See C++ Super FAQ isocpp.org/wiki/faq/containers#arrays-are-evil \$\endgroup\$ Commented Sep 5, 2020 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\$ Commented Sep 6, 2020 at 8:02
4
\$\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\$ Commented Sep 6, 2020 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\$ Commented Sep 6, 2020 at 8:11
  • 1
    \$\begingroup\$ 6. Use iterators instead of direct indices (and the type of the indices is std::size_t anyway) \$\endgroup\$ Commented Sep 6, 2020 at 9:37
  • \$\begingroup\$ New code that needs reviewing means a new question. \$\endgroup\$ Commented Sep 9, 2020 at 20:52

You must log in to answer this question.