6
\$\begingroup\$

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?

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – nwp Nov 26 '15 at 10:22
  • \$\begingroup\$ @nwp I'm skeptical. Evidence? \$\endgroup\$ – Barry Nov 26 '15 at 13:10
  • \$\begingroup\$ @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. \$\endgroup\$ – Barry Nov 26 '15 at 13:30
  • \$\begingroup\$ 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. \$\endgroup\$ – nwp Nov 26 '15 at 16:37
  • \$\begingroup\$ How about using std::iter_swap(it - 1, it)? \$\endgroup\$ – набиячлэвэлиь Nov 26 '15 at 22:11
3
\$\begingroup\$

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ int* const provides relatively little value, as outside observers don't really care whether the pointers are immutable within the function implementation. \$\endgroup\$ – 200_success Nov 26 '15 at 6:59

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.