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\$
  • 2
    \$\begingroup\$ A speed issue with bubble sort? That seems hard to believe... :-) \$\endgroup\$ – Jerry Coffin Jan 28 '16 at 23:18
  • \$\begingroup\$ FeelsBadMan the problem says to use bubble sort :( \$\endgroup\$ – yoprogrammer Jan 28 '16 at 23:21
  • \$\begingroup\$ The best way to speed up a bubble sort is to use a better algorithm. \$\endgroup\$ – Edward Jan 28 '16 at 23:28
  • \$\begingroup\$ see also: Ruby Interrupted Bubble Sort. \$\endgroup\$ – greybeard Jan 29 '16 at 8:19
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.

| improve this answer | |
\$\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);
            }
        }
    }
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ (Starting each iteration at numbers.begin() is not exactly bubble sort.) \$\endgroup\$ – greybeard Jan 29 '16 at 9:01
  • \$\begingroup\$ @greybeard: For all I know it is, and wikipedia agrees too. \$\endgroup\$ – ChrisWue Jan 30 '16 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 '16 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.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$

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.