3
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ Non in-place sort, wow. That's extremely rare in my experience. \$\endgroup\$ – Incomputable Oct 9 '17 at 7:06
  • \$\begingroup\$ What do you mean? I'm sort of new in programming so please bear with me. \$\endgroup\$ – The_Babu Oct 10 '17 at 19:05
2
\$\begingroup\$

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;
            }
        }
   }
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Would be great to check if file was opened. This is especially annoying if CMake doesn't handle copying of input files into binary directory. \$\endgroup\$ – Incomputable Oct 9 '17 at 19:24
  • \$\begingroup\$ Hey @Loki i just reviewed your code a little bit and I keep getting an error with this line of code: std::istream_iterator<int> fileIter(SortFile); I can't seem to find any reference to this so could you please explain it to me? \$\endgroup\$ – The_Babu Oct 11 '17 at 14:52
  • \$\begingroup\$ Oh wait... I'm stupid I forgot to include the iterator thing... \$\endgroup\$ – The_Babu Oct 11 '17 at 15:05
  • \$\begingroup\$ @Loki Atari Could you please explain to me what this means: ` PrintTime("Bubble Sort", [num](){BubbleSort(nums);});` ? Or of there is any other way to call this function or create an instantiation of it? \$\endgroup\$ – The_Babu Oct 12 '17 at 18:30
  • \$\begingroup\$ @Hacksaurus_Babu [num](){BubbleSort(nums);} This is called a lambda. Its a big topic so worth looking up. Simply put it is a self contained function; that you can call with operator(). So the function PrintTime() takes a string and a function. I pass a lambda (self contained function) that could do anything, but in this instance I pass a lambda that simply called BubbleSort() passing nums as a parameter. Inside BubbleSort() the function is called with action(); \$\endgroup\$ – Martin York Oct 12 '17 at 19:09

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.