Measuring the time for the bubble sort algorithm

Question

I created a program that measures the time for the bubble sort algorithm to sort a list of numbers:

#include <iostream>
#include <fstream>
#include <vector>
#include <time.h>

std::vector<int> FiletoVector()
{
    std::ifstream SortFile("Number_Sort.input");

    std::vector<int> vector;
    int read;

    while(SortFile >> read)
    {
        vector.push_back(read);
    }

    return vector;
}

void PrintTime(std::string sorttype, std::vector<int> funcinput(std::vector<int>), std::vector<int> vecinput)
{
    //Start Time
    float time = clock();

    funcinput(vecinput);

    //End Time
    time = (clock() - time) / CLOCKS_PER_SEC;

    std::cout << sorttype << " took " << time << " seconds!" << std::endl;
}

std::vector<int> BubbleSort(std::vector<int> vecinput)
{
    for(int i = 0; i < vecinput.size(); i++)
    {
        for(int n = 0; n < vecinput.size(); n++)
        {
            //std::cout << vecinput[n] << " " << vecinput[n + 1] << std::endl;
            if(vecinput[n] > vecinput[n + 1])
            {
                int a = vecinput[n];
                int b = vecinput[n + 1];

                vecinput[n] = b;
                vecinput[n + 1] = a;
            }
        }
    }

    return vecinput;
}

int main()
{
    std::vector<int> nums = FiletoVector();

    //REMEMBER FUNCTION IN PARAMETER HAS NO ()
    PrintTime("Bubble Sort", BubbleSort, nums);


    /*
    //Print Ordered List and Time (Bubble)
    for(int i = 0; i < vecBubble.size(); i++) 
    {
        std::cout << vecBubble[i] << std::endl;
    }
    std::cout << time << " seconds!" << std::endl;
    */
}

As you can see the first function is to take the file (Number_Sort.input) and make it into a vector (since it can change size in elements). Then my second function is prints out the time it takes for the sorting algorithm to sort all of its data. Finally my last function is the bubble sort algorithm.

The reason I put my code in this fashion is that so I can later on learn other algorithms and put them in here, and then compare the speed that they execute them with different data sets.

But my code feels a bit messy, I feel like I can further make it more readable, specifically the PrintTime function and all of those parameters. I am not even sure if I did the funcinput(std::vector<int>) in a proper way. I had to make the input of the bubble sort function as a separator parameter (I could not do PrintTime("Bubble Sort", BubbleSort(nums)). And all of that std::vector<int> is gonna kill me! Is there any way to clean that mess too?

Answer 1

Some tips:

std::vector<int> FiletoVector()
{
    std::ifstream SortFile("Number_Sort.input");

    std::vector<int> vector;
    int read;

    while(SortFile >> read)
    {
        vector.push_back(read);
    }

    return vector;
}

Perfectly good readable code. But you can simplify it a bit using iterators.

The standard contains an input iterator that reads values from a stream.

`std::istream_iterator<T>`  // can be used to iterate through a stream.

Since most C++ loops are based on iterators lets update your code to use an iterator based approach.

std::vector<int> FiletoVector()
{
    std::ifstream SortFile("Number_Sort.input");

    std::vector<int> vector;

    std::istream_iterator<int>  fileIter(SortFile)
    for(; fileIter != std::istream_iterator<int>(); ++fileIter)
    {
        vector.push_back(*fileIter);
    }

    return vector;
}

But if you look at the constructor of vector you will see that you can constructor the vector using two iterators. So we can simplify the above code too:

std::vector<int> FiletoVector()
{
    std::ifstream SortFile("Number_Sort.input");

    std::vector<int> vector(std::istream_iterator<int>(SortFile),
                            std::istream_iterator<int>());

    return vector;
}

We can take this one step further as we don't need to have a local member. Just return the value:

std::vector<int> FiletoVector()
{
    std::ifstream SortFile("Number_Sort.input");

    return std::vector<int>(std::istream_iterator<int>(SortFile),
                            std::istream_iterator<int>());
}

Lets look at the timming function next:

void PrintTime(std::string sorttype, std::vector<int> funcinput(std::vector<int>), std::vector<int> vecinput)
{
    // Note `sortType` is passed by value (so you get a copy)
    //      funcinput  has to be a function that takes a vector of int
    //                 that seems overly limiting. 
    //      vecinput   Again you pass by value (so you get a copy)
    //                 This is probably on purpose so this is fine.
    //                 But be careful.
    //

    //Start Time
    float time = clock();

    funcinput(vecinput);

    //End Time
    time = (clock() - time) / CLOCKS_PER_SEC;

    std::cout << sorttype << " took " << time << " seconds!" << std::endl;
}

That all seems perfectly reasonable. But you are limiting yourself to sorting functions. I don't see the need for that. You should be able to time any function.

So just let your users pass in any function. Then you can specialize the function using a lambda later.

template<typename Action>
void PrintTime(std::string const& message, Action action)
{
    //Start Time
    float time = clock();

    action();

    //End Time
    time = (clock() - time) / CLOCKS_PER_SEC;

    std::cout << message << " took " << time << " seconds!\n";
}

Now you can call the function like this:

 PrintTime("Bubble Sort", [num](){BubbleSort(nums);});

So lets look at your sorting.

The first thing I notice is that you return a vector. This implies you are copying the vector at some point. Usually you sort in place for optimum performance.

You also pass by value. Which gets you that copy.

std::vector<int> BubbleSort(std::vector<int> vecinput)

Personally I would pass by reference to avoid a copy and then sort in place which means returning nothing.

void BubbleSort(std::vector<int>& vecinput)
^^^^                            ^

Secondly by specifying std::vector<int> you are limiting yourself to only sorting vectors of int. That are lots of things than can be sorted. So you should generalize this to sort any type.

template<typename T>
void BubbleSort(std::vector<T>& vecinput)

You can take this a step further by abstract the container type by allowing the user to pass in iterators.

template<typename I>
void BubbleSort(I begin, I end)

This is how the standard works. You have a bunch of containers and a bunch of algorithms. That glue that holds it all together are iterators. So you can perform nearly any algorithm on any container by passing iterators into the algorithm.

This allows you to sort vectors:

std::vector<int>   x = Load();
BubbleSort(std::begin(x), std::end(x));

But now you can also sort C-Arrays.

int  y[] = { 6,7,10,7,2,3,10};
BubbleSort(std::begin(y), std::end(y));

Three notes on your implementation of bubble sort

1. The best case version of bubble sort is O(n). You only need to do a single pass over the container if it is already sorted. So you should track if there was a swap on a given pass and exit early if no changes were made.

2. Secondly both loops go from [0..size). The inner loop does not need to cover the whole container. Each pass you have moved at least one item all the way to the correct location. So the next pass you don't need to check that item.

3. You do some manual swapping. There is a built in std::swap() in the standard that allows you to swap to object optimally.

This gives you something like this:

   bool noswap = false;
   for(int i = 0; noswap && i < vecinput.size(); i++)
   {
        noswap = true;
        for(int n = 0; n < vecinput.size() - i - 1; n++)
        {
            if(vecinput[n] > vecinput[n + 1])
            {
                std::swap(vecinput[n], vecinput[n + 1])
                noswap = false;
            }
        }
   }