Sign up ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I wrote a simple function to sort an array of integers in ascending order. Here is the code -

void sort(int* begin, int* end) {

    int* it = begin;

    int num1 = 0, num2 = 0;

    while (it != end) {

        num1 = *it;
        num2 = *(it + 1);

        if (num1 > num2) {

            *it = num2;
            *(it + 1) = num1;
            it = begin;

         } else {

             it++;

         }

    }

}

Is there any way I can improve this code?

share|improve this question

2 Answers 2

up vote 4 down vote accepted

Reading and writing off the end!

When it points to the last element (one before end), you read one-past-the-end, and then potentially write to it. This is undefined behavior. You need to make sure that you stop before then. One way to ensure this is to iterate from begin+1 to end, and compare the element with the one before it.

Logic

The typical way to write bubble sort is to have a loop that goes the full list, and set a flag if you swapped anything, and loop until you didn't. This will make it easier to understand what's going on - rather than having your loop next step set in two separate places, which is error prone.

Unnecessary variables

You don't need num1 or num2. Simply rely on std::swap:

if (*(it-1) > *it) {
    std::swap(*(it-1), *it);
    swapped = true;
}

Or you could implement such a thing yourself:

void swap(int& a, int& b) {
    int tmp = a;
    a = b;
    b = tmp;
}

Either way, avoiding unnecessary variables is a plus.

Spacing

Don't add so many blank statements between lines. Taking up too much vertical space makes it harder to read.

Proposed implementation

The following addresses all of my points:

void sort2(int* begin, int* end) {
    bool swapped = true;
    while (swapped) {
        swapped = false;
        for (int *it = begin+1; it != end; ++it) {
            if (*(it - 1) > *it) {
                std::swap(*(it - 1), *it);
                swapped = true;
            }
        }
    }
}

Minor optimization

Rewriting the way I did it above allows for a minor optimization. Every time through the for loop, we know that we just put the "largest" number at the end. It "bubbled" up! At that point, we don't need to do anything else with it, so we can decrement the end pointer:

while (swapped) {
    swapped = false;
    for (int *it = begin+1; it != end; ++it) {
       ...
    }

    --end; // <==
}

Future work

Bubble sort is \$O(n^2)\$. It gets the job done, but it's... not great. A strictly better algorithm to start with is insertion sort, which is still \$O(n^2)\$. From there, you can look at merge sort and quicksort, both \$O(n \lg n)\$.

Also consider what you'd need to do to be able to support (a) arbitrary types, not just ints and (b) in arbitrary order, not just increasing.

share|improve this answer
    
Supposedly bubble sort beats all other sorting algorithms in speed when you have 64 or less integers to sort due to cache friendliness. I'd be more careful about the strictly better part. – nwp 18 hours ago
    
@nwp I'm skeptical. Evidence? – Barry 16 hours ago
    
@nwp Pretty sure insertion sort is strictly better than bubble sort. Both beat quicksort on mostly-sorted input. Not sure cache friendliness is a factor. – Barry 15 hours ago
    
I think it wasn't that bubble sort beat all other sorting algorithms, just some common algorithms such as quick sort and merge sort. Your statement is probably correct, though confusing to read. It reads as if merge sort and quick sort were strictly better because it seems to not make sense to recommend a sorting algorithm that is not better. – nwp 12 hours ago
    
How about using std::iter_swap(it - 1, it)? – набиячлэвэлиь 7 hours ago

Declare function parameters as const

Since you are not modifying begin and end pointers itself in your function (rather values pointed by them may change). So ideally they should be made const like below,

void sort(int* const begin, int* const end)

Initialization is not required

 int num1 = 0, num2 = 0;

Since you are already assigning values within while loop, so initialization with 0 seems redundant but nothing wrong with it!

You can use std::swap

You can also use generic std::swap function instead of your handwritten code for swapping,

swap(*it, *(it+1));

Rest looks fine.

share|improve this answer
3  
int* const provides relatively little value, as outside observers don't really care whether the pointers are immutable within the function implementation. – 200_success 22 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.