Ascending Order Algorithm

Question

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?

Answer 1

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.

Answer 2

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.