C++ Interrupted Bubble Sort

Question

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;
}

• Jerry Coffin: A speed issue with bubble sort? That seems hard to believe... :-)
• yoprogrammer: FeelsBadMan the problem says to use bubble sort :(
• Edward: The best way to speed up a bubble sort is to use a better algorithm.
• greybeard: see also: Ruby Interrupted Bubble Sort.

Answer 1

• 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.

Answer 2

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);
 }
 }
 }
}

• greybeard: (Starting each iteration at numbers.begin() is not exactly bubble sort.)
• ChrisWue: @greybeard: For all I know it is, and wikipedia agrees too.
• greybeard: 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".

Answer 3

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.

Answer 4

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