3
\$\begingroup\$

I've written an interrupted bubble sort, which prints the intermediate result after some specified number of iterations of bubble sort. But I seem to have an speed issue. Could anyone help me spot some places that need to be optimized or are just plain wrong?

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <sstream>

using std::cout;
using std::endl;
using std::string;
using std::vector;
using std::ifstream;
using std::stoi;
using std::stringstream;

template<typename T>
void printVector(vector<T> vect) {
    for(int i = 0; i < vect.size(); i++) {
        if(i == 0) {
            cout << vect[i];
        } else {
            cout << " " << vect[i];
        }
    }
    cout << endl;
}

template<typename T>
void swap(T &elementOne, T &elementTwo) {
    T temp = elementOne;
    elementOne = elementTwo;
    elementTwo = temp;
}

void bubbleSort(vector<int> numbers, long int iterations) {
    for(int i = 0; i < iterations; i++) {
        for(int j = 0; j < numbers.size(); j++) {
            if(numbers[j] > numbers[j + 1]) {
                swap(numbers[j], numbers[j + 1]);
            }
        }
    }
    printVector(numbers);
}

void parse(string line) {
    size_t delimiterPos = line.find("|");
    long int iterations = stol(line.substr(delimiterPos + 1));
    string numbersString = line.substr(0, delimiterPos - 1);

    stringstream numbersSS(numbersString);
    vector<int> numbers;
    int tempNum;
    while(numbersSS >> tempNum) {
        numbers.push_back(tempNum);
    }
    bubbleSort(numbers, iterations);
}

int main(int argc, const char * argv[]) {
    ifstream file(argv[1]);
    string line;
    while(getline(file, line)) {
        parse(line);
    }
    return 0;
}
\$\endgroup\$
4
  • 2
    \$\begingroup\$ A speed issue with bubble sort? That seems hard to believe... :-) \$\endgroup\$ Jan 28, 2016 at 23:18
  • \$\begingroup\$ FeelsBadMan the problem says to use bubble sort :( \$\endgroup\$ Jan 28, 2016 at 23:21
  • \$\begingroup\$ The best way to speed up a bubble sort is to use a better algorithm. \$\endgroup\$
    – Edward
    Jan 28, 2016 at 23:28
  • \$\begingroup\$ see also: Ruby Interrupted Bubble Sort. \$\endgroup\$
    – greybeard
    Jan 29, 2016 at 8:19

4 Answers 4

2
\$\begingroup\$
  • Single Responsibility

    As written, parse parses data and sorts them. This is plain wrong. Same goes for bubbleSort which sorts and prints. I recommend to change parse to

    long int parse(string line, vector<int>& numbers);
    

    and use it as in

    vector<int> data;
    while (getline(file, line)) {
        long int iterations = parse(line, data);
        bubbleSort(data, iterations);
        printVector(data);
    }
    
  • Kudos for not using namespace std!

  • The code seems to implement interrupted bubble sort correctly. I don't really understand the expected outcome of the assignment so no comments on the speed.

\$\endgroup\$
2
\$\begingroup\$

printVector

  1. It should take the vector as a reference - there is no need to copy the entire vector just to print it.

  2. You should make use of the newer features of the C++ language which were introduced since C++11, like auto and range-based for loops.

  3. You can remove some conditional statements from the implementation by adjusting the logic slightly.

Overall the refactored function looks like this:

template<typename T>
void printVector(vector<T> &vect) {
    string separator = "";
    for (auto const &T item : vect) {
        cout << separator << item;
        separator = " ";
    }
    cout << endl;
}

swap

No need to re-invent the wheel. Use std::swap instead.


bubbleSort

  1. You pass in the vector by value which means a copy of the original vector is passed in. This means the sort will not be visible outside of the function. So if you were to move printVector outside of bubbleSort you will see that it prints the unsorted original vector. You either need to pass the vector as a reference or return the sorted copy from the function.

  2. int is not guaranteed to be able to index all items in a vector. You should use vector<T>::size_type for the index variable.

  3. You can avoid the whole indexing by using iterators and iter_swap.

The refactored function looks like this:

void bubbleSort(vector<int> &numbers, long int iterations) {
    for(int i = 0; i < iterations; i++) {
        auto end = numbers.end() - 1;
        for (auto it = numbers.begin(); it != end; ++it)
        {
            if (*it > *(it + 1)) {
                std::iter_swap(it, it + 1);
            }
        }
    }
}
\$\endgroup\$
3
  • \$\begingroup\$ (Starting each iteration at numbers.begin() is not exactly bubble sort.) \$\endgroup\$
    – greybeard
    Jan 29, 2016 at 9:01
  • \$\begingroup\$ @greybeard: For all I know it is, and wikipedia agrees too. \$\endgroup\$
    – ChrisWue
    Jan 30, 2016 at 0:20
  • \$\begingroup\$ Sorry, must have been confused: not stopping one element earlier than in the previous iteration is non-standard, even if the source quoted dubs that "optimized". \$\endgroup\$
    – greybeard
    Jan 30, 2016 at 9:45
1
\$\begingroup\$

Out of bounds

    for(int j = 0; j < numbers.size(); j++) {
        if(numbers[j] > numbers[j + 1]) {

When j reaches numbers.size() - 1, you will read past the end of your vector.

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

There's no need to write your own swap() function. You can use std::swap().

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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