Simple bubblesort algorithm in C++

Question

I have been learning C++ over the last couple of days. I know a few other programming languages well, and it hasn't been horribly difficult. I would appreciate any comments on my code so that I may improve:

• Readability
• CPP "style"
• Efficiency
• Vector vs array--which is better in this case?

Thanks in advance for any help you can give me.

//Bubblesort algorithm
#include <iostream>
#include <cstdlib>
#include <ctime>

#define pass ;

int main()
{
    // int unsorted[] = {1,2,3,4,5,6,7,8,9,10};
    int length;
    int max;
    srand(time(NULL));
    std::cout << "Please input how many numbers you want to sort and the max value on those numbers: " << std::endl;
    std::cin >> length;
    std::cin >> max;
    int unsorted[length];
    int count = -1;
    while(count++<length)
    {
        unsorted[count] = rand()%max;
    }
    //int length = sizeof( unsorted ) / sizeof( int );
    int i = 0;
    int num_changes_per_loop = 1; /* Should be set to zero at the beginning of each loop, but is nonzero here to prevent the loop from being cancelled on the first iteration */
    int general_loop_count = 0;
    while(general_loop_count++<length)
    {
        if(num_changes_per_loop==0) { break; }
        for(i=0;i<length-1;i++)
        {
            int current_value = unsorted[i];
            int adjacent_value = unsorted[i+1];
            if(adjacent_value > current_value) {pass}
            else if(current_value > adjacent_value) {
                std::cout << "These two values need to be switched!" << std::endl;
                int tmp = adjacent_value;
                unsorted[i+1] = current_value;
                unsorted[i] = tmp; 
                num_changes_per_loop++;
            }
        }
    }
    std::cout << "Finished!" << std::endl;
    for(i=0;i<length;i++)
    {
        std::cout << unsorted[i] << ", ";
    }
}

Answer 1

Vector vs raw array

When dealing with arrays that have a length know at run-time, you usually use an std::vector, it is cleaner and safer w.r.t the memory allocation (for dynamicity). When the size of the array is known at compile-time, consider using an std::array, which is the C++ way of using raw arrays.

In this case, I'd use an std::vector and a .reserve(length) call

Array out of bound

Here is a concrete argument to why you should use a vector: you are actually writing/reading outside of you array, which can fail immediately (if you are lucky), or can fail way later in your code (if you're unlucky).

int count = -1;
while(count++<length)
{
    unsorted[count] = rand()%max;
}

if you have length == 1 for example, here is what will happen, 'unwrapping' the while:

int count = -1;
if (count++ < 1) // count == -1, so count < 1 is true ; after that we increment count by 1, so count == 0 
{
    // accessint unsorted[0]
    unsorted[count] = rand()%max;
}
if (count++ < 1) // count == 0, so count < 1 is true ; after that we increment count by 1, so count == 1 
{
    // accessint unsorted[1], which is outside of the array
    unsorted[count] = rand()%max;
}
// after that, the condition is false

For loops vs while loops

Twice in your code, you have a while loop looking like this one:

int count = -1;
while(count++<length)

When you iterate this way, you usually see a for loop instead:

for(unsigned int count = 0 ; count < length ; ++count)

which does (almost) the same thing, but is more readable.

Note that the starting value is 0, leading into one less iteration than previously. However, it is actually the last iteration that is removed

Pass

In your main loop, you are using your pass macro. As jvb mentioned, you usually want to avoid to use macros (as the faq iso cpp says). Moreover, in this particular case, you may consider two alternatives:

• Using the continue keyword
• Reverting your condition

In this case, the second alternative is way better, as it is easy to put into place (the keyword continue shouldn't be used unless other alternatives are awkward).

if(adjacent_value > current_value) { continue; }
else if(current_value > adjacent_value) {
    // ...
}

would become

if(adjacent_value < current_value) {
    // ...
}

because you are really doing something only if the above condition is fulfilled

Swapping values

To swap your values, you are using your custom code

int tmp = adjacent_value;
unsorted[i+1] = current_value;
unsorted[i] = tmp; 

which works well.

However, you may consider using the function std::swap, that swaps two values:

std::swap(unsorted[i], unsorted[i+1]);

Answer 2

Aside from the std::stream operations, there's not much C++ to see... yet ;) But that will come, over time. So, you definitely should try out a std::vector. One of its advantages is that it encapsulates data and the item count... you can ask the vector for its size().

The pass #define... please don't do that. All this preprocessor stuff is handled even before the compiler will see the source code; and the preprocessor has - in a manner of speaking - a very bad grasp of language syntax. In the long run, you are bound to get very strange compile-/runtime-errors with stuff like that (...just imagine to find out after hours of debugging that someone somewhere has called a function pass).

In any language, it's recommended to check user input. If anyone will enter a "-1" for length, what will int unsorted[length]; do? Of course, that depends (but probably horrific things). Any dimension should be of an unsigned type, or (even better) size_t.

The naming could be improved - "unsorted" maybe is a little bit misleading - as the sorted final result will be in "unsorted" ;)

The "general_loop_count"-thing is a little bit strange. Usually, if one feels the urge to add comments like "should be set to zero at the beginning...", something is less from ideal. I usually write it like that (as follows), but of course you may find your own style. But it's always nice not to litter variables.

while(true) {
    unsigned changes=0;
    // ...sort loop here
    if (!changes) break;
}

For similar reasons, it's somewhat unusual (and a little bit dangerous) to declare an index variable i somewhere and to reuse it in different for loops through the program. The usual technique is to have a local counter like for(int i=0; i<length; i++)... which is available only in the loop body.

Strictly speaking, there is no need to have current_value/adjacent_value variables... at least one can get rid of tmp here. While sorting int, this is not of much importance, but imagine sorting (heavy) std::string or even larger things... it makes sense to minimize the copying operations.

And a final std::cout << std::end might give a nicer output.