5
\$\begingroup\$

This is the solution for a simple challenge from Hackerrank.I am just trying to solve Sorting: Bubble Sort Problem on HackerRank.

We are asked to count the number of swaps performed during a bubble sort and to print the first and last item of the ordered vector.

Sample input

3
3 2 1

First line is the number of elements in the vector, the second line is the vector

Expected output

Array is sorted in 3 swaps.
First Element: 1
Last Element: 3

Code

I've implemented my solution in C++ and would love to hear what your feedback and what could I have done cleaner

#include <iostream>
#include <vector>
#include <algorithm>

using big_int = long long;

struct answer {
    std::size_t count;
    big_int first_element;
    big_int last_element;
};

template<class T>
answer bubble_sort(std::vector<T> &v) {
    std::size_t swap_count = 0;
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v.size() - 1; j++) {
            if (v[j] > v[j + 1]) {
                std::swap(v[j], v[j + 1]);
                swap_count++;
            }
        }
    }
    return answer{swap_count, v[0], v[v.size()-1]};
}

int main(int argc, char** argv) {
    int n;
    std::cin >> n;
    std::vector<big_int> v(n);
    for (int i=0; i<n; i++) {
        std::cin >> v[i];
    }

    auto answer = bubble_sort(v);
    std::cout << "Array is sorted in " << answer.count         << " swaps.\n"  
              << "First Element: "     << answer.first_element << "\n"
              << "Last Element: "      << answer.last_element;

}
\$\endgroup\$
3
  • \$\begingroup\$ Can you please Add link of this problem to your Question ? \$\endgroup\$ Commented Apr 13, 2020 at 16:54
  • \$\begingroup\$ @AhmedEmad I've updated it with the link \$\endgroup\$ Commented Apr 13, 2020 at 16:57
  • \$\begingroup\$ I saw and i have edited some changes and will support your question to find solution for it,Good Luck! @Blasco \$\endgroup\$ Commented Apr 13, 2020 at 17:33

2 Answers 2

Reset to default
3
\$\begingroup\$

Your answer should also be a template struct. It contains first and last element of type big_int but in the bubble _sort function it is constructed with template argument type T.

template<class T>
struct answer {
    std::size_t count;
    T first_element;
    T last_element;
};

But actually maybe the structure Is redundant because first And last element can Always easily be accessed inside the sorted container. Or it could at least contain just references to those elements instead of their copies in case the template argument T is something more complex then long long.

auto count = bubble_sort(v);
auto & first = v[0];
auto & last = v[v.size - 1];

Further instead of accepting vector<T>, you could accept two iterators of template argument type as Is common with many standard functions and allows to work not only for any type of container but also for just a range within a container.

template<class Iterator>
std::size_t bubble_sort(Iterator from, Iterator to);

// ...

auto count = bubble_sort(v.begin(), v.end());
\$\endgroup\$
3
  • \$\begingroup\$ Nitpick: s/iterator/random access iterator; also s/container/container with random-access iterator \$\endgroup\$ Commented Mar 24, 2020 at 1:25
  • \$\begingroup\$ @L.F. good point, but I don't think we need to restrict to random access containers. I think any forward Iterator Is enough for the sorting itself. Random access Iterator Is only needed for constant time access to the first and last element. But actually some containers have constant access to first and last elements but not the other elements (like doubly linked list). \$\endgroup\$ Commented Mar 24, 2020 at 8:29
  • \$\begingroup\$ Oops, didn't realize bubble sort doesn't need random access. Sorry! I think forward iterator is enough then - since we are copying iterators and visiting the elements multiple times. \$\endgroup\$ Commented Mar 24, 2020 at 8:30
2
\$\begingroup\$

Overall, your code looks great. It's nicely structured, and having a well-defined answer type makes immediately clear what the question is about.

At the bottom of the code, i=0 is missing some spaces.

You can improve the speed of the bubble sort by 50% by not counting j from 0 to size but only from 0 to size - 1 - i, since the last few elements are already bubbled up and therefore don't change anymore.

For testing, you should add another counter for the number of comparisons.

To test that your code is indeed correct, you should add an automatic test that takes a large array, fills it with 0 to size and shuffles the array. After sorting it should be the same as before.

I'm not sure whether the C++ compiler is smart enough to know that the vector's size doesn't change during the bubble sort. To get a simple performance boost, compute v.size() once and store it in a local variable. Measure the performance difference using a large array that is already sorted.

\$\endgroup\$
3
  • \$\begingroup\$ Is it faster to cache the size of std::vector? The answers seem to suggest no. \$\endgroup\$ Commented Mar 23, 2020 at 0:42
  • 1
    \$\begingroup\$ From my understanding the compiler should optimize that, right? I've just checked, and with the default O0 it is true that one can see the size() calls. With O3 there isn't even a call to the function that I've defined bubble_sort(), I also see no calls to size() everything is optimized away \$\endgroup\$ Commented Mar 23, 2020 at 11:54
  • \$\begingroup\$ As I said, "I'm not sure". It's good that everything is optimized away, I wouldn't have expected this though since the compiler needs quite a lot of information to decide all this. \$\endgroup\$ Commented Mar 23, 2020 at 20:58

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.